Fast Quantum Algorithm for Solving Multivariate Quadratic Equations

Jean-Charles Faugère · Kelsey Horan · Delaram Kahrobaei · Marc Kaplan · Elham Kashefi · Ludovic Perret

arXiv 1712.07211

Time bound

O(2^0.462n) expected quantum gates

Space bound

Not stated in the checked source

Source / version date

19 Dec 2017

Comparison variant

Boolean · quantum gates · algebraic assumptions

Cost scale

2^{c n + o(n)}

success

Las Vegas; expected quantum gates

equations

m=n

field

F_2

Assumptions and source notes

Las Vegas quantum gate count for m=n, under the source algebraic assumption. No claim of unconditional worst-case improvement is made.

Source location

Abstract, arXiv:1712.07211v1
Version: Checked 2026-11-08; see linked source version/date

Primary source ↗

@misc{fhkkkp17,
  author = {Jean-Charles Faugère and Kelsey Horan and Delaram Kahrobaei and Marc Kaplan and Elham Kashefi and Ludovic Perret},
  title = {{Fast Quantum Algorithm for Solving Multivariate Quadratic Equations}},
  year = {2017},
  url = {https://arxiv.org/abs/1712.07211},
  keywords = {MQ, quantum gates, BooleanSolve},
  cr_date = {2017-12-19},
  cr_date_precision = {day},
  cr_status = {preprint},
  cr_venue = {arXiv:1712.07211},
  cr_author_ids = {jean-charles-faugere; kelsey-horan; delaram-kahrobaei; marc-kaplan; elham-kashefi; ludovic-perret}
}