Multivariate quadratic equations
Solve a system of m quadratic equations in n variables over a specified finite field.
Boolean · quantum mesh · algebraic assumptions
m=n over F_2; mesh time exponent with an explicit area budget
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| 1 | Asymptotically faster quantum algorithms to solve multivariate quadratic equationsPQCrypto 2018SourceBibTeX / details | 18 Dec 2017 | 2(0.45743+o(1))n mesh time | Area 2(0.01467+o(1))n | PublishedSource checked |
Comparison definition & assumptions
- Regime
- m=n over F_2; mesh time exponent with an explicit area budget
- Computation
- Quantum
- Rigor
- Conditional
- Instances
- Mesh-connected quantum computation
- Cost scale
- 2^{c n + o(n)}
- Parameter
- n
- Description
- m=n over F_2; mesh time exponent with an explicit area budget
- Comparison rules
- Time refers to the mesh-connected architecture in the source, not a sequential gate count. Keep the area exponent beside the time exponent; an unrestricted parallel-time leaderboard would be meaningless.
- Tags
- binary field, quantum mesh, area-time