TY - CONF

T1 - Solving linear equations on adiabatic quantum computer

AU - Шалгин, Владимир Сергеевич

PY - 2021/12

Y1 - 2021/12

N2 - We consider the problem of solving the equation $ax=b$ using the adiabatic quantum computer D-Wave 2000Q. Due to the specifics of the computer, the task is reduced to finding the minimum of the function $H(x)=(ax-b)^2$, where $x=c\sum_{i=0}^{R-1}{2^{-i}q_i}-d$ --- is a $R$-bit representation of the desired minimum point up to scaling and shifting. A matrix of the quadratic form $H(q_0,\ldots,q_{R-1})$ it is sent to the computer as an input. The result of the computer is a random variable having a Boltzmann distribution. It is proved that in the case when $R,\,c,\,d\rightarrow+\infty$, the limiting distribution of solutions of the equation $ax=b$ is a normal distribution, or a truncated normal distribution when only $R\rightarrow+\infty$. The parameters of the distribution of solutions to one equation were found experimentally by minimizing the distance between the empirical distribution and the normal distribution in one case and the Boltzmann distribution in the other. An algorithm for refining the solution of the equation is constructed. Sufficient conditions for its convergence are found in the case of the assumption of a normal and truncated normal distribution of solutions. A generalization of the above results is developing for the case of a system of linear equations, including systems with no solutions or having infinitely many solutions.

AB - We consider the problem of solving the equation $ax=b$ using the adiabatic quantum computer D-Wave 2000Q. Due to the specifics of the computer, the task is reduced to finding the minimum of the function $H(x)=(ax-b)^2$, where $x=c\sum_{i=0}^{R-1}{2^{-i}q_i}-d$ --- is a $R$-bit representation of the desired minimum point up to scaling and shifting. A matrix of the quadratic form $H(q_0,\ldots,q_{R-1})$ it is sent to the computer as an input. The result of the computer is a random variable having a Boltzmann distribution. It is proved that in the case when $R,\,c,\,d\rightarrow+\infty$, the limiting distribution of solutions of the equation $ax=b$ is a normal distribution, or a truncated normal distribution when only $R\rightarrow+\infty$. The parameters of the distribution of solutions to one equation were found experimentally by minimizing the distance between the empirical distribution and the normal distribution in one case and the Boltzmann distribution in the other. An algorithm for refining the solution of the equation is constructed. Sufficient conditions for its convergence are found in the case of the assumption of a normal and truncated normal distribution of solutions. A generalization of the above results is developing for the case of a system of linear equations, including systems with no solutions or having infinitely many solutions.

M3 - Abstract

Y2 - 6 December 2021 through 10 December 2021

ER -