We establish an improved classical algorithm for solving linear systems in a model analogous to the QRAM that is used by quantum linear solvers. Precisely, for the linear system \( A{\bf x}= {\bf b} \) , we show that there is a classical algorithm that outputs a data structure for \( {\bf x} \) allowing sampling and querying to the entries, where \( {\bf x} \) is such that \( \Vert {\bf x}- A^{+}{\bf b}\Vert \le \epsilon \Vert A^{+}{\bf b}\Vert \) . This output can be viewed as a classical analogue to the output of quantum linear solvers. The complexity of our algorithm is \( \widetilde{O}(\kappa _F^6 \kappa ^2/\epsilon ^2) \) , where \( \kappa _F = \Vert A\Vert _F\Vert A^{+}\Vert \) and \( \kappa = \Vert A\Vert \Vert A^{+}\Vert \) . This improves the previous best algorithm [Gilyén, Song and Tang, arXiv:2009.07268] of complexity \( \widetilde{O}(\kappa _F^6 \kappa ^6/\epsilon ^4) \) . Our algorithm is based on the randomized Kaczmarz method, which is a particular case of stochastic gradient descent. We also find that when A is row sparse, this method already returns an approximate solution \( {\bf x} \) in time \( \widetilde{O}(\kappa _F^2) \) , while the best quantum algorithm known returns \( | {\bf x} \rangle \) in time \( \widetilde{O}(\kappa _F) \) when A is stored in the QRAM data structure. As a result, assuming access to QRAM and if A is row sparse, the speedup based on current quantum algorithms is quadratic.
We establish an improved classical algorithm for solving linear systems in a model analogous to the QRAM that is used by quantum linear solvers. Precisely, for the linear system ( A{\bf x}= {\bf b} ) , we show that there is a classical algorithm that outputs a data structure for ( {\bf x} ) allowing sampling and querying to the entries, where ( {\bf x} ) is such that ( \Vert {\bf x}- A^{+}{\bf b}\Vert \le \epsilon \Vert A^{+}{\bf b}\Vert ) . This output can be viewed as a classical analogue to the output of quantum linear solvers. The complexity of our algorithm is ( \widetilde{O}(\kappa _F^6 \kappa ^2/\epsilon ^2) ) , where ( \kappa _F = \Vert A\Vert _F\Vert A^{+}\Vert ) and ( \kappa = \Vert A\Vert \Vert A^{+}\Vert ) . This improves the previous best algorithm [Gilyén, Song and Tang, arXiv:2009.07268] of complexity ( \widetilde{O}(\kappa _F^6 \kappa ^6/\epsilon ^4) ) . Our algorithm is based on the randomized Kaczmarz method, which is a particular case of stochastic gradient descent. We also find that when A is row sparse, this method already returns an approximate solution ( {\bf x} ) in time ( \widetilde{O}(\kappa _F^2) ) , while the best quantum algorithm known returns ( | {\bf x} \rangle ) in time ( \widetilde{O}(\kappa _F) ) when A is stored in the QRAM data structure. As a result, assuming access to QRAM and if A is row sparse, the speedup based on current quantum algorithms is quadratic.
We propose fast and practical quantum-inspired classical algorithms for solving linear systems. Specifically, given sampling and query access to a matrix A∈Rm×n and a vector b∈Rm, we propose classical algorithms that produce a data structure for the solution x∈Rn of the linear system Ax=b with the ability to sample and query its entries. The resulting x satisfies ∥x−A+b∥≤ε∥A+b∥, where ∥⋅∥ is the spectral norm and A+ is the Moore-Penrose inverse of A. Our algorithm has time complexity O(κF4/κε2) in the general case, where κF=∥A∥F∥A+∥ and κ=∥A∥∥A+∥ are condition numbers. Compared to the prior state-of-the-art result [Shao and Montanaro, arXiv:2103.10309v2], our algorithm achieves a polynomial speedup in condition numbers. When A is s-sparse, our algorithm has complexity O(sκlog(1/ε)), matching the quantum lower bound for solving linear systems in κ and 1/ε up to poly-logarithmic factors [Harrow and Kothari]. When A is s-sparse and symmetric positive-definite, our algorithm has complexity O(sκlog(1/ε)). Technically, our main contribution is the application of the heavy ball momentum method to quantum-inspired classical algorithms for solving linear systems, where we propose two new methods with speedups: quantum-inspired Kaczmarz method with momentum and quantum-inspired coordinate descent method with momentum. Their analysis exploits careful decomposition of the momentum transition matrix and the application of novel spectral norm concentration bounds for independent random matrices. Finally, we also conduct numerical experiments for our algorithms on both synthetic and real-world datasets, and the experimental results support our theoretical claims.
We introduce a quantum linear system solving algorithm based on the Kaczmarz method, a widely used workhorse for large linear systems and least-squares problems that updates the solution by enforcing one equation at a time. Its simplicity and low memory cost make it a practical choice across data regression, tomographic reconstruction, and optimization. In contrast to many existing quantum linear solvers, our method does not rely on oracle access to query entries, relaxing a key practicality bottleneck. In particular, when the rank of the system of interest is sufficiently small and the rows of the matrix of interest admit an appropriate structure, we achieve circuit complexity O(ε1logm), where m is the number of variables and ε is the target precision, without dependence on the sparsity s, and could possibly be without explicit dependence on condition number κ. This shows a significant improvement over previous quantum linear solvers where the dependence on κ,s is at least linear. At the same time, when the rows have an arbitrary structure and have at most s nonzero entries, we obtain the circuit depth O(ε1logs) using extra O(s) ancilla qubits, so the depth grows only logarithmically with sparsity s. When the sparsity s grows as O(logm), then our method can achieve an exponential improvement with respect to circuit depth compared to existing quantum algorithms, while using (asymptotically) the same amount of qubits.
We give a classical algorithm for linear regression analogous to the quantum matrix inversion algorithm [Harrow, Hassidim, and Lloyd, Physical Review Letters'09] for low-rank matrices [Wossnig, Zhao, and Prakash, Physical Review Letters'18], when the input matrix A is stored in a data structure applicable for QRAM-based state preparation.Namely, suppose we are given an A∈Cm×n with minimum non-zero singular value σ which supports certain efficient ℓ2 -norm importance sampling queries, along with a b∈Cm . Then, for some x∈Cn satisfying ‖x–A+b‖≤ε‖A+b‖ , we can output a measurement of |x⟩ in the computational basis and output an entry of x with classical algorithms that run in O~(‖A‖F6‖A‖6σ12ε4) and O~(‖A‖F6‖A‖2σ8ε4) time, respectively. This improves on previous "quantum-inspired" algorithms in this line of research by at least a factor of ‖A‖16σ16ε2 [Chia, Gilyén, Li, Lin, Tang, and Wang, STOC'20]. As a consequence, we show that quantum computers can achieve at most a factor-of-12 speedup for linear regression in this QRAM data structure setting and related settings. Our work applies techniques from sketching algorithms and optimization to the quantum-inspired literature. Unlike earlier works, this is a promising avenue that could lead to feasible implementations of classical regression in a quantum-inspired settings, for comparison against future quantum computers.
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.
Quantum algorithms for linear algebra that access a matrix A through quantum random access memory (QRAM) prepare quantum states proportional to the solutions of linear systems and related problems. Dequantized classical algorithms, when given sampling and query access to A, return sampling and query access to an approximate solution. Both kinds of algorithms use a number of queries that is polynomial in the normalized Frobenius norm ρ=∥A∥F/∥A∥ and does not directly depend on the dimension. For linear systems at fixed condition number and accuracy, quantum algorithms use O(ρ) queries, whereas the best dequantized algorithms use O(ρ4). We prove that this quartic gap is tight in the worst case, up to a logarithmic factor. For every constant κ0>1, we construct dense linear systems with condition number at most κ0 for which sampling from the solution within a sufficiently small constant total variation distance requires Ω(ρ4/logρ) classical queries but only Θ(ρ) quantum queries. The same separation holds, for errors below smaller thresholds, for positive-definite systems, least squares, ridge regression, matrix powers and square roots, imaginary-time and real-time Hamiltonian evolution, and sampling from the top principal component. Our results therefore show that many quantum algorithms for linear algebra, achieve a near-quartic speedup in the worst case, over classical algorithms with sampling and query access. All of these classical lower bounds follow from the same framework, which is based on a lower bound for sampling from distributions that depend on a fixed set of Fourier coefficients of an unknown Boolean function.
We describe and analyze a simple algorithm for sampling from the solution x∗:=A+b to a linear system Ax=b. We assume access to a sampler which allows us to draw indices proportional to the squared row/column-norms of A. Our algorithm produces a compressed representation of some vector x for which ∥x∗−x∥<ε∥x∗∥ in O(κF4κ2/ε2) time, where κF:=∥A∥F∥A+∥ and κ:=∥A∥∥A+∥. The representation of x allows us to query entries of x in O(κF2) time and sample proportional to the square entries of x in O(κF4κ6) time, assuming access to a sampler which allows us to draw indices proportional to the squared entries of any given row of A. Our analysis, which is elementary, non-asymptotic, and fully self-contained, simplifies and clarifies several past analyses from literature including [Gilyén, Song, and Tang; 2022, 2023] and [Shao and Montanaro; 2022].