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:1302.4310 · Physical Review Letters

Experimental Quantum Computing to Solve Systems of Linear Equations

Xiang Cai, Christian Weedbrook, Zu-En Su, Minjia Chen, Mile Gu, Mingzheng Zhu, Li Li, Nai-Le Liu, Chao‐Yang Lu, Jian-Wei Pan

Published Jun 6, 2013• 173 citations
arXivHTMLPDF

Abstract

Solving linear systems of equations is ubiquitous in all areas of science and engineering. With rapidly growing data sets, such a task can be intractable for classical computers, as the best known classical algorithms require a time proportional to the number of variables N. A recently proposed quantum algorithm shows that quantum computers could solve linear systems in a time scale of order log(N), giving an exponential speedup over classical computers. Here we realize the simplest instance of this algorithm, solving 2×2 linear equations for various input vectors on a quantum computer. We use four quantum bits and four controlled logic gates to implement every subroutine required, demonstrating the working principle of this algorithm.

DOI
10.1103/physrevlett.110.230501

Related papers

Experimental realization of quantum algorithm for solving linear systems of equations

Jian Pan, Yudong Cao, Xiwei Yao +6 more

Many important problems in science and engineering can be reduced to the problem of solving linear equations. The quantum algorithm discovered recently indicates that one can solve an $N$-dimensional linear equation in $O(logN)$ time, which provides an exponential speedup over the classical counterpart. Here we report an experimental demonstration of the quantum algorithm when the scale of the linear equation is $2\ifmmode\times\else\texttimes\fi{}2$ using a nuclear magnetic resonance quantum information processor. For all sets of experiments, the fidelities of the final four-qubit states are all above 96%. This experiment gives the possibility of solving a series of practical problems related to linear systems of equations and can serve as the basis to realize many potential quantum algorithms.

arXiv:1302.1946•Physical Review A•Feb 12, 2014•110 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

Solving Systems of Linear Equations with a Superconducting Quantum Processor

Yarui Zheng, Chao Song, Ming-Cheng Chen +15 more

Superconducting quantum circuits are a promising candidate for building scalable quantum computers. Here, we use a four-qubit superconducting quantum processor to solve a two-dimensional system of linear equations based on a quantum algorithm proposed by Harrow, Hassidim, and Lloyd [Phys. Rev. Lett. 103, 150502 (2009)PRLTAO0031-900710.1103/PhysRevLett.103.150502], which promises an exponential speedup over classical algorithms under certain circumstances. We benchmark the solver with quantum inputs and outputs, and characterize it by nontrace-preserving quantum process tomography, which yields a process fidelity of 0.837±0.006. Our results highlight the potential of superconducting quantum circuits for applications in solving large-scale linear systems, a ubiquitous task in science and engineering.

arXiv:1703.06613•Physical Review Letters•May 26, 2017•95 citations

Quantum circuit design for solving linear systems of equations

Yudong Cao, Ammar Daskin, Steven H. Frankel +1 more

Recently, it has been demonstrated that quantum computers can be used for solving linear systems of algebraic equations with exponential speedup compared with classical computers. Here, we present an efficient and generic quantum circuit design for implementing the algorithm for solving linear systems. In particular, we show the detailed construction of a quantum circuit which solves a 4 × 4 linear system with seven qubits. It consists of only the basic quantum gates that can be realized with present physical devices, implying great possibility for experimental implementation. Furthermore, the performance of the circuit is numerically simulated and its ability to solve the intended linear system is verified.

arXiv:1110.2232•Molecular Physics•May 15, 2012•64 citations

Quantum Problem Solvers

I. S. Osborne

Applied Physics Quantum computers, when they become available, will harness the power of quantum mechanics to perform calculations and searches, outperforming classical computers at certain tasks. The development of quantum computers is two-pronged: Both hardware and software must be devised. The focus in the software realm is on which problems can be solved and how to do so. Solving a set of linear equations is a generic and important problem in many fields of science, engineering, and mathematics. On a classical computer the computational cost of extracting a solution grows linearly with the size of the system. Harrow et al. have developed a quantum algorithm that will solve the problem much more rapidly (scaling as the logarithm of the system size), requiring exponentially less time. Now we wait for the machinery to arrive. Phys. Rev. Lett. 103 , 150502 (2009).

Science•Oct 29, 2009•0 citations

Quantum algorithm for solving linear differential equations: Theory and experiment

Tao Xin, Shijie Wei, Jianlian Cui +7 more

Solving linear differential equations (LDEs) is a hard problem for classical computers, while quantum algorithms have been proposed to be capable of speeding up the calculation. However, they are yet to be realized in experiment as it cannot be easily converted into an implementable quantum circuit. Here, we present and experimentally realize an implementable gate-based quantum algorithm for efficiently solving the LDE problem: given an $N\ifmmode\times\else\texttimes\fi{}N$ matrix $\mathcal{M}$, an $N$-dimensional vector $\mathbf{b}$, and an initial vector $\mathbf{x}(0)$, we obtain a target vector $\mathbf{x}(t)$ as a function of time $t$ according to the constraint $d\mathbf{x}(t)/dt=\mathcal{M}\mathbf{x}(t)+\mathbf{b}$. We show that our algorithm exhibits an exponential speedup over its classical counterpart in certain circumstances, and a gate-based quantum circuit is produced which is friendly to the experimentalists and implementable in current quantum techniques. In addition, we experimentally solve a $4\ifmmode\times\else\texttimes\fi{}4$ linear differential equation using our quantum algorithm in a four-qubit nuclear magnetic resonance quantum information processor. Our algorithm provides a key technique for solving many important problems which rely on the solutions to linear differential equations.

