MQ / Boolean · quantum mesh · algebraic assumptions

Asymptotically faster quantum algorithms to solve multivariate quadratic equations

Daniel J. Bernstein · Bo-Yin Yang

PQCrypto 2018

PublishedSource checked

Time bound: 2^{(0.45743+o(1))n} mesh time
Space bound: Area 2^{(0.01467+o(1))n}

Source / version date: 18 Dec 2017
Comparison variant: Boolean · quantum mesh · algebraic assumptions
Cost scale: 2^{c n + o(n)}
area-exponent: 0.01467
area-time-exponent: 0.47210
assumptions: Standard source assumptions; m=n, q=2

Assumptions and source notes

Source model is a mesh-connected quantum computer, with area exponent 0.01467 and area-time exponent 0.47210. These resources must not be silently compared with sequential quantum gates.

Source location

Abstract
Version: Checked 2026-11-08; see linked source version/date

Primary source ↗

BibTeXDownload .bib

@misc{by17-mq,
  author = {Daniel J. Bernstein and Bo-Yin Yang},
  title = {{Asymptotically faster quantum algorithms to solve multivariate quadratic equations}},
  year = {2018},
  doi = {10.1007/978-3-319-79063-3_23},
  url = {https://eprint.iacr.org/2017/1206},
  keywords = {MQ, quantum mesh, area-time},
  cr_date = {2017-12-18},
  cr_date_precision = {day},
  cr_status = {published},
  cr_venue = {PQCrypto 2018},
  cr_author_ids = {daniel-j-bernstein; bo-yin-yang}
}