Asymptotically faster quantum algorithms to solve multivariate quadratic equations
Asymptotically faster quantum algorithms to solve multivariate quadratic equations
复制标题
求解多元二次方程的渐进更快量子算法
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Bo
中科院分区：
文献类型：
--
作者：
D. Bernstein;Bo
设计并分析了求解有限域（{mathbf {F}} q）上m个n元二次方程组的量子算法。在（m=n）和（q=2）的情况下，在标准假设下，该算法在面积为（2^{（a+o（1））n}）的网格连接计算机上花费时间（2 ^{（t+o（1））n}），其中（tapprox 0.45743）和（aapprox 0.01467）。面积-时间乘积具有渐近指数（t+ aapprox0.47210）。
This paper designs and analyzes a quantum algorithm to solve a system of m quadratic equations in n variables over a finite field ({mathbf {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 (tapprox 0.45743) and (aapprox 0.01467). The area-time product has asymptotic exponent (t+aapprox 0.47210).