arXiv:1807.04553•Physical Review A•Mar 6, 2020•86 citations
Solving linear systems of equations is ubiquitous in all areas of science and engineering. With rapidly growing data sets, such a task can be intractable for classical computers, as the best known classical algorithms require a time proportional to the number of variables N. A recently proposed quantum algorithm shows that quantum computers could solve linear systems in a time scale of order log(N), giving an exponential speedup over classical computers. Here we realize the simplest instance of this algorithm, solving 2×2 linear equations for various input vectors on a quantum computer. We use four quantum bits and four controlled logic gates to implement every subroutine required, demonstrating the working principle of this algorithm.
Many important problems in science and engineering can be reduced to the problem of solving linear equations. The quantum algorithm discovered recently indicates that one can solve an NNN-dimensional linear equation in O(logN)O(logN)O(logN) time, which provides an exponential speedup over the classical counterpart. Here we report an experimental demonstration of the quantum algorithm when the scale of the linear equation is $2\ifmmode\times\else\texttimes\fi{}2$ using a nuclear magnetic resonance quantum information processor. For all sets of experiments, the fidelities of the final four-qubit states are all above 96%. This experiment gives the possibility of solving a series of practical problems related to linear systems of equations and can serve as the basis to realize many potential quantum algorithms.
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.
Superconducting quantum circuits are a promising candidate for building scalable quantum computers. Here, we use a four-qubit superconducting quantum processor to solve a two-dimensional system of linear equations based on a quantum algorithm proposed by Harrow, Hassidim, and Lloyd [Phys. Rev. Lett. 103, 150502 (2009)PRLTAO0031-900710.1103/PhysRevLett.103.150502], which promises an exponential speedup over classical algorithms under certain circumstances. We benchmark the solver with quantum inputs and outputs, and characterize it by nontrace-preserving quantum process tomography, which yields a process fidelity of 0.837±0.006. Our results highlight the potential of superconducting quantum circuits for applications in solving large-scale linear systems, a ubiquitous task in science and engineering.
Recently, it has been demonstrated that quantum computers can be used for solving linear systems of algebraic equations with exponential speedup compared with classical computers. Here, we present an efficient and generic quantum circuit design for implementing the algorithm for solving linear systems. In particular, we show the detailed construction of a quantum circuit which solves a 4 × 4 linear system with seven qubits. It consists of only the basic quantum gates that can be realized with present physical devices, implying great possibility for experimental implementation. Furthermore, the performance of the circuit is numerically simulated and its ability to solve the intended linear system is verified.
Applied Physics Quantum computers, when they become available, will harness the power of quantum mechanics to perform calculations and searches, outperforming classical computers at certain tasks. The development of quantum computers is two-pronged: Both hardware and software must be devised. The focus in the software realm is on which problems can be solved and how to do so. Solving a set of linear equations is a generic and important problem in many fields of science, engineering, and mathematics. On a classical computer the computational cost of extracting a solution grows linearly with the size of the system. Harrow et al. have developed a quantum algorithm that will solve the problem much more rapidly (scaling as the logarithm of the system size), requiring exponentially less time. Now we wait for the machinery to arrive. Phys. Rev. Lett. 103 , 150502 (2009).
Solving linear differential equations (LDEs) is a hard problem for classical computers, while quantum algorithms have been proposed to be capable of speeding up the calculation. However, they are yet to be realized in experiment as it cannot be easily converted into an implementable quantum circuit. Here, we present and experimentally realize an implementable gate-based quantum algorithm for efficiently solving the LDE problem: given an $N\ifmmode\times\else\texttimes\fi{}N$ matrix M\mathcal{M}M, an NNN-dimensional vector b\mathbf{b}b, and an initial vector x(0)\mathbf{x}(0)x(0), we obtain a target vector x(t)\mathbf{x}(t)x(t) as a function of time ttt according to the constraint dx(t)/dt=Mx(t)+bd\mathbf{x}(t)/dt=\mathcal{M}\mathbf{x}(t)+\mathbf{b}dx(t)/dt=Mx(t)+b. We show that our algorithm exhibits an exponential speedup over its classical counterpart in certain circumstances, and a gate-based quantum circuit is produced which is friendly to the experimentalists and implementable in current quantum techniques. In addition, we experimentally solve a $4\ifmmode\times\else\texttimes\fi{}4$ linear differential equation using our quantum algorithm in a four-qubit nuclear magnetic resonance quantum information processor. Our algorithm provides a key technique for solving many important problems which rely on the solutions to linear differential equations.