The quantum algorithm for linear systems of equations, designed by Aram Harrow, Avinatan Hassidim, and Seth Lloyd, is a quantum algorithm for solving linear systems formulated in 2009. The algorithm estimates the result of a scalar measurement on the solution vector to a given linear system of equations.
Contents
- Procedure
- Initialization
- Hamiltonian simulation
- U i n v e r t displaystyle Umathrm invert subroutine
- Main loop
- Scalar measurement
- Classical efficiency
- Quantum efficiency
- Optimality
- Error analysis
- Experimental realization
- Cai et al
- Barz et al
- Pan et al
- Applications
- Linear differential equation solving
- Least squares fitting
- Machine learning and big data analysis
- References
The algorithm is one of the main fundamental algorithms expected to provide a speedup over their classical counterparts, along with Shor's factoring algorithm, Grover's search algorithm and quantum simulation. Provided the linear system is a sparse and has a low condition number
An implementation of the quantum algorithm for linear systems of equations was first demonstrated in 2013 by Cai et al., Barz et al.and Pan et al. in parallel. The demonstrations consisted of simple linear equations on specially designed quantum devices.
Due to the prevalence of linear systems in virtually all areas of science and engineering, the quantum algorithm for linear systems of equations has the potential for widespread applicability.
Procedure
The problem we are trying to solve is: given a Hermitian
First, the algorithm represents the vector
Next, Hamiltonian simulation techniques are used to apply the unitary operator
The state of the system after this decomposition is approximately:
where
We would then like to perform the linear map taking
Where
Initialization
Firstly, the algorithm requires that the matrix
As
Secondly, The algorithm requires an efficient procedure to prepare
Finally, the algorithm assumes that the state
for some large
Hamiltonian simulation
Hamiltonian simulation is used to transform the Hermitian matrix
U i n v e r t {displaystyle U_{mathrm {invert} }} subroutine
The key subroutine to the algorithm, denoted
1. Prepare
2. Apply the conditional Hamiltonian evolution (sum)
3. Apply the Fourier transform to the register C. Denote the resulting basis states with
4. Adjoin a three-dimensional register S in the state
5. Reverse steps 1–3, uncomputing any garbage produced along the way.
The phase estimation procedure in steps 1-3 allows for the estimation of eigenvalues of A up to error
The ancilla register in step 4 is necessary to construct a final state with inverted eigenvalues corresponding to the diagonalized inverse of A. In this register, the functions f, g, are called filter functions. The states 'nothing', 'well' and 'ill' are used to instruct the loop body on how to proceed; 'nothing' indicates that the desired matrix inversion has not yet taken place, 'well' indicates that the inversion has taken place and the loop should halt, and 'ill' indicates that part of
Main loop
The body of the algorithm follows the amplitude amplification procedure: starting with
where
and
After each repetition,
Scalar measurement
After successfully measuring 'well' on
Finally, we perform the quantum-mechanical operator corresponding to M and obtain an estimate of the value of
Classical efficiency
The best classical algorithm which produces the actual solution vector
If A is s-sparse and positive semi-definite, then the Conjugate Gradient method can be used to find the solution vector
When only a summary statistic of the solution vector
Quantum efficiency
The quantum algorithm for solving linear systems of equations originally proposed by Harrow et al. was shown to be
Optimality
An important factor in the performance of the matrix inversion algorithm is the condition number of
If the run-time of the algorithm were made poly-logarithmic in
Error analysis
Performing the Hamiltonian simulation, which is the dominant source of error, is done by simulating
The phase estimation step errs by
Experimental realization
While there does not yet exist a quantum computer that can truly offer a speedup over a classical computer, implementation of a "proof of concept" remains an important milestone in the development of a new quantum algorithm. Demonstrating the quantum algorithm for linear systems of equations remained a challenge for years after its proposal until 2013 when it was demonstrated by Cai et al., Barz et al. and Pan et al. in parallel.
Cai et al.
Published in Physical Review Letters 110, 230501 (2013), Cai et al. reported an experimental demonstration of the simplest meaningful instance of this algorithm, that is, solving 2*2 linear equations for various input vectors. The quantum circuit is optimized and compiled into a linear optical network with four photonic quantum bits (qubits) and four controlled logic gates, which is used to coherently implement every subroutine for this algorithm. For various input vectors, the quantum computer gives solutions for the linear equations with reasonably high precision, ranging from fidelities of 0.825 to 0.993.
Barz et al.
On February 5, 2013, Barz et al. demonstrated the quantum algorithm for linear systems of equations on a photonic quantum computing architecture. This implementation used two consecutive entangling gates on the same pair of polarization-encoded qubits. Two separately controlled NOT gates were realized where the successful operation of the first was heralded by a measurement of two ancillary photons. Barz et al. found that the fidelity in the obtained output state ranged from 64.7% to 98.1% due to the influence of higher-order emissions from spontaneous parametric down-conversion.
Pan et al.
On February 8, 2013 Pan et al. reported a proof-of-concept experimental demonstration of the quantum algorithm using a 4-qubit nuclear magnetic resonance quantum information processor. The implementation was tested using simple linear systems of only 2 variables. Across three experiments they obtain the solution vector with over 96% fidelity.
Applications
Quantum computers are devices that harness quantum mechanics to perform computations in ways that classical computers cannot. For certain problems, quantum algorithms supply exponential speedups over their classical counterparts, the most famous example being Shor's factoring algorithm. Few such exponential speedups are known, and those that are (such as the use of quantum computers to simulate other quantum systems) have so far found limited use outside the domain of quantum mechanics. This algorithm provides an exponentially faster method of estimating features of the solution of a set of linear equations, which is a problem ubiquitous in science and engineering, both on its own and as a subroutine in more complex problems.
Linear differential equation solving
Dominic Berry proposed a new algorithm for solving linear time dependent differential equations as an extension of the quantum algorithm for solving linear systems of equations. Berry provides an efficient algorithm for solving the full-time evolution under sparse linear differential equations on a quantum computer.
Least-squares fitting
Wiebe et al. provide a new quantum algorithm to determine the quality of a least-squares fit in which a continuous function is used to approximate a set of discrete points by extending the quantum algorithm for linear systems of equations. As the amount of discrete points increases, the time required to produce a least-squares fit using even a quantum computer running a quantum state tomography algorithm becomes very large. Wiebe et al. find that in many cases, their algorithm can efficiently find a concise approximation of the data points, eliminating the need for the higher-complexity tomography algorithm.
Machine learning and big data analysis
Machine learning is the study of systems that can identify trends in data. Tasks in machine learning frequently involve manipulating and classifying a large volume of data in high-dimensional vector spaces. The runtime of classical machine learning algorithms is limited by a polynomial dependence on both the volume of data and the dimensions of the space. Quantum computers are capable of manipulating high-dimensional vectors using tensor product spaces are thus the perfect platform for machine learning algorithms.
The quantum algorithm for linear systems of equations has been applied to a support vector machine, which is an optimized linear or non-linear binary classifier. A support vector machine can be used for supervised machine learning, in which training set of already classified data is available, or unsupervised machine learning, in which all data given to the system is unclassified. Rebentrost et al. show that a quantum support vector machine can be used for big data classification and achieve an exponential speedup over classical computers.