Chang Chia Cheng, Gambhir Arjun, Humble Travis S, Sota Shigetoshi
RIKEN Interdisciplinary Theoretical and Mathematical Sciences (iTHEMS), Wako, Saitama, 351-0198, Japan.
Department of Physics, University of California, Berkeley, California, 94720, USA.
Sci Rep. 2019 Jul 16;9(1):10258. doi: 10.1038/s41598-019-46729-0.
Numerous scientific and engineering applications require numerically solving systems of equations. Classically solving a general set of polynomial equations requires iterative solvers, while linear equations may be solved either by direct matrix inversion or iteratively with judicious preconditioning. However, the convergence of iterative algorithms is highly variable and depends, in part, on the condition number. We present a direct method for solving general systems of polynomial equations based on quantum annealing, and we validate this method using a system of second-order polynomial equations solved on a commercially available quantum annealer. We then demonstrate applications for linear regression, and discuss in more detail the scaling behavior for general systems of linear equations with respect to problem size, condition number, and search precision. Finally, we define an iterative annealing process and demonstrate its efficacy in solving a linear system to a tolerance of 10.
众多科学和工程应用都需要对方程组进行数值求解。传统上，求解一般的多项式方程组需要迭代求解器，而线性方程组既可以通过直接求矩阵的逆来求解，也可以通过明智的预处理进行迭代求解。然而，迭代算法的收敛性变化很大，部分取决于条件数。我们提出了一种基于量子退火的直接方法来求解一般的多项式方程组，并使用在市售量子退火器上求解的二阶多项式方程组系统对该方法进行了验证。然后，我们展示了线性回归的应用，并更详细地讨论了一般线性方程组系统相对于问题规模、条件数和搜索精度的缩放行为。最后，我们定义了一种迭代退火过程，并证明了其在将线性系统求解到10的容差方面的有效性。
