Harrow, Hassidim, and Lloyd [ Phys. Rev. Lett., 103 (2009), 150502] showed that for a suitably specified $N \times N$ matrix $A$ and an $N$-dimensional vector $\vec{b}$, there is a quantum algorithm that outputs a quantum state proportional to the solution of the linear system of equations $A\vec{x} = \vec{b}$. If $A$ is sparse and well-conditioned, their algorithm runs in time ${poly}(\log N, 1/\epsilon)$, where $\epsilon$ is the desired precision in the output state. We improve this to an algorithm whose running time is polynomial in $\log(1/\epsilon)$, exponentially improving the dependence on precision while keeping essentially the same dependence on other parameters. Our algorithm is based on a general technique for implementing any operator with a suitable Fourier or Chebyshev series representation. This allows us to bypass the quantum phase estimation algorithm, whose dependence on $\epsilon$ is prohibitive.
Harrow, Hassidim, and Lloyd [ Phys. Rev. Lett., 103 (2009), 150502] showed that for a suitably specified N×N matrix A and an N-dimensional vector b, there is a quantum algorithm that outputs a quantum state proportional to the solution of the linear system of equations Ax=b. If A is sparse and well-conditioned, their algorithm runs in time poly(logN,1/ϵ), where ϵ is the desired precision in the output state. We improve this to an algorithm whose running time is polynomial in log(1/ϵ), exponentially improving the dependence on precision while keeping essentially the same dependence on other parameters. Our algorithm is based on a general technique for implementing any operator with a suitable Fourier or Chebyshev series representation. This allows us to bypass the quantum phase estimation algorithm, whose dependence on ϵ is prohibitive.
Harrow, Hassidim, and Lloyd showed that for a suitably specified N×N
matrix A and N-dimensional vector b, there is a quantum algorithm
that outputs a quantum state proportional to the solution of the linear system
of equations Ax=b. If A is sparse and well-conditioned, their
algorithm runs in time poly(logN,1/ϵ), where ϵ is
the desired precision in the output state. We improve this to an algorithm
whose running time is polynomial in log(1/ϵ), exponentially improving
the dependence on precision while keeping essentially the same dependence on
other parameters. Our algorithm is based on a general technique for
implementing any operator with a suitable Fourier or Chebyshev series
representation. This allows us to bypass the quantum phase estimation
algorithm, whose dependence on ϵ is prohibitive.
The Harrow-Hassidim-Lloyd (HHL) quantum algorithm for sampling from the solution of a linear system provides an exponential speed-up over its classical counterpart. The problem of solving a system of linear equations has a wide scope of applications, and thus HHL constitutes an important algorithmic primitive. In these notes, we present the HHL algorithm and its improved versions in detail, including explanations of the constituent sub- routines. More specifically, we discuss various quantum subroutines such as quantum phase estimation and amplitude amplification, as well as the important question of loading data into a quantum computer, via quantum RAM. The improvements to the original algorithm exploit variable-time amplitude amplification as well as a method for implementing linear combinations of unitary operations (LCUs) based on a decomposition of the operators using Fourier and Chebyshev series. Finally, we discuss a linear solver based on the quantum singular value estimation (QSVE) subroutine.
Solving linear systems of equations is a frequently encountered problem in machine learning and optimization. Given a matrix A and a vector b the task is to find the vector x such that Ax=b. We describe a quantum algorithm that achieves a sparsity-independent runtime scaling of $\mathcal{O}\mathbf{(}{\ensuremath{\kappa}}^{2}\sqrt{n}\text{polylog}(n)/\ensuremath{\epsilon}\mathbf{)}$ for an $n\ifmmode\times\else\texttimes\fi{}n$ dimensional A with bounded spectral norm, where $\ensuremath{\kappa}$ denotes the condition number of A, and $\ensuremath{\epsilon}$ is the desired precision parameter. This amounts to a polynomial improvement over known quantum linear system algorithms when applied to dense matrices, and poses a new state of the art for solving dense linear systems on a quantum computer. Furthermore, an exponential improvement is achievable if the rank of A is polylogarithmic in the matrix dimension. Our algorithm is built upon a singular value estimation subroutine, which makes use of a memory architecture that allows for efficient preparation of quantum states that correspond to the rows of A and the vector of Euclidean norms of the rows of A.
Solving linear systems of equations is a common problem that arises both on its own and as a subroutine in more complex problems: given a matrix A and a vector $\stackrel{\ensuremath{\rightarrow}}{b}$, find a vector $\stackrel{\ensuremath{\rightarrow}}{x}$ such that $A\stackrel{\ensuremath{\rightarrow}}{x}=\stackrel{\ensuremath{\rightarrow}}{b}$. We consider the case where one does not need to know the solution $\stackrel{\ensuremath{\rightarrow}}{x}$ itself, but rather an approximation of the expectation value of some operator associated with $\stackrel{\ensuremath{\rightarrow}}{x}$, e.g., ${\stackrel{\ensuremath{\rightarrow}}{x}}^{\ifmmode\dagger\else\textdagger\fi{}}M\stackrel{\ensuremath{\rightarrow}}{x}$ for some matrix M. In this case, when A is sparse, $N\ifmmode\times\else\texttimes\fi{}N$ and has condition number $\ensuremath{\kappa}$, the fastest known classical algorithms can find $\stackrel{\ensuremath{\rightarrow}}{x}$ and estimate ${\stackrel{\ensuremath{\rightarrow}}{x}}^{\ifmmode\dagger\else\textdagger\fi{}}M\stackrel{\ensuremath{\rightarrow}}{x}$ in time scaling roughly as $N\sqrt{\ensuremath{\kappa}}$. Here, we exhibit a quantum algorithm for estimating ${\stackrel{\ensuremath{\rightarrow}}{x}}^{\ifmmode\dagger\else\textdagger\fi{}}M\stackrel{\ensuremath{\rightarrow}}{x}$ whose runtime is a polynomial of log(N) and $\ensuremath{\kappa}$. Indeed, for small values of $\ensuremath{\kappa}$ [i.e., polylog(N)], we prove (using some common complexity-theoretic assumptions) that any classical algorithm for this problem generically requires exponentially more time than our quantum algorithm.
In the quantum linear systems problem (QLSP), we are given query access to a d-sparse N×N matrix A with condition number κ, and the ability to prepare a quantum state proportional to a vector b. The goal is to output an ε-approximation to the quantum state proportional to the solution x of Ax=b. Following a long line of work, the best previously known quantum algorithms for the QLSP had query complexities O(κdlog(1/ε)) and κd(κd/ε)o(1), while the best known lower bounds were Ω(κlog(1/ε)) and Ω(κd). We improve these bounds and show that the complexity of the QLSP is Θ(κdlog(1/ε)). We also resolve an open problem of Berry and Childs by showing that any N×N unitary can be implemented with bounded error using O(N) queries to its matrix entries.
Given a matrix A of dimension M×N and a vector b, the quantum linear system (QLS) problem asks for the preparation of a quantum state ∣y⟩ proportional to the solution of Ay=b. Existing QLS algorithms have runtimes that scale linearly with the condition number κ(A), the sparsity of A, and logarithmically with inverse precision, but often overlook structural properties of b, whose alignment with A's eigenspaces can greatly affect performance. In this work, we present a new QLS algorithm that explicitly leverages the structure of the right-hand side vector b. The runtime of our algorithm depends polynomially on the sparsity of the augmented matrix H=[A,−b], the inverse precision, the ℓ2 norm of the solution y=A+b, and a new instance-dependent parameter ET=∑i=1Mpi2⋅di, where p=(AA⊤)+b, and di denotes the squared ℓ2 norm of the i-th row of H. We also introduce a structure-aware rescaling technique tailored to the solution y=A+b. Unlike left preconditioning methods, which transform the linear system to DAy=Db, our approach applies a right rescaling matrix, reformulating the linear system as ADz=b. As an application of our instance-aware QLS algorithm and new rescaling scheme, we develop a quantum algorithm for solving multivariate polynomial systems in regimes where prior QLS-based methods fail. This yields an end-to-end framework applicable to a broad class of problems. In particular, we apply it to the maximum independent set (MIS) problem, formulated as a special case of a polynomial system, and show through detailed analysis that, under certain conditions, our quantum algorithm for MIS runs in polynomial time.