The quantum algorithm for linear systems of equations, also called HHL algorithm, designed by
Aram Harrow
Aram Wettroth Harrow (born 1980) is a professor of physics in the Massachusetts Institute of Technology's Center for Theoretical Physics.
Harrow works in quantum information science and quantum computing. Together with Avinatan Hassidim and Set ...
, Avinatan Hassidim, and
Seth Lloyd
Seth Lloyd (born August 2, 1960) is a professor of mechanical engineering and physics at the Massachusetts Institute of Technology.
His research area is the interplay of information with complex systems, especially quantum systems. He has perform ...
, is a
quantum algorithm
In quantum computing, a quantum algorithm is an algorithm which runs on a realistic model of quantum computation, the most commonly used model being the quantum circuit model of computation. A classical (or non-quantum) algorithm is a finite s ...
published in 2008 for solving
linear systems. The algorithm estimates the result of a scalar measurement on the solution vector to a given linear system of equations.
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 the
quantum fourier transform
In quantum computing, the quantum Fourier transform (QFT) is a linear transformation on quantum bits, and is the quantum analogue of the discrete Fourier transform. The quantum Fourier transform is a part of many quantum algorithms, notably Shor' ...
. Provided the linear system is
sparse and has a low
condition number
In numerical analysis, the condition number of a function measures how much the output value of the function can change for a small change in the input argument. This is used to measure how sensitive a function is to changes or errors in the inpu ...
, and that the user is interested in the result of a scalar measurement on the solution vector, instead of the values of the solution vector itself, then the algorithm has a runtime of
, where
is the number of variables in the linear system. This offers an exponential speedup over the fastest classical algorithm, which runs in
(or
for positive semidefinite matrices).
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.
The first demonstration of a general-purpose version of the algorithm appeared in 2018 in the work of Zhao et al.
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.
[Quantum Computer Runs The Most Practically Useful Quantum Algorithm, by Lu and Pan](_blank)
Procedure
The problem we are trying to solve is: given a
Hermitian matrix
In mathematics, a Hermitian matrix (or self-adjoint matrix) is a complex square matrix that is equal to its own conjugate transpose—that is, the element in the -th row and -th column is equal to the complex conjugate of the element in the -t ...
and a
unit vector
In mathematics, a unit vector in a normed vector space is a vector (often a spatial vector) of length 1. A unit vector is often denoted by a lowercase letter with a circumflex, or "hat", as in \hat (pronounced "v-hat").
The term ''direction v ...
, find the solution vector
satisfying
. This algorithm assumes that the user is not interested in the values of
itself, but rather the result of applying some operator
onto x,
.
First, the algorithm represents the vector
as a
quantum state
In quantum physics, a quantum state is a mathematical entity that provides a probability distribution for the outcomes of each possible measurement on a system. Knowledge of the quantum state together with the rules for the system's evolution i ...
of the form:
:
Next, Hamiltonian simulation techniques are used to apply the unitary operator
to
for a superposition of different times
. The ability to decompose
into the eigenbasis of
and to find the corresponding eigenvalues
is facilitated by the use of
quantum phase estimation.
The state of the system after this decomposition is approximately:
:
where
is the eigenvector basis of
, and
.
We would then like to perform the linear map taking
to
, where
is a normalizing constant. The linear mapping operation is not unitary and thus will require a number of repetitions as it has some probability of failing. After it succeeds, we uncomputed the
register and are left with a state proportional to:
:
where
is a quantum-mechanical representation of the desired solution vector ''x''. To read out all components of ''x'' would require the procedure be repeated at least ''N'' times. However, it is often the case that one is not interested in
itself, but rather some expectation value of a linear operator ''M'' acting on ''x''. By mapping ''M'' to a quantum-mechanical operator and performing the quantum measurement corresponding to ''M'', we obtain an estimate of the expectation value
. This allows for a wide variety of features of the vector ''x'' to be extracted including normalization, weights in different parts of the state space, and moments without actually computing all the values of the solution vector ''x''.
Explanation of the algorithm
Initialization
Firstly, the algorithm requires that the matrix
be
Hermitian {{Short description, none
Numerous things are named after the French mathematician Charles Hermite (1822–1901):
Hermite
* Cubic Hermite spline, a type of third-degree spline
* Gauss–Hermite quadrature, an extension of Gaussian quadrature m ...
so that it can be converted into a
unitary operator
In functional analysis, a unitary operator is a surjective bounded operator on a Hilbert space that preserves the inner product. Unitary operators are usually taken as operating ''on'' a Hilbert space, but the same notion serves to define the co ...
. In the case where
is not Hermitian, define
:
As
is Hermitian, the algorithm can now be used to solve
to obtain
.
Secondly, The algorithm requires an efficient procedure to prepare
, the quantum representation of b. It is assumed that there exists some linear operator
that can take some arbitrary quantum state
to
efficiently or that this algorithm is a subroutine in a larger algorithm and is given
as input. Any error in the preparation of state
is ignored.
Finally, the algorithm assumes that the state
can be prepared efficiently. Where
:
for some large
. The coefficients of
are chosen to minimize a certain quadratic loss function which induces error in the
subroutine described below.
Hamiltonian simulation
Hamiltonian simulation is used to transform the Hermitian matrix
into a unitary operator, which can then be applied at will. This is possible if ''A'' is ''s''-sparse and efficiently row computable, meaning it has at most ''s'' nonzero entries per row and given a row index these entries can be computed in time O(''s''). Under these assumptions, quantum Hamiltonian simulation allows
to be simulated in time
.
subroutine
The key subroutine to the algorithm, denoted
, is defined as follows and incorporates a
phase estimation subroutine:
1. Prepare
on register ''C''
2. Apply the conditional Hamiltonian evolution (sum)
3. Apply the Fourier transform to the register ''C''. Denote the resulting basis states with
for ''k'' = 0, ..., ''T'' − 1. Define
.
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
is in the ill-conditioned subspace of ''A'' and the algorithm will not be able to produce the desired inversion. Producing a state proportional to the inverse of ''A'' requires 'well' to be measured, after which the overall state of the system collapses to the desired state by the extended
Born rule
The Born rule (also called Born's rule) is a key postulate of quantum mechanics which gives the probability that a measurement of a quantum system will yield a given result. In its simplest form, it states that the probability density of findi ...
.
Main loop
The body of the algorithm follows the
amplitude amplification procedure: starting with
, the following operation is repeatedly applied:
:
where
:
and
:
After each repetition,
is measured and will produce a value of 'nothing', 'well', or 'ill' as described above. This loop is repeated until
is measured, which occurs with a probability
. Rather than repeating
times to minimize error, amplitude amplification is used to achieve the same error resilience using only
repetitions.
Scalar measurement
After successfully measuring 'well' on
the system will be in a state proportional to:
:
Finally, we perform the quantum-mechanical operator corresponding to M and obtain an estimate of the value of
.
Run time analysis
Classical efficiency
The best classical algorithm which produces the actual solution vector
is
Gaussian elimination
In mathematics, Gaussian elimination, also known as row reduction, is an algorithm for solving systems of linear equations. It consists of a sequence of operations performed on the corresponding matrix of coefficients. This method can also be used ...
, which runs in
time.
If ''A'' is ''s''-sparse and positive semi-definite, then the
Conjugate Gradient method
In mathematics, the conjugate gradient method is an algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a c ...
can be used to find the solution vector
, which can be found in
time by minimizing the quadratic function
.
When only a summary statistic of the solution vector
is needed, as is the case for the quantum algorithm for linear systems of equations, a classical computer can find an estimate of
in
.
Quantum efficiency
The runtime of the quantum algorithm for solving systems of linear equations originally proposed by Harrow et al. was shown to be
, where
is the error parameter and
is the
condition number
In numerical analysis, the condition number of a function measures how much the output value of the function can change for a small change in the input argument. This is used to measure how sensitive a function is to changes or errors in the inpu ...
of
. This was subsequently improved to
by Andris Ambainis
and a quantum algorithm with runtime polynomial in
was developed by Childs et al. Since the HHL algorithm maintains its logarithmic scaling in
only for sparse or low rank matrices, Wossnig et al.
extended the HHL algorithm based on a quantum singular value estimation technique and provided a linear system algorithm for dense matrices which runs in
time compared to the
of the standard HHL algorithm.
Optimality
An important factor in the performance of the matrix inversion algorithm is the
condition number
In numerical analysis, the condition number of a function measures how much the output value of the function can change for a small change in the input argument. This is used to measure how sensitive a function is to changes or errors in the inpu ...
, which represents the ratio of
's largest and smallest eigenvalues. As the condition number increases, the ease with which the solution vector can be found using gradient descent methods such as the
conjugate gradient method
In mathematics, the conjugate gradient method is an algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a c ...
decreases, as
becomes closer to a matrix which cannot be inverted and the solution vector becomes less stable. This algorithm assumes that all
singular values In mathematics, in particular functional analysis, the singular values, or ''s''-numbers of a compact operator T: X \rightarrow Y acting between Hilbert spaces X and Y, are the square roots of the (necessarily non-negative) eigenvalues of the self ...
of the matrix
lie between
and 1, in which case the claimed run-time proportional to
will be achieved. Therefore, the speedup over classical algorithms is increased further when
is a
.
If the run-time of the algorithm were made poly-logarithmic in
then problems solvable on ''n'' qubits could be solved in poly(''n'') time, causing the complexity class
BQP to be equal to
PSPACE
In computational complexity theory, PSPACE is the set of all decision problems that can be solved by a Turing machine using a polynomial amount of space.
Formal definition
If we denote by SPACE(''t''(''n'')), the set of all problems that can b ...
.
Error analysis
Performing the Hamiltonian simulation, which is the dominant source of error, is done by simulating
. Assuming that
is s-sparse, this can be done with an error bounded by a constant
, which will translate to the additive error achieved in the output state
.
The phase estimation step errs by
in estimating
, which translates into a relative error of
in
. If
, taking
induces a final error of
. This requires that the overall run-time efficiency be increased proportional to
to minimize error.
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
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,
Stefanie Barz
Stefanie Barz is a German physicist and Professor of Quantum Information and Technology at the University of Stuttgart. She studies quantum physics and quantum information in photonics.
Early life and education
Barz studied mathematics, physic ...
and co-workers 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.
Wen et al.
Another experimental demonstration using NMR for solving an 8*8 system was reported by Wen et al. in 2018 using the algorithm developed by Subaşı et al.
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.
Electromagnetic scattering
Clader et al. provided a preconditioned version of the linear systems algorithm that provided two advances. First, they demonstrated how a
preconditioner
In mathematics, preconditioning is the application of a transformation, called the preconditioner, that conditions a given problem into a form that is more suitable for numerical solving methods. Preconditioning is typically related to reducin ...
could be included within the quantum algorithm. This expands the class of problems that can achieve the promised exponential speedup, since the scaling of HHL and the best classical algorithms are both polynomial in the
condition number
In numerical analysis, the condition number of a function measures how much the output value of the function can change for a small change in the input argument. This is used to measure how sensitive a function is to changes or errors in the inpu ...
. The second advance was the demonstration of how to use HHL to solve for the
radar cross-section
Radar cross-section (RCS), also called radar signature, is a measure of how detectable an object is by radar. A larger RCS indicates that an object is more easily detected.
An object reflects a limited amount of radar energy back to the source. ...
of a complex shape. This was one of the first end to end examples of how to use HHL to solve a concrete problem exponentially faster than the best known classical algorithm.
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.
Finite element method
The
Finite Element Method
The finite element method (FEM) is a popular method for numerically solving differential equations arising in engineering and mathematical modeling. Typical problem areas of interest include the traditional fields of structural analysis, heat ...
uses large systems of linear equations to find approximate solutions to various physical and mathematical models. Montanaro and Pallister demonstrate that the HHL algorithm, when applied to certain FEM problems, can achieve a polynomial quantum speedup. They suggest that an exponential speedup is not possible in problems with fixed dimensions, and for which the solution meets certain smoothness conditions.
Quantum speedups for the finite element method are higher for problems which include solutions with higher-order derivatives and large spatial dimensions. For example, problems in many-body dynamics require the solution of equations containing derivatives on orders scaling with the number of bodies, and some problems in
computational finance
Computational finance is a branch of applied computer science that deals with problems of practical interest in finance.Rüdiger U. Seydel, '' tp://nozdr.ru/biblio/kolxo3/F/FN/Seydel%20R.U.%20Tools%20for%20Computational%20Finance%20(4ed.,%20Sprin ...
, such as
Black-Scholes models, require large spatial dimensions.
Least-squares fitting
Wiebe et al. provide a new quantum algorithm to determine the quality of a
least-squares fit
The method of least squares is a standard approach in regression analysis to approximate the solution of overdetermined systems (sets of equations in which there are more equations than unknowns) by minimizing the sum of the squares of the re ...
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 number 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
Machine learning (ML) is a field of inquiry devoted to understanding and building methods that 'learn', that is, methods that leverage data to improve performance on some set of tasks. It is seen as a part of artificial intelligence.
Machine ...
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 and 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
Though used sometimes loosely partly because of a lack of formal definition, the interpretation that seems to best describe Big data is the one associated with large body of information that we could not comprehend when used only in smaller am ...
classification and achieve an exponential speedup over classical computers.
In June 2018, Zhao et al. developed an algorithm for performing Bayesian training of deep neural networks in quantum computers with an exponential speedup over classical training due to the use of the quantum algorithm for linear systems of equations,
providing also the first general-purpose implementation of the algorithm to be run in
cloud-based quantum computers.
See also
*
Differentiable programming
References
{{DEFAULTSORT:Quantum Algorirthm for Linear Systems
Quantum algorithms
Integer factorization algorithms
Articles containing proofs