Welcome to the resource topic for 2017/1206
Title:
Asymptotically faster quantum algorithms to solve multivariate quadratic equations
Authors: Daniel J. Bernstein, Bo-Yin Yang
Abstract:This paper designs and analyzes a quantum algorithm to solve a system of m quadratic equations in n variables over a finite field {\bf F}_q. In the case m=n and q=2, under standard assumptions, the algorithm takes time 2^{(t+o(1))n} on a mesh-connected computer of area 2^{(a+o(1))n}, where t\approx 0.45743 and a\approx 0.01467. The area-time product has asymptotic exponent t+a\approx 0.47210. For comparison, the area-time product of Grover’s algorithm has asymptotic exponent 0.50000. Parallelizing Grover’s algorithm to reach asymptotic time exponent 0.45743 requires asymptotic area exponent 0.08514, much larger than 0.01467.
ePrint: https://eprint.iacr.org/2017/1206
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .