The algorithm estimates the result of a scalar measurement on the solution vector to a given linear system of equations.
An implementation of the quantum algorithm for linear systems of equations was first demonstrated in 2013 by three independent publications.
as a quantum state of the form: Next, Hamiltonian simulation techniques are used to apply the unitary operator
The linear mapping operation is not unitary and thus will require a number of repetitions as it has some probability of failing.
By mapping M to a quantum-mechanical operator and performing the quantum measurement corresponding to M, we obtain an estimate of the expectation value
The ancilla register in step 4 is necessary to construct a final state with inverted eigenvalues corresponding to the diagonalized inverse of A.
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
If A is s-sparse and positive semi-definite, then the Conjugate Gradient method can be used to find 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
The runtime of the quantum algorithm for solving systems of linear equations originally proposed by Harrow et al. was shown to be
only for sparse or low rank matrices, Wossnig et al.[10] extended the HHL algorithm based on a quantum singular value estimation technique and provided a linear system algorithm for dense matrices which runs in
then problems solvable on n qubits could be solved in poly(n) time, causing the complexity class BQP to be equal to PSPACE.
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
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.
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.
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.
Berry provides an efficient algorithm for solving the full-time evolution under sparse linear differential equations on a quantum computer.
[15] Two groups proposed[16] efficient algorithms for numerically integrating dissipative nonlinear ordinary differential equations.
Liu et al.[17] utilized Carleman linearization technique for second order equations and Lloyd et al.[18] employed a mean field linearization method inspired by nonlinear Schrödinger equation for general order nonlinearities.
The Finite Element Method 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.
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 thus are well-suited platforms for machine learning algorithms.
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.
[24] In 2023, Baskaran et al. proposed the use of HHL algorithm to quantum chemistry calculations, via the linearized coupled cluster method (LCC).
[25] The connection between the HHL algorithm and the LCC method is due to the fact that the latter can be recast in the form of system of linear equations.