Multivariate quadratic equations
Solve a system of m quadratic equations in n variables over a specified finite field.
Boolean · quantum gates · algebraic assumptions
m=n quadratic equations over F_2; sequential quantum gate complexity
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| 1 | Fast Quantum Algorithm for Solving Multivariate Quadratic EquationsarXiv 1712.07211SourceBibTeX / details | 19 Dec 2017 | O(20.462n) expected quantum gates | Not stated in the checked source | PreprintSource checked |
Comparison definition & assumptions
- Regime
- m=n quadratic equations over F_2; sequential quantum gate complexity
- Computation
- Quantum
- Rigor
- Conditional
- Instances
- Algebraic regularity assumptions
- Cost scale
- 2^{c n + o(n)}
- Parameter
- n
- Description
- m=n quadratic equations over F_2; sequential quantum gate complexity
- Comparison rules
- Compare sequential quantum gate counts with source algebraic assumptions attached. Mesh depth, physical area and gate count are different resources and must not share a scalar ranking.
- Tags
- binary field, quantum gates, m=n