HHL algorithm
≈ 7 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
The Harrow–Hassidim–Lloyd (HHL) algorithm is a quantum algorithm for obtaining certain limited information about the solution to a system of linear equations, introduced by Aram Harrow, Avinatan Hassidim, and Seth Lloyd. Specifically, the algorithm estimates quadratic functions of the solution vector to a given system. The algorithm is one of the main fundamental algorithms expected to provide a speedup over their classical counterparts, along with Shor's factoring algorithm and Grover's search algorithm. Assuming the system is sparse, has a low condition number \kappa , and that the user is only interested in certain information about solution vector and not the entire vector itself, the algorithm has a runtime of O(\log(N)\kappa^2) , where N is the number of variables. This offers an exponential speedup over the fastest classical algorithm, which runs in O(N\kappa) (or O(N\sqrt{\kappa}) for positive semidefinite matrices). An implementation of the HHL algorithm was first demonstrated in 2013 by three independent publications, consisting of simple systems on specially designed devices. The first demonstration of a general-purpose version of the algorithm appeared in 2018.
The Harrow–Hassidim–Lloyd (HHL) algorithm is a quantum algorithm for obtaining certain limited information about the solution to a system of linear equations, introduced by Aram Harrow, Avinatan Hassidim, and Seth Lloyd. Specifically, the algorithm estimates quadratic functions of the solution vector to a given system. The algorithm is one of the main fundamental algorithms expected to provide a speedup over their classical counterparts, along with Shor's factoring algorithm and Grover's search algorithm. Assuming the system is sparse, has a low condition number \kappa , and that the user is only interested in certain information about solution vector and not the entire vector itself, the algorithm has a runtime of O(\log(N)\kappa^2) , where N is the number of variables. This offers an exponential speedup over the fastest classical algorithm, which runs in O(N\kappa) (or O(N\sqrt{\kappa}) for positive semidefinite matrices). An implementation of the HHL algorithm was first demonstrated in 2013 by three independent publications, consisting of simple systems on specially designed devices. The first demonstration of a general-purpose version of the algorithm appeared in 2018. Given an N \times N Hermitian matrix A and unit vector \vec b\in\mathbb{R}^N , the HHL algorithms prepares the quantum state |x\rangle whose amplitudes are the entries of the solution \vec x\in\mathbb{R}^N to the linear system A\vec x=\vec b . The algorithm cannot efficiently output the solution x itself, but allows one to efficiently estimate \vec{x}^{T}M\vec{x} for a Hermitian matrix M . The algorithm first prepares the quantum state |b\rangle whose amplitudes are equal to the entries of \vec b . Using Hamiltonian simulation, the unitary operator e^{iAt} is applied to |b\rangle for a superposition of different times t. The algorithm then uses quantum phase estimation to decompose |b\rangle in the eigenbasis of A and find the corresponding eigenvalues \lambda_j . The state of the system after this step is approximately \sum_{j \mathop =1}^N \beta_j|u_j\rangle|\lambda_j\rangle, where u_j are the eigenvectors of A and \beta_j is the j-th coefficient of b in the eigenbasis of A. We would then like to apply the linear map taking |\lambda_j\rangle to C\lambda^{-1}_j|\lambda_j\rangle for some constant C. This map is not unitary and must be implemented using a quantum measurement with a nonzero probability of failure. After it succeeds, we have uncomputed the |\lambda_j\rangle register and have a state proportional to \sum_{i \mathop =1}^N \beta_i\lambda^{-1}_j|u_j\rangle=A^{-1}|b\rangle=|x\rangle. By performing the quantum measurement corresponding to M, we get an estimate of \vec{x}^{T}M\vec{x} . One could use quantum tomography to retrieve all components of x, but this would require repeating the algorithm roughly N times. The algorithm requires A to be Hermitian so that it can be exponentiated into a unitary operator. If A is not Hermitian, one can define a Hermitian matrix \mathbf{C} = \begin{bmatrix} 0 & A \\ A^\dagger & 0 \end{bmatrix} and solve Cy=\begin{bmatrix} b \\ 0 \end{bmatrix} to obtain y = \begin{bmatrix} 0 \\ x \end{bmatrix} . The algorithm requires an efficient procedure to prepare |b\rangle . It is assumed that either |b\rangle has already been prepared or there exists some B which takes some quantum state |\mathrm{initial}\rangle to |b\rangle efficiently. Any error in the preparation of |b\rangle is ignored. The algorithm assumes that the state | \psi_0 \rangle can be prepared efficiently, where | \psi_0 \rangle := \sqrt{2/T} \sum_{\tau \mathop =0}^{T-1} \sin\pi\left(\tfrac{\tau+\tfrac{1}{2}}{T}\right) |\tau\rangle for some large T. The coefficients of | \psi_0 \rangle are chosen to minimize a certain quadratic loss function which induces error in the U_\mathrm{invert} subroutine described below. The algorithm assumes that the unitary operator e^{iAt} can be applied efficiently. This is possible using Hamiltonian simulation if A is s-sparse and efficiently row computable, meaning it has at most s nonzero entries per row which can be computed in time O(s) given a row index. One can then apply e^{iAt} in time O(\log(N)s^2t) . Apply the Fourier transform to the register C. Denote the resulting basis states with |k\rangle for k = 0, ..., T − 1. Define \lambda_k:=2\pi k/t_0 . Adjoin a three-dimensional register S in the state |h(\lambda_k)\rangle^S := \sqrt{1-f(\lambda_k)^2 - g(\lambda_k)^2} |\mathrm{nothing} \rangle^S + f(\lambda_k)| \mathrm{well} \rangle^S+g (\lambda_k) | \mathrm{ill} \rangle^S, Reverse steps 1–3, uncomputing any garbage produced along the way. The phase estimation procedure in steps 1-3 estimates the eigenvalues of A up to error \epsilon . The ancilla register in step 4 is needed to construct a state with inverted eigenvalues corresponding to the diagonalized inverse of A. The states 'nothing', 'well' and 'ill' are used to direct the loop body; 'nothing' indicates that the matrix inversion has not yet taken place, 'well' indicates that it has and the loop should halt, and 'ill' indicates that part of |b\rangle is in the ill-conditioned subspace of A and the algorithm cannot produce the desired inversion. Producing a state proportional to the inverse of A requires 'well' to be measured, after which the overall state collapses to the desired output. \sum_{i \mathop =1}^N \beta_i \lambda^{-1}_j |u_j\rangle = A^{-1} |b \rangle = | x\rangle. The quantum measurement corresponding to M then gives an estimate of \vec{x}^{T}M\vec{x} . The phase estimation step errs by O(1/t_0) in estimating \lambda , which results in a relative error of O((\lambda t_0)^{-1}) in 1/\lambda . If \lambda \ge 1/\kappa , taking t_0=O(\kappa\varepsilon) induces a final error of \varepsilon . This requires the overall runtime to be increased proportional to O(1/\varepsilon) in order to minimize error.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1378875664 under CC BY-SA 4.0; modifications have been made.