We describe and analyze a simple algorithm for sampling from the solution $\mathbf{x}^* := \mathbf{A}^+\mathbf{b}$ to a linear system $\mathbf{A}\mathbf{x} = \mathbf{b}$. We assume access to a sampler which allows us to draw indices proportional to the squared row/column-norms of $\mathbf{A}$. Our algorithm produces a compressed representation of some vector $\mathbf{x}$ for which $\|\mathbf{x}^* - \mathbf{x}\| < \varepsilon \|\mathbf{x}^* \|$ in $\widetilde{O}(κ_{\mathsf{F}}^4 κ^2 / \varepsilon^2)$ time, where $κ_{\mathsf{F}} := \|\mathbf{A}\|_{\mathsf{F}}\|\mathbf{A}^{+}\|$ and $κ:= \|\mathbf{A}\|\|\mathbf{A}^{+}\|$. The representation of $\mathbf{x}$ allows us to query entries of $\mathbf{x}$ in $\widetilde{O}(κ_{\mathsf{F}}^2)$ time and sample proportional to the square entries of $\mathbf{x}$ in $\widetilde{O}(κ_{\mathsf{F}}^4 κ^6)$ time, assuming access to a sampler which allows us to draw indices proportional to the squared entries of any given row of $\mathbf{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].
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].
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 Ax=b , we show that there is a classical algorithm that outputs a data structure for x allowing sampling and querying to the entries, where x is such that ∥x−A+b∥≤ϵ∥A+b∥ . This output can be viewed as a classical analogue to the output of quantum linear solvers. The complexity of our algorithm is O(κF6κ2/ϵ2) , where κF=∥A∥F∥A+∥ and κ=∥A∥∥A+∥ . This improves the previous best algorithm [Gilyén, Song and Tang, arXiv:2009.07268] of complexity O(κF6κ6/ϵ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 x in time O(κF2) , while the best quantum algorithm known returns ∣x⟩ in time O(κ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.
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.
We present two efficient classical analogues of the quantum matrix inversion algorithm [16] for low-rank matrices. Inspired by recent work of Tang [27], assuming length-square sampling access to input data, we implement the pseudoinverse of a low-rank matrix allowing us to sample from the solution to the problem Ax = b using fast sampling techniques. We construct implicit descriptions of the pseudo-inverse by finding approximate singular value decomposition of A via subsampling, then inverting the singular values. In principle, our approaches can also be used to apply any desired “smooth” function to the singular values. Since many quantum algorithms can be expressed as a singular value transformation problem [15], our results indicate that more low-rank quantum algorithms can be effectively “dequantised” into classical length-square sampling algorithms.
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.
We present classical sublinear-time algorithms for solving low-rank linear systems of equations. Our algorithms are inspired by the HHL quantum algorithm for solving linear systems and the recent breakthrough by Tang of dequantizing the quantum algorithm for recommendation systems. Let A∈Cm×n be a rank-k matrix, and b∈Cm be a vector. We present two algorithms: a "sampling" algorithm that provides a sample from A−1b and a "query" algorithm that outputs an estimate of an entry of A−1b, where A−1 denotes the Moore-Penrose pseudo-inverse. Both of our algorithms have query and time complexity O(poly(k,κ,∥A∥F,1/ε)polylog(m,n)), where κ is the condition number of A and ε is the precision parameter. Note that the algorithms we consider are sublinear time, so they cannot write and read the whole matrix or vectors. In this paper, we assume that A and b come with well-known low-overhead data structures such that entries of A and b can be sampled according to some natural probability distributions. Alternatively, when A is positive semidefinite, our algorithms can be adapted so that the sampling assumption on b is not required.