PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum-inspired algorithms in practice

Juan Miguel Arrazola, Alain Delgado, Bhaskar Roy Bardhan, Seth Lloyd

arXiv:1905.10415v3quant-phcs.DS

TL;DR

Quantum-inspired algorithms promised exponential asymptotic speedups, but their large polynomial overhead left their practical usefulness uncertain. The paper analyzes bottlenecks, implements the algorithms, and benchmarks them on controlled and practical problems. It finds faster-than-bound runtimes and useful performance only for very large, low-rank, well-conditioned inputs, with errors worsening as rank and condition number increase.

  • Problem

    The paper asks whether pessimistic complexity bounds reflect proof techniques or fundamental limits, and how quantum-inspired algorithms perform in practice.

  • Method

    The authors theoretically analyze bottlenecks, implement the algorithms, and benchmark them on artificial matrices and portfolio-optimization and recommendation-system problems.

  • Results

    Implemented runtimes are significantly faster than the proven bounds suggest, while approximation errors grow noticeably as matrix rank and condition number increase.

  • Takeaways & Limitations

    Quantum-inspired algorithms perform well only for extremely large-dimensional inputs with very low rank and condition number.

  • Takeaways & Limitations

    Their practical advantage is restricted to stringent input regimes, and it remains unclear whether datasets with those properties commonly occur in practice.

Abstract

from arXiv · show

We study the practical performance of quantum-inspired algorithms for recommendation systems and linear systems of equations. These algorithms were shown to have an exponential asymptotic speedup compared to previously known classical methods for problems involving low-rank matrices, but with complexity bounds that exhibit a hefty polynomial overhead compared to quantum algorithms. This raised the question of whether these methods were actually useful in practice. We conduct a theoretical analysis aimed at identifying their computational bottlenecks, then implement and benchmark the algorithms on a variety of problems, including applications to portfolio optimization and movie recommendations. On the one hand, our analysis reveals that the performance of these algorithms is better than the theoretical complexity bounds would suggest. On the other hand, their performance as seen in our implementation degrades noticeably as the rank and condition number of the input matrix are increased. Overall, our results indicate that quantum-inspired algorithms can perform well in practice provided that stringent conditions are met: low rank, low condition number, and very large dimension of the input matrix. By contrast, practical datasets are often sparse and high-rank, precisely the type that can be handled by quantum algorithms.

1 Introduction

Quantum-inspired classical algorithms promise sublinear linear-algebra runtimes, but their large polynomial complexity overhead raises questions about practical usefulness. This paper analyzes, implements, and benchmarks these methods to identify practical bottlenecks and favorable regimes.

  • Motivation: The broader motivation is that quantum algorithms and classical methods continually reshape the boundary of computational efficiency.The paper places quantum-inspired algorithms within an ongoing exchange of ideas between classical and quantum computing.
  • Motivation: Theoretical bounds suggest potentially prohibitive runtimes, raising whether they reflect proof artifacts or fundamental algorithmic limits.The stated bounds scale steeply with condition number, rank, matrix norm, and precision for linear systems, and with rank and precision for recommendation systems.
  • Approach: The study combines theoretical bottleneck analysis with implementations and benchmarks on controlled random matrices and practical portfolio-optimization and MovieLens problems.The experiments vary dimension, rank, and condition number on artificial inputs before testing real-world applications.
  • Main finding: Quantum-inspired algorithms can produce good approximations in reasonable times for very large-dimensional problems when input matrices have small rank and condition number.This is the paper’s main reported favorable regime.

2 Quantum-inspired algorithms for linear algebra

Quantum-inspired linear-algebra algorithms combine approximate SVD, coefficient estimation, and solution-vector sampling, using length-square access to reduce dependence on matrix dimension. Their practical benefits arise from compressing large matrices into smaller sampled problems, but coefficient estimation and approximation accuracy impose strong rank, conditioning, and sample-complexity constraints.

  • Sampling access: The algorithm assumes data access supporting length-square sampling, which preferentially samples high-norm rows and large entries within rows.A suitable data structure can support sampling in time logarithmic in dimension.
  • Algorithmic framework: Quantum-inspired algorithms replace direct coefficient and solution-vector computation with Monte Carlo estimation and rejection sampling, reducing dimension dependence from O(kn) to polylogarithmic scaling.These steps are the source of the asymptotic speedup after approximate SVD.
  • Approximate SVD: FKV samples and renormalizes rows and columns to construct a smaller matrix whose SVD approximates the singular values and vectors of the original input.The sampled matrix can have dimensions independent of the original matrix dimensions, subject to the low-rank approximation requirements.
  • Approximate SVD: FKV reduces the expensive SVD from an m × n matrix to an r × c matrix, with savings when r and c are much smaller than m and n.The reduced computation costs O(min{r^2c, rc^2}) rather than the naive full-matrix SVD cost O(min{m^2n, mn^2}).
  • Coefficient estimation: Coefficient estimation can lose its desired polylogarithmic complexity when inner-product geometry is unfavorable, although low-rank, well-conditioned matrices can permit good estimates.The paper notes that worst-case inner products cannot generally be approximated in sublinear time.
  • Practical bottlenecks: For k = κ = κβ = 100, coefficient estimation requires about 10^16 samples at error ϵ = 10^-2, and more samples improve precision but not errors inherited from inaccurate FKV singular data.Rejection sampling itself adds an O(rk) inner-product overhead and is usually comparatively inexpensive.

3 Numerical benchmarking

Numerical benchmarks show that quantum-inspired algorithms can outperform direct calculations in very large, low-rank, well-conditioned settings, but their accuracy and practical advantage deteriorate as rank, condition number, or dataset realism increases.

  • 3.2 High-dimensional problems: Very low rank and condition number yielded good estimates on extremely high-dimensional problems, with runtimes far below those suggested by the theoretical complexity bound.For k = κ = κβ = 10, the bound suggests about 10^22 operations, inconsistent with observed runtimes; estimate quality nevertheless worsens as rank and condition number increase.
  • 3.3 Random matrices: Approximation errors for random matrices decreased as 1/√r and increased linearly with both matrix rank and condition number.At k = 5, the solution-vector error was 8.7%; errors reached ηx ≥100% for κ ≥100.
  • 3.3 Random matrices: The approximate SVD was orders-of-magnitude faster than direct calculation for a 40,000 × 20,000 matrix with rank 5 and condition number 5.Constructing length-square distributions and estimating coefficients accounted for most overhead, although distributions could in principle be built while generating matrix data.
  • 3.4 Portfolio optimization: Portfolio and recommendation benchmarks produced substantial solution-vector errors, including ηx = 0.74 and ηx = 0.71, while coefficient estimation again dominated runtime.For recommendations, the first ten singular values had ησ = 0.06, but reconstructed-matrix and coefficient errors were 0.32, 0.66, and 0.58.
  • 3.5 Movie recommendations: On moderately sized real-world datasets, the quantum-inspired algorithms were slower and less accurate than exact diagonalization, implying that speedups require datasets too large for exact methods.The FKV approximation complexity scales as O(1/ε6) in the analyzed setting, compatible with the theoretical error dependence.
  • 3.3 Random matrices: Coefficient estimation dominated several runtimes, including high-dimensional low-rank problems, despite having smaller complexity exponents than the headline theoretical bounds.The observed linear dependence of error on rank and condition number supports coefficient estimation as a major error source in these regimes.

4 Conclusion

Quantum-inspired algorithms can run faster in practice than their theoretical bounds suggest, but their practical advantages require extremely large dimensions together with very low rank and condition number.

  • Quantum-inspired algorithms run significantly faster in implementation than their proven complexity bounds suggest.This cautions against using the asymptotic bounds alone to predict practical performance.
  • Performance degrades as rank and condition number increase, limiting practical usefulness to matrices with very low values of both.
  • Sampling-based coefficient estimation adds polynomial costs in rank, condition number, and estimation error, so it outperforms direct computation only at extremely large dimensions.
  • The O(k6/ε6) scaling for approximate SVD follows from the matrix Chernoff bound and prior error bounds, suggesting these exponents are fundamental rather than proof artifacts.
  • Quantum algorithms remain suitable for full-rank problems, whereas practical datasets are often sparse and high-rank; large condition numbers challenge all techniques.

A Worst-case hardness of coefficient estimation

The paper shows that coefficient estimation cannot generally be performed in sublinear time by reducing estimation to an NP-hard Ising-model partition-function problem.

  • The hardness construction encodes an Ising-model partition function into an inner product whose computation is as difficult as the original partition function.
  • The reduction represents any sum Z = Σ_i w_i as an inner product Z = ⟨y, z⟩, enabling hardness of estimating Z to transfer to a coefficient λ = ⟨x, y⟩.
  • Because approximating the general Ising partition function is NP-hard, the exponential time hypothesis implies a worst-case lower bound of 2^δm = O(n) time for coefficient estimation.

B Formulas for high-dimensional problems

The derivation expresses sampled matrix quantities through known entries and basis transformations, showing that every row has the same norm because rows contain identical elements in different positions.

  • The row-norm derivation introduces z′ = z ⊕ y and a shifted basis defined by ẽ(z′) = e(z′ ⊕ y).
  • All rows of the high-dimensional matrices have equal norm because their elements are identical up to position permutations.The resulting norm does not depend on the row label y.
  • The entries of matrix C are written using the vector a containing all possible values of the matrix entries a_y,z.
  • The sampled random variable has an average equal to the inner product ⟨v^(ℓ), A^T b⟩.

C Complementary results for random matrices

For random matrices, approximate SVD and coefficient-estimation errors worsen substantially with rank and condition number, especially for reconstructed pseudoinverses and estimated coefficients.

  • The random-matrix benchmarks use controlled low-rank Gaussian matrices generated by QR-orthogonalized factors with prescribed condition numbers.The largest singular value is sampled from [1, 500], the smallest is set by σ_min = σ_max/κ, and intermediate values follow a specified singular-value law.
  • Errors in the reconstructed pseudoinverse scale linearly with rank and exceed 45% at k = 100.Singular-value errors are not strongly influenced by rank, whereas singular-vector errors become apparent in reconstructed matrices.
  • Errors in the reconstructed pseudoinverse grow linearly with condition number and exceed 100% already for κ > 100.Singular-value and reconstructed-matrix errors show almost no dependence on condition number, but singular-vector errors propagate through factors of roughly 1/σℓ.
  • Coefficient-estimation error exceeds 100% for k > 20 and rises rapidly with condition number even at k = 5.The error depends weakly on the number of sampled rows and columns but worsens with rank and condition number.

D Singular values and coefficients for portfolio optimization and recommendation systems

The paper evaluates singular values and coefficient estimates for portfolio optimization and movie recommendation matrices, using the first ten singular components in both applications.

  • The portfolio and movie-recommendation experiments compare the first ten singular values with exact and estimated coefficients.Figure 8 covers portfolio optimization on S&P 500 data, while Figure 9 covers MovieLens 100K recommendations.
Loading 1905.10415v3…