Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2310.15441

Convergence rate of algorithms for solving linear equations by quantum annealing

V. S. Shalgin, Tikhomirov, S.

Published Oct 24, 2023• 0 citations
arXivHTMLPDF

Abstract

We consider various iterative algorithms for solving the linear equation $ax=b$ using a quantum computer operating on the principle of quantum annealing. Assuming that the computer's output is described by the Boltzmann distribution, it is shown under which conditions the equation-solving algorithms converge, and an estimate of their convergence rate is provided. The application of this approach to algorithms using both an infinite number of qubits and a small number of qubits is discussed.

DOI
10.48550/arxiv.2310.15441

Related papers

Convergence Rate of Algorithm for Solving Linear Equations by Quantum Annealing

Sergey B. Tikhomirov, V. S. Shalgin

Various iterative algorithms for solving the linear equation $$ax = b$$ using a quantum computer operating on the principle of quantum annealing are studied. Assuming that the result produced by the computer is described by the Boltzmann distribution, conditions under which these algorithms converge are obtained and an estimate of their convergence rate is provided. Application of this approach for algorithms that use an infinite number of qubits and a small number of qubits is considered.

Computational Mathematics and Mathematical Physics•May 1, 2024•0 citations

CONVERGENCE RATE OF ALGORITHM FOR SOLVING LINEAR EQUATIONS BY QUANTUM ANNEALING

Sergey B. Tikhomirov, V. S. Shalgin

Various iterative algorithms for solving the linear equation ax = b using a quantum computer operating on the principle of quantum annealing are studied. Assuming that the result produced by the computer is described by the Boltzmann distribution, conditions under which these algorithms converge are obtained and an estimate of their convergence rate is provided. Application of this approach for algorithms that use an infinite number of qubits and a small number of qubits is considered.

Журнал вычислительной математики и математической физики•Nov 16, 2024•1 citation

How viable is quantum annealing for solving linear algebra problems?

Ajinkya Borle, Samuel J. Lomonaco

With the increasing popularity of quantum computing and in particular quantum annealing, there has been growing research to evaluate the meta-heuristic for various problems in linear algebra: from linear least squares to matrix and tensor factorization. At the core of this effort is to evaluate quantum annealing for solving linear least squares and linear systems of equations. In this work, we focus on the viability of using quantum annealing for solving these problems. We use simulations based on the adiabatic principle to provide new insights for previously observed phenomena with the D-wave machines, such as quantum annealing being robust against ill-conditioned systems of equations and scaling quite well against the number of rows in a system. We then propose a hybrid approach which uses a quantum annealer to provide a initial guess of the solution $x_0$, which would then be iteratively improved with classical fixed point iteration methods.

arXiv:2206.10576•Jun 21, 2022•6 citations

Quantum annealing for systems of polynomial equations

Chia Cheng Chang, Arjun Gambhir, Travis S. Humble +1 more

Abstract 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−8.

arXiv:1812.06917•Scientific Reports•Jul 16, 2019•33 citations

Quantum Annealing for Electromagnetic Engineers—Part I: A computational method to solve various types of optimization problems.

Sangbin Lee, Qi Jian Lim, Charles Ross +5 more

It is well known that electromagnetic computations are computationally demanding. Interestingly, many such problems can be recast to be solved by quantum annealing. Quantum annealing, a kind of quantum computer, utilizes quantum tunneling for state transitions, which enables one to find the global minimum in a complex energy landscape. Part I of this article explains quantum annealing for the classical electromagnetic community, assuming little knowledge of quantum theory. It reviews the basic principle and recent advances in quantum annealing to extend its applications, such as a hybrid quantum-classical annealing algorithm. Part II presents various examples of electromagnetic problems that can be solved by quantum annealing. These are 1) optimization of a reconfigurable directional metasurface, 2) finding current distribution in an arbitrary wire antenna, 3) finding charge and field distributions in a static condition, and 4) optimization of source excitation to focus fields in hyperthermia. Lastly, the performance of the quantum annealer is compared with classical solvers to deduce the type of applications in which a quantum annealer of current technologies can be preferred in practice.

IEEE Antennas and Propagation Magazine•Dec 13, 2024•10 citations

Quantum algorithm for solving matrix equations of the form AX = B

Xu Li, Xiaoqi Liu, Jin‐Min Liang +3 more

Abstract Solving linear systems of equations is of vital importance in various fields of science. With the scale of calculation soaring, classical computers are intractable, and the advantage of quantum computing is reflected. Quantum algorithm has exponential acceleration in solving the linear systems A x ⃗ = b ⃗ for sparse and well-conditioned coefficient matrix A with dimension N × N . In this paper, we present a quantum algorithm to solve matrix equations of the form AX = B , where X = ( x ⃗ 1 , x ⃗ 2 , … , x ⃗ n ) , B = ( b ⃗ 1 , b ⃗ 2 , … , b ⃗ n ) , x ⃗ k and b ⃗ k are unit vectors. The problem can be intuitively treated as solving n linear systems simultaneously, which will needs O ( n log N ) complexity by the famous HHL algorithm. We demonstrate that in our algorithm the scale of complexity is O ( log n N ) . In the error analysis part, phase estimation is discussed in details.

Laser Physics Letters•Mar 21, 2022•10 citations
We consider various iterative algorithms for solving the linear equation ax=bax=bax=b using a quantum computer operating on the principle of quantum annealing. Assuming that the computer's output is described by the Boltzmann distribution, it is shown under which conditions the equation-solving algorithms converge, and an estimate of their convergence rate is provided. The application of this approach to algorithms using both an infinite number of qubits and a small number of qubits is discussed.
Various iterative algorithms for solving the linear equation ax=bax = bax=b using a quantum computer operating on the principle of quantum annealing are studied. Assuming that the result produced by the computer is described by the Boltzmann distribution, conditions under which these algorithms converge are obtained and an estimate of their convergence rate is provided. Application of this approach for algorithms that use an infinite number of qubits and a small number of qubits is considered.
With the increasing popularity of quantum computing and in particular quantum annealing, there has been growing research to evaluate the meta-heuristic for various problems in linear algebra: from linear least squares to matrix and tensor factorization. At the core of this effort is to evaluate quantum annealing for solving linear least squares and linear systems of equations. In this work, we focus on the viability of using quantum annealing for solving these problems. We use simulations based on the adiabatic principle to provide new insights for previously observed phenomena with the D-wave machines, such as quantum annealing being robust against ill-conditioned systems of equations and scaling quite well against the number of rows in a system. We then propose a hybrid approach which uses a quantum annealer to provide a initial guess of the solution x0x_0x0​, which would then be iteratively improved with classical fixed point iteration methods.
Abstract 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−8.
It is well known that electromagnetic computations are computationally demanding. Interestingly, many such problems can be recast to be solved by quantum annealing. Quantum annealing, a kind of quantum computer, utilizes quantum tunneling for state transitions, which enables one to find the global minimum in a complex energy landscape. Part I of this article explains quantum annealing for the classical electromagnetic community, assuming little knowledge of quantum theory. It reviews the basic principle and recent advances in quantum annealing to extend its applications, such as a hybrid quantum-classical annealing algorithm. Part II presents various examples of electromagnetic problems that can be solved by quantum annealing. These are 1) optimization of a reconfigurable directional metasurface, 2) finding current distribution in an arbitrary wire antenna, 3) finding charge and field distributions in a static condition, and 4) optimization of source excitation to focus fields in hyperthermia. Lastly, the performance of the quantum annealer is compared with classical solvers to deduce the type of applications in which a quantum annealer of current technologies can be preferred in practice.
Abstract Solving linear systems of equations is of vital importance in various fields of science. With the scale of calculation soaring, classical computers are intractable, and the advantage of quantum computing is reflected. Quantum algorithm has exponential acceleration in solving the linear systems A x ⃗ = b ⃗ for sparse and well-conditioned coefficient matrix A with dimension N × N . In this paper, we present a quantum algorithm to solve matrix equations of the form AX = B , where X = ( x ⃗ 1 , x ⃗ 2 , … , x ⃗ n ) , B = ( b ⃗ 1 , b ⃗ 2 , … , b ⃗ n ) , x ⃗ k and b ⃗ k are unit vectors. The problem can be intuitively treated as solving n linear systems simultaneously, which will needs O ( n log N ) complexity by the famous HHL algorithm. We demonstrate that in our algorithm the scale of complexity is O ( log n N ) . In the error analysis part, phase estimation is discussed in details.