Source-linked AI summary
Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning
Nai-Hui Chia, András Gilyén, Tongyang Li, Han-Hsuan Lin, Ewin Tang, Chunhao Wang
TL;DR
The paper addresses whether quantum linear-algebra methods, especially QSVT, provide exponential speedups under QRAM-style input assumptions. It develops a sampling-based classical framework that approximately reproduces their matrix arithmetic and applies it across quantum machine learning. The resulting algorithms provide evidence that QRAM-based QSVT lacks exponential speedups, while not excluding large polynomial advantages.
Problem
Quantum machine-learning algorithms rely on restrictive input assumptions, motivating the question of whether QSVT-based methods retain exponential speedups in the corresponding QRAM model.
Method
The paper defines oversampling and query access and uses approximate closure under matrix arithmetic and singular-value transformations to construct dimension-independent classical algorithms.
Results
The framework gives evidence against exponential speedups for QRAM-based QSVT and recovers or improves dequantizations across several quantum machine-learning tasks.
Takeaways & Limitations
Sampling and query access can serve as a classical analogue of block-encodings for bounded-Frobenius-norm matrices, extending quantum-inspired algorithms across applications.
Takeaways & Limitations
The framework does not rule out large polynomial quantum speedups, and one PCA protocol is dequantized only in the low-rank setting.
Abstract
from arXiv · showhide
We present an algorithmic framework for quantum-inspired classical algorithms on close-to-low-rank matrices, generalizing the series of results started by Tang's breakthrough quantum-inspired algorithm for recommendation systems [STOC'19]. Motivated by quantum linear algebra algorithms and the quantum singular value transformation (SVT) framework of Gilyén, Su, Low, and Wiebe [STOC'19], we develop classical algorithms for SVT that run in time independent of input dimension, under suitable quantum-inspired sampling assumptions. Our results give compelling evidence that in the corresponding QRAM data structure input model, quantum SVT does not yield exponential quantum speedups. Since the quantum SVT framework generalizes essentially all known techniques for quantum linear algebra, our results, combined with sampling lemmas from previous work, suffice to generalize all recent results about dequantizing quantum machine learning algorithms. In particular, our classical SVT framework recovers and often improves the dequantization results on recommendation systems, principal component analysis, supervised clustering, support vector machines, low-rank regression, and semidefinite program solving. We also give additional dequantization results on low-rank Hamiltonian simulation and discriminant analysis. Our improvements come from identifying the key feature of the quantum-inspired input model that is at the core of all prior quantum-inspired results: $\ell^2$-norm sampling can approximate matrix products in time independent of their dimension. We reduce all our main results to this fact, making our exposition concise, self-contained, and intuitive.
1 Introduction
The paper develops a sampling-based classical framework that approximately mirrors quantum linear-algebra operations, including QSVT, under QRAM-style input assumptions. It uses these tools to dequantize and extend quantum-inspired algorithms across several machine-learning and numerical tasks.
- Input model: The framework defines oversampling and query access as a classical analogue of quantum state-preparation assumptions, with improved closure properties.The model supports sampling entries according to squared magnitudes, querying entries, and obtaining ℓ2 norms.
- Matrix arithmetic: Approximately closed matrix arithmetic lets sampling and query access produce complex expressions without paying the linear time needed to explicitly compute them.The framework can chain these operations indefinitely up to controllable Frobenius-norm error.
- Implications for QSVT: The results give evidence against exponential speedups for QRAM-based QSVT, while leaving open the possibility of large polynomial quantum speedups.Classical runtimes are polynomially slower than corresponding quantum algorithms except in the ε parameter.
- Singular value transformation: Given SQ(A), the framework accesses an approximation of f(A†A) in time independent of the matrix dimensions for Lipschitz f with f(0)=0.This is the paper’s singular-value-transformation closure property.
- Applications: The framework recovers or improves dequantized algorithms for recommendation systems, PCA, supervised clustering, SVMs, matrix inversion, and semidefinite programming.It also provides new quantum-inspired algorithms for low-rank Hamiltonian simulation and discriminant analysis.
- Technical principle: Its central primitive is approximate matrix multiplication through importance or ℓ2-norm sampling, which can operate independently of input dimension.This perspective also yields dimension-independent access to useful low-rank-approximation outputs.
2 Preliminaries
The preliminaries establish matrix, norm, decomposition, and transformation notation, including singular-value and eigenvalue transforms and approximate isometries.
- Matrices use row, column, entry, concatenation, vectorization, Euclidean, Frobenius, and spectral-norm notation.
- An SVD writes A as UDV† with ordered nonnegative singular values, while Hermitian eigendecompositions permit negative diagonal entries.
- The rank-k approximation retains the first k singular components, and the pseudoinverse rescales nonzero singular components by their reciprocals.
- Singular value transformation applies f to singular values through an SVD, with f(0)=0 ensuring independence from the chosen decomposition.
- Eigenvalue transformation applies f to a Hermitian matrix’s eigenvalues; unlike singular-value transformation, it can distinguish eigenvalue signs.
- An α-approximate isometry satisfies V†V−I bounded by α and lies within α of an exact isometry with the same column space.
3 Sampling and query access oracles
The sampling-and-query model supplies efficient entry, norm, and ℓ2-norm sampling access, while oversampling enables approximate recovery through rejection sampling and supports arithmetic closure.
- Query access returns vector or matrix entries, while sampling and query access additionally samples indices by squared magnitudes and returns ℓ2 norms.
- Oversampling permits a distribution to dominate the target distribution pointwise, with factor ϕ measuring the sampling overhead.
- Rejection sampling converts oversampled access into target-distribution samples with acceptance probability 1/ϕ.
- Given SQϕ(v), target sampling succeeds with probability at least 1−δ in O(ϕ sqϕ(v) log(1/δ)) time, and the norm can be estimated multiplicatively.
- Linear combinations and outer products preserve sampling-and-query access with overhead determined by oversampling factors and input-access costs.
- A dynamic data structure supports matrix SQ(A) with q(A)=O(1), s(A)=O(log mn), and n(A)=O(1), after linear preprocessing for sparse input.
4 Matrix sketches
Matrix sketches reduce dimension by sampling rows according to norm-based distributions, while approximate multiplication and singular-value results provide reusable arithmetic primitives.
- An importance-sampling sketch S is formed by independently sampling rows according to row norms or ϕ-oversampled bounding row norms.
- Sketching preserves the Frobenius norm up to constant factors with probability at least 0.9 when the sketch has Ω(1/ϕ^2) rows.
- From SQϕ(A), sketches of SA and (SA)† retain oversampling and query access with factor at most 2ϕ when the sketch is sufficiently large.
- Subsampling gives an unbiased estimator X†S†SY for X†Y, with variance bounds controlling approximation error.
- Approximate matrix multiplication yields closure of oversampling and query access under products, and matrix-product bounds translate into singular-value approximations.
- When X=Y, the spectral-norm error bound improves from dependence on ∥X∥F^2 to dependence on ∥X∥∥X∥F.
5 Singular value transformation
The singular-value transformation framework approximates smooth functions of A†A from sampling-and-query access using a low-dimensional sketch decomposition, under Lipschitz and low-rank-related conditions.
- Given SQϕ(A) and a smooth f, the main primitive approximates f(A†A) by R†UR+f(0)I.
- Theorem 5.1 requires f and (f(x)−f(0))/x to be Lipschitz on a domain surrounding the spectrum of A†A.
- The construction sketches A to R=SA and C=SAT, then computes a function of the small matrix CC†.
- In a restricted dimension-independent setting, the assumptions bound rank and condition number through ∥A∥F/σ, while the function’s steepness is controlled by Γ.
- The resulting decomposition satisfies author-provided norm and approximation bounds with failure probability controlled by δ.
- A logarithmic spectral-norm factor cannot generally be removed because some Lipschitz functions are not operator Lipschitz.
6 Applying the framework to dequantizing QML algorithms
The framework recovers prior dequantization results across several quantum machine-learning applications and extends them to QSVT, Hamiltonian simulation, and discriminant analysis.
- The framework recovers dequantization results for recommendation systems, supervised clustering, principal component analysis, low-rank matrix inversion, support-vector machines, and low-rank semidefinite programs.
- It proposes new quantum-inspired algorithms for QSVT, Hamiltonian simulation, and discriminant analysis.
- Applications are presented in roughly chronological order, which also roughly follows their difficulty from easier to harder.
6.1 Dequantizing QSVT
The paper dequantizes quantum singular value transformation for close-to-low-rank matrices using sampling and query access, handling even and odd polynomial transformations. Under QRAM-compatible assumptions, the resulting classical procedure matches QSVT's dimension-independent dependence while differing in error dependence.
- The framework begins by dequantizing the quantum singular value transformation for close-to-low-rank matrices.
- For even polynomials, p(QV)(A) is represented as q(A†A); for odd polynomials, p(QV)(A) is represented as A · q(A†A).
- Theorem 6.2 assumes sampling and query access to A and A†, a normalized vector b, and a bounded degree-d polynomial with matching parity.
- In the QRAM input model, QSVT does not yield an exponential speedup, while the classical procedure is polynomially slower and has worse ε and δ dependence.
- The classical algorithm can query output entries, whereas the quantum algorithm cannot do so without paying at least a 1/ε factor.
6.2 Recommendation systems
The framework gives a sampling-based low-rank approximation for recommendation systems, recovering the target up to Frobenius error and enabling dimension-independent sampling and matrix-vector products.
- The framework yields a simpler and faster variant of Tang's recommendation-system dequantization.
- Recommendation reduces to sampling a good product for a user from incomplete preferences represented by a matrix A with sampling and query access.
- The approximation Aσ,η thresholds singular values around σ, retaining values above σ(1 +η), removing values below σ(1 −η), and interpolating between them.
- The algorithm rewrites the low-rank approximation as A · t(A†A), approximates the transformed factor, and samples from each resulting row.
- The sampling procedure is exact, so total-variation error arises only from the probability of failure.
- Without assumptions on A, the output satisfies ∥Â −A∥ ≲ε∥A∥F in dimension-independent time and supports sampling rows or products with vectors.
6.3 Supervised clustering
The supervised-clustering application converts centroid-distance estimation into an inner-product estimation problem and supplies a classical algorithm under sampling and query access.
- Supervised clustering assigns a new point to the cluster whose centroid is nearest by estimating its distance to each centroid.
- The centroid-distance expression is rewritten as the norm of a matrix-vector product, ∥wM∥2.
- The quantum input assumptions translate into sampling and query access to the data points.
- Problem 6.9 asks for approximating (wM)(wM)T to additive ε error with probability at least 1 −δ.
- A classical algorithm solves Problem 6.9 by expressing the target as an inner product and applying the sampling-based inner-product estimator.
- The quantum algorithm has a quadratically faster runtime, ignoring polylog(n, d) factors.
6.4 Principal component analysis
The framework solves low-rank PCA by estimating leading eigenvalues and constructing approximate eigenvectors through sampling-based singular-value transformations. Its runtime depends on conditioning and spectral-gap parameters, and it improves prior quantum-inspired PCA results.
- Scope: Exact dequantization of the full protocol is unavailable, but the low-rank setting covers the useful polylogarithmic-time application identified for quantum PCA.
- The task is to estimate the top k eigenvalues and eigenvectors of X†X from sampling and query access to X.
- Assumptions: The runtime must depend on condition-number and spectral-gap parameters to avoid degeneracy and enable spectral sampling.
- Results: The method improves significantly over prior quantum-inspired PCA work, while the quantum comparison is stated up to polylogarithmic factors.
- Method: The algorithm estimates eigenvalues from an importance-sampled submatrix whose singular values approximate those of X.
- Method: Smoothened step functions isolate each leading eigenspace, and the resulting rank-one decompositions provide approximate eigenvectors with sampling and query access.
6.5 Matrix inversion and principal component regression
The framework dequantizes low-rank matrix inversion and extends it to approximately low-rank matrices by applying thresholded inverse transformations on well-conditioned subspaces. This broadens prior strictly low-rank results while preserving sampling-based access to approximate solutions.
- The framework handles approximately low-rank matrices by computing a thresholded pseudoinverse on a well-conditioned subspace.
- Results: The resulting algorithm supports approximate inversion beyond strictly rank-k inputs, unlike prior work restricted to strict low rank.
- The inversion problem asks for sampling and query access to an approximate solution with error bounded relative to ∥A∥^-1∥b∥.
- Assumptions: The construction assumes access to sampled and queried matrix and vector data and uses condition, threshold, and gap parameters in its runtime.
- Method: The method represents the thresholded inverse as a function of A†A and approximates it through an RUR decomposition before applying it to b.
6.6 Support vector machines
The paper dequantizes a quantum support vector machine by reducing the required computation to its low-rank matrix inversion framework. The resulting guarantees use normalization assumptions shared with the quantum algorithm, with an alternative method for weaker normalization dependence.
- Method: The dequantization reduces the support vector machine computation to matrix inversion and then applies the inversion corollary.
- The support vector machine classifies labeled points by fitting a separating hyperplane with nonnegative slack variables.
- Assumptions: The algorithm solves the stated support vector machine problem under the assumption ∥F̂∥≤1.
- Method: The implementation estimates kernel entries by sampling row inner products and obtains sampling access to the resulting quantities.
- Comparison: The paper notes that a prior claimed dequantization gave no correctness or runtime bounds, and its correctness is unclear because its approximations incur significant errors.
- Limitations: A normalization issue can cause failure when X has too small Frobenius norm, motivating an alternative method based on computing F+.
6.7 Hamiltonian simulation
The framework develops sampling-based classical algorithms for Hamiltonian simulation, expressing the matrix exponential through smooth even and odd functions. It gives separate algorithms for low-rank and arbitrary Hamiltonians, with a smoothed variant for small singular values.
- Hamiltonian simulation seeks sampling and query access to an approximation of e^iHb for a Hermitian H and input state b.
- Results: The paper gives two fundamentally similar algorithms, one for low-rank H and one for arbitrary H.
- Method: The method decomposes a generic function into even and odd parts, then applies the singular-value transformation framework to each part.
- Method: For Hamiltonian simulation, the construction uses cosine and sinc functions whose approximations combine into a vector close to e^iHb.
- Assumptions: The low-rank result assumes a minimum singular value σ, while the arbitrary-H result applies under a separate error condition.
- Scope: For non-low-rank H, a modified construction smoothly thresholds away small singular values while retaining the zeroth- and first-order exponential terms.
6.8 Semidefinite program solving
The paper improves quantum-inspired semidefinite-program feasibility solving using matrix multiplicative weights and trace-estimation techniques. The resulting algorithm handles a more general problem and improves the runtime over prior work.
- Result: The algorithm solves SDP ε-feasibility with success probability at least 1 − δ while providing sampling and query access to a solution.It assumes F ≥ max_j∈[m] ||A^(j)||_F and F = Ω(1).
- Comparison: Unlike prior quantum-inspired SDP solving restricted to low-rank constraint matrices, the new result applies to a more general setting.Under the rank-at-most-r assumption, the paper relates F to √r for comparison with prior bounds.
- Method: Matrix multiplicative weights frames feasibility testing as a zero-sum game between proposing X and finding violated constraints.At each round, a violating constraint guides the next candidate solution.
- Method: The method estimates traces involving Gibbs-state matrices to execute the feasibility algorithm on implicitly defined inputs.The key estimates concern Tr[A^(i)H] and Tr(H), whose ratio determines constraint violations.
10 If no solution found, conclude that the SDP is infeasible and terminate the algorithm
The section develops trace-estimation machinery for Gibbs-state matrices used inside the SDP solver, combining approximate spectral decompositions with sampling-based matrix access. It also applies the broader framework to discriminant analysis.
- Trace estimation: An approximate eigendecomposition of H yields a diagonal representation whose eigenvalues support approximations to exponential matrix functions.The resulting trace approximations use perturbation bounds and trace-norm inequalities.
- Trace estimation: Trace estimates for Tr(A^(i)e^H) and Tr(e^H) provide the quantities needed to evaluate SDP constraints to the required precision.The construction approximates both the partition function and matrix-weighted traces.
- Implementation: The algorithm handles both small- and large-norm regimes, using direct computation when the matrix representation is sufficiently small and spectral methods otherwise.This split avoids applying the same approximation strategy outside its efficient regime.
- Discriminant analysis: For discriminant analysis, the framework constructs approximate eigenvalues and eigenvectors for the generalized scatter-matrix problem.The construction targets the relaxed problem obtained after truncating small eigenvalues.
- Discriminant analysis: The discriminant-analysis relaxation is not evaluated for whether it produces a meaningful output.The paper explicitly leaves that question beyond its scope.
7 More singular value transformation
The paper extends its sampling-based framework from even singular value transformations to generic SVT and eigenvalue transformations. These procedures produce compact approximations with dimension-independent runtime under low-rank and sampling assumptions.
- Generic SVT: The framework provides generic singular value transformation algorithms for matrices with sampling and query access to both A and A†.The transformed matrix is output through a CUR decomposition.
- Runtime: For relative error ε = O(ℓ||A||), the generic SVT runtime is independent of input dimension.This holds in the strictly low-rank or effectively truncated setting described by the paper.
- Method: The proof combines sketches, smooth spectral filtering, approximate eigendecomposition, and matrix-product approximation to construct the transformed output.The filter removes small eigenvalues before the remaining low-dimensional expression is diagonalized.
- Runtime: The framework also supplies explicit complexity expressions involving sampling, query, sketch, and matrix dimensions.These costs arise from producing sketches, querying entries, transforming singular values, and multiplying the resulting matrices.
- Eigenvalue transformation: The eigenvalue-transformation procedure outputs an approximate isometry and diagonal matrix whose entries approximate transformed eigenvalues.The diagonal approximation satisfies |D(i,i) + f(0) − f(λ_i)| ≤ ε.
A Proof sketch for Remark 6.4
The proof sketch shows how sampling and query access to A can be converted into approximate access to A†. It constructs a thresholded low-rank representation and uses approximate matrix products to obtain the needed access structure.
- Access conversion: The construction forms a thresholded approximation B satisfying ||B − A†|| ≤ ε||A||.A smooth step function filters singular values around ε||A||.
- Access conversion: The filtered representation is expressed through sampled factors and a small matrix, enabling sampling and query access to B and B†.The matrix is written as a sum of outer products whose components have sampling and query access.
- Error control: Approximate orthonormality and a lower bound on ||Av|| support querying entries of the constructed vectors and controlling the approximation error.The proof uses inner-product estimation to approximate Av entrywise.
- Access conversion: Row-norm sampling supplies an oversampling distribution for the auxiliary vector needed to complete the access conversion.The construction uses ˜u(i) := 2||A(i, ·)|| to obtain sampling access from SQ(A).
B Deferred proofs
The deferred proofs establish technical tools for approximate isometries, sampling-based matrix products, concentration, inner-product estimation, polynomial transformations, and matrix-function approximation. These lemmas support dimension-independent quantum-inspired computations under sampling access assumptions.
- Isometries: Approximate isometries can be replaced by exact isometries with the same column space while controlling operator-norm error.The construction uses a singular value decomposition and replaces the singular values with one.
- Sampling and concentration: Subsampling gives an unbiased estimator for X†Y, with concentration obtained by applying bounded-difference inequalities to the sampled indices.The proof treats the estimator as a function of independently sampled coordinates and bounds changes caused by modifying one coordinate.
- Sampling and concentration: ℓ2-sampling estimates inner products to additive error ε with failure probability at most δ using repeated sampling, averaging, medians, and a union bound.The resulting runtime is the number of samples multiplied by O(sq(u) + q(v)).
- Polynomial approximation: Polynomial bounds control transformed functions and derivatives on bounded intervals, supporting approximation arguments for singular-value transformations.The proof invokes Markov–Bernstein inequalities and Taylor expansions, with parity-specific treatment of the polynomial.
- Matrix-function approximation: The regression-related construction reduces inversion to approximating f(X†X), where f(λ) = 1/(λ + σ²), and can become dimension-independent under stated parameter conditions.The runtime is dimension-independent when γ^-1/2 is sufficiently large and ∥α∥ = Ω(γ∥y∥).
- Matrix-function approximation: Matrix perturbation and subsampling lemmas propagate approximation guarantees to output vectors and partition-function estimates.The proofs combine block-matrix inversion, approximate matrix functions, matrix-vector products, and perturbation bounds.