PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions

Ewin Tang

arXiv:1811.00414v3cs.DScs.IRcs.LGquant-ph

TL;DR

Quantum machine-learning algorithms are hard to compare with classical ones because they often rely on quantum-state inputs and outputs. The paper introduces classical sample and query access and applies it to principal component analysis and supervised clustering; for the considered algorithms, exponential speedups vanish under analogous input assumptions.

  • Problem

    Many quantum machine-learning algorithms use quantum-state inputs and outputs, leaving no comparable classical computation model for evaluating their speedups.

    Source: INTRODUCTION · p. 1

  • Method

    The paper introduces sample and query access, an ℓ2-norm sampling model, and uses it to construct classical analogues of quantum principal component analysis and supervised clustering.

    Source: INTRODUCTION · p. 1, THE DEQUANTIZATION MODEL · p. 2

  • Results

    For the considered algorithms, exponential speedups vanish when classical algorithms receive analogous input assumptions.

    Source: INTRODUCTION · p. 1

  • Takeaways & Limitations

    The paper concludes that these algorithms do not provide exponential speedups on classical data across a wide range of settings.

    Source: INTRODUCTION · p. 1

    The nearest-centroid parameter C(V,w) can be arbitrarily large in general; the stated quantum speedup applies when k is large and C(V,w) is small.

    Source: PRINCIPAL COMPONENT ANALYSIS · p. 4

Abstract

from arXiv · show

A central roadblock to analyzing quantum algorithms on quantum states is the lack of a comparable input model for classical algorithms. Inspired by recent work of the author [E. Tang, STOC'19], we introduce such a model, where we assume we can efficiently perform $\ell^2$-norm samples of input data, a natural analogue to quantum algorithms that assume efficient state preparation of classical data. Though this model produces less practical algorithms than the (stronger) standard model of classical computation, it captures versions of many of the features and nuances of quantum linear algebra algorithms. With this model, we describe classical analogues to Lloyd, Mohseni, and Rebentrost's quantum algorithms for principal component analysis [Nat. Phys. 10, 631 (2014)] and nearest-centroid clustering [arXiv:1307.0411]. Since they are only polynomially slower, these algorithms suggest that the exponential speedups of their quantum counterparts are simply an artifact of state preparation assumptions.

INTRODUCTION

Quantum machine-learning algorithms are difficult to compare with classical ones because they often take quantum states as input and output. The paper introduces sample and query access as a classical analogue to state preparation, then uses it to dequantize two quantum algorithms.

INTRODUCTION

  • The main comparison challenge is that most QML algorithms take quantum states as input and output quantum states, leaving no known analogous classical computation model for finding similar algorithms [8].Source: INTRODUCTION · p. 1
  • Matching quantum state-preparation assumptions with classical ℓ2-norm sampling assumptions motivates the comparison model.The paper presents this as a principle for comparing quantum and classical machine-learning algorithms.Source: INTRODUCTION · p. 1
  • The paper introduces sample and query (SQ) access and dequantizes quantum principal component analysis and supervised clustering with polynomial slowdown.The classical algorithms match the corresponding quantum bounds and runtime up to polynomial slowdown.Source: INTRODUCTION · p. 1

THE DEQUANTIZATION MODEL

  • SQ access lets an algorithm query vector entries and norms and sample entries according to the input state's computational-basis measurement distribution.For matrices, the model includes SQ access to rows and to a normalized matrix representation.Source: THE DEQUANTIZATION MODEL · p. 2
  • Typical classical-data state-preparation settings, including QRAM, sparse vectors, and close-to-uniform vectors, can provide efficient SQ access.The paper describes dequantization as replacing state-preparation access with SQ access while preserving similar guarantees up to polynomial slowdown.Source: THE DEQUANTIZATION MODEL · p. 2

NEAREST-CENTROID CLASSIFICATION

The paper dequantizes nearest-centroid clustering by estimating the distance from a data point to a cluster centroid. Its general classical algorithm has only quadratic slowdown, and the quantum protocol's sole speedup is quadratic.

NEAREST-CENTROID CLASSIFICATION

  • The classical nearest-centroid algorithm handles general input data with only quadratic slowdown, unlike earlier dequantizations restricted to sparse or close-to-uniform inputs.The target is estimating a data point's distance to a cluster centroid.Source: NEAREST-CENTROID CLASSIFICATION · p. 2
  • The dequantization estimates an inner product in place of the quantum swap test, and amplitude estimation gives the quantum protocol a quadratic speedup, but no more.The paper identifies amplitude amplification as the only speedup achieved by quantum nearest-centroid.Source: NEAREST-CENTROID CLASSIFICATION · p. 3
  • Given SQ access to V and u, the classical algorithm solves the centroid-distance problem to additive ε error with probability at least 1−δ.The theorem gives a runtime bound in terms of the SQ-access parameter and problem parameters, but the supplied passage truncates the expression.Source: NEAREST-CENTROID CLASSIFICATION · p. 3

PRINCIPAL COMPONENT ANALYSIS

The section dequantizes QPCA’s top-principal-component task using sample-and-query access and low-rank approximation. Its classical procedure estimates leading singular values and vectors, with rejection sampling handling access to matrix-vector products.

PRINCIPAL COMPONENT ANALYSIS

  • QPCA’s central task is producing quantum states for the top principal components of a low-rank dataset; here the target is the leading eigenpairs of A†A.For a mean-zero dataset, these correspond to its top principal components.Source: PRINCIPAL COMPONENT ANALYSIS · p. 3
  • A low-rank approximation reduces A to a smaller matrix W, whose singular value decomposition yields explicit estimates of large singular values and an implicit description of right singular vectors.The vectors are represented as S†Û*,i/σ̂_i, with SQ access to S inherited from A’s rows.Source: PRINCIPAL COMPONENT ANALYSIS · pp. 3–4
  • Rejection sampling simulates SQ access to Vw; its sampling cost depends on C(V,w), which is O(K) in this application but can be arbitrarily large in general.The authors note that quantum algorithms can gain a speedup when k is large and C(V,w) is small, as for some high-dimensional unitary operations.Source: PRINCIPAL COMPONENT ANALYSIS · p. 4
  • Theorem 8 gives estimates for the desired principal-component quantities from SQ access to A, under the stated parameter conditions.The passage also states that learning about v_i from copies of |v_i⟩ incurs an ε_v-dependent cost for quantum algorithms.Source: PRINCIPAL COMPONENT ANALYSIS · p. 4

DISCUSSION

The discussion positions SQ access as a weaker classical input model that can still support dequantizations of QML routines. It distinguishes these guarantees from ordinary classical sketching and connects the techniques to quantum simulation and later low-rank QML work.

DISCUSSION

  • SQ algorithms generalize to a weaker input model than typical classical sketching, so their provable guarantees need not imply better performance in usual RAM settings.The discussion gives the conversion from O(T)-time quantum-inspired algorithms to Õ(nnz + T)-time RAM algorithms, but not the converse.Source: DISCUSSION · p. 4
  • Frieze et al.’s low-rank approximation is singled out because it generalizes to SQ access, unlike classical techniques that require stronger data structures.The authors say it is, to their knowledge, the only classical-literature algorithm that naturally generalizes to SQ.Source: DISCUSSION · pp. 4–5
  • Van den Nest’s computationally tractable states correspond to SQ access for vectors, but the cited work lacks the low-rank approximation technique used here for PCA.The paper places its supervised-clustering techniques within that work’s scope while describing its PCA techniques as new to that line of work.Source: DISCUSSION · p. 5
  • Unlike this work’s approximate low-rank treatment on the full state, tensor-network methods often approximate exactly on a subset and prioritize practical performance for suitably low-rank inputs.The discussion says some dequantized algorithms might also be matched by tensor-network contraction when the input has low tensor rank.Source: DISCUSSION · p. 5
  • Later work is described as extending the SQ approach across low-rank QML, including a dequantization of singular value transformation when input is in QRAM.The cited follow-ups use fundamentally the same techniques.Source: DISCUSSION · p. 5

Supplemental Material for “Quantum principal component analysis only achieves an

The supplement describes settings in which state-preparation access to classical data also supplies sample-and-query access. It also marks a boundary: the conversion relies on classically available input entries.

MOTIVATING SAMPLE AND QUERY ACCESS

  • The conversion depends on classical access to every input entry; if data instead comes from a quantum system, the authors say they cannot obtain SQ access this way.For an efficient integration oracle, the supplement also gives O(T log n)-time SQ access, matching the stated quantum-setting result.Source: MOTIVATING SAMPLE AND QUERY ACCESS · p. 7
  • QRAM state preparation and Grover-Rudolph preparation from an integration oracle are presented as settings that also yield SQ access to the input.Grover-Rudolph preparation uses O(log(n)) applications of the integration oracle; SQ access takes O(T log n) time when integration takes O(T) time.Source: MOTIVATING SAMPLE AND QUERY ACCESS · p. 7
  • When input entries are classically available, measuring prepared states or querying entries can provide sample-and-query access, including when generic state preparation is feasible.The supplement notes that this route may apply even when a full QRAM algorithm is impractical because of its space and time overhead.Source: MOTIVATING SAMPLE AND QUERY ACCESS · p. 7

RELATION TO TENSOR NETWORKS

The paper contrasts its low-rank-state algorithms with tensor-network methods, which rely on different representation assumptions and approximation strategies. Its SQ model covers a broader set of low-rank states, with guarantees that do not depend on bond dimension; the appendix also supplies nearest-centroid proofs for completeness.

RELATION TO TENSOR NETWORKS

  • The classical analogues run independently of bond dimension, and their broader applicability comes from abstracting away representation details rather than outperforming tensor-network methods.The paper says the SQ model may cover regimes beyond tensor-network results, such as QPCA on matrix product states.Source: RELATION TO TENSOR NETWORKS · p. 8
  • The algorithms run efficiently on low-rank states, a set much broader than states efficiently represented by tensor networks.The paper attributes this breadth to the SQ model abstracting away state-representation difficulties.Source: RELATION TO TENSOR NETWORKS · p. 8
  • Unlike tensor-network methods’ repeated local low-rank approximations, the QPCA algorithm approximates only once, with low error for the density matrices considered.The paper says iterative approximation is heuristic and tensor-network methods generally lack guarantees on general inputs.Source: RELATION TO TENSOR NETWORKS · p. 8

DETAILS FOR NEAREST-CENTROID CLASSIFICATION

Proof of Proposition 3

The proposition gives an inner-product estimator using SQ access and a median-of-means procedure. Its guarantee accommodates approximate norm queries, while the accompanying discussion bounds the possible quantum speedup for this task.

Proof of Proposition 3

  • The procedure averages batches of samples and takes a component-wise median of the means to control estimation error.For exact norm access, each batch mean has variance at most ε²∥x∥²∥y∥²/9.Source: Proof of Proposition 3 · p. 8
  • The estimator achieves error (ε+ν+εν)∥x∥∥y∥ with probability at least 1−δ given SQν(x) and Q(y).Source: Proof of Proposition 3 · p. 8
  • Using SQ(y) instead of Q(y) improves the scaling by at most constant factors.Source: Proof of Proposition 3 · p. 9
  • Amplitude estimation provides a quadratic speedup for quantum inner-product estimation, but no more, by the unstructured-search lower bound.Source: Proof of Proposition 3 · p. 9

Proof of Theorem 4

The proof reduces nearest-centroid distance estimation to inner-product estimation under SQ access. The theorem states an additive-error, high-probability solution, and the proof rescales the error using the relevant norm identities.

Proof of Theorem 4

  • Theorem 4’s algorithm estimates the centroid distance to additive error ε with probability at least 1−δ under the stated SQ-access assumptions.The problem is to estimate the distance between u and a centroid formed from V.Source: Proof of Theorem 4 · p. 9
  • The proof rewrites the target as wM M†w† and estimates it as an inner product between flattened tensors using Proposition 3.The construction obtains SQ access to M and query access to w from the given data access.Source: Proof of Theorem 4 · p. 9
  • The proof uses ∥a∥_F=4 and ∥b∥=∥w∥²=Z, then rescales ε by 4Z to obtain the stated result.Source: Proof of Theorem 4 · p. 9

Proof of Theorem 6

The proof applies QPCA to estimate the leading singular values and vectors under a gap assumption, with runtime depending on state preparation and the target accuracy. The gap lets the algorithm identify individual singular vectors from their eigenvalue estimates.

Proof of Theorem 6

  • The task is to estimate the top k singular values and corresponding right singular vectors of A, given a lower bound σ on those singular values.The theorem assumes access to ∥A∥_F and copies of |A⟩ that take O(T) time to prepare.Source: Proof of Theorem 6 · p. 9
  • Given copies of |A⟩ preparable in O(T) time, the quantum algorithm outputs the desired estimates for Problem 5 in Õ(TK min(εσ, δ)^-3) time.The theorem's output comprises estimates of the leading singular values and singular vectors.Source: Proof of Theorem 6 · p. 9
  • QPCA samples eigenvectors with probability proportional to their eigenvalues, and eigenvalue estimates identify the leading vectors under the gap assumption.Because each target eigenvector has sampling probability at least σ²/∥A∥²_F, enough samples can recover all k target vectors and their eigenvalue estimates.Source: Proof of Theorem 6 · p. 10
  • The analysis targets individual singular vectors and relies on a gap; without low rank, distinguishing vectors may require εσ = O(1/n), eliminating the exponential speedup.The authors note that learning the top-k subspace may remain efficient without a gap, but restrict this result to individual vectors.Source: Proof of Theorem 6 · p. 10

Analysis of Low-Rank Approximation Algorithm

The low-rank approximation algorithm samples rows and columns to construct an implicit approximation to A. Its guarantees cover truncation, approximation error, singular-value accuracy, and near-orthonormal output vectors.

Analysis of Low-Rank Approximation Algorithm

  • The algorithm samples rows and columns to form a smaller matrix, computes its large singular vectors, and outputs an implicit low-rank approximation D = A V̂V̂†.The approximation is represented using sampled data and the computed singular vectors and singular values.Source: Analysis of Low-Rank Approximation… · p. 10
  • With probability at least 1 − δ, the approximation satisfies bounds on truncation, residual error, singular values, and closeness of its vectors to orthonormal columns.The proposition states these guarantees for the implicit description of D.Source: Analysis of Low-Rank Approximation… · p. 10
  • The guarantees mean ℓ is an appropriate truncation point, D is a low-rank approximation, its singular values are approximately correct, and its singular vectors are approximately orthonormal.These are additive-error guarantees, weaker than the relative-error bounds common in classical ML literature; the authors say this is inherent in the weaker SQ input assumptions, and quantum algorithms also achieve only additive-error bounds.Source: Analysis of Low-Rank Approximation… · p. 10
  • The proof largely adapts the earlier ModFKV result, with the algorithm's choice of ε as the stated difference.The proof invokes prior lemmas and a proposition for the separate guarantees.Source: Analysis of Low-Rank Approximation… · p. 10

Proof of Proposition 7

The proposition simulates sample-and-query access to Vw using access to V† and query access to w. Rejection sampling produces the correct output distribution, with its cost governed by C(V, w).

Proof of Proposition 7

  • Rejection sampling chooses an index weighted by |w_i|²∥V_*,i∥², then accepts an output coordinate with a probability that corrects the sampling distribution.Conditioned on success, the output coordinate is distributed as a measurement from |Vw⟩.Source: Proof of Proposition 7 · p. 11
  • Given SQ(V†) and Q(w), the procedure simulates SQν(Vw) with query time O(Tk) and sampling time O(Tk²C(V, w) log(1/δ)).C(V, w) = Σ_i ∥w_iV_*,i∥²/∥Vw∥².Source: Proof of Proposition 7 · p. 11
  • Each rejection-sampling attempt succeeds with probability (kC(V, w))^-1, so repeated attempts control the sampling cost and failure probability.The proof uses a Chernoff bound to establish the norm estimate's correctness.Source: Proof of Proposition 7 · p. 11

Proof of Theorem 8

The proof combines the low-rank approximation and matrix-vector access guarantees to construct estimates of the leading singular values and vectors. The gap assumption is used to show that the estimated vectors correspond individually to the target vectors.

Proof of Theorem 8

  • Algorithm 5 uses the low-rank approximation routine, then reconstructs each estimated singular vector from S†, the computed left singular vectors, and its singular value.It returns estimates of the first k singular values and SQ access to the corresponding vectors.Source: Proof of Theorem 8 · p. 11
  • The theorem states that Algorithm 5 outputs the desired estimates for Problem 5 from SQ(A) access.Its input includes εσ, εv, and δ in (0, 0.01).Source: Proof of Theorem 8 · p. 11
  • The proof combines Proposition 9's low-rank guarantees with Proposition 7's matrix-vector access simulation to establish the PCA guarantees.The individual-vector error requires a separate argument because the low-rank approximation alone controls the span, not each vector.Source: Proof of Theorem 8 · p. 11
  • Applying the low-rank approximation bound to each rank-r truncation, together with the gap assumption, shows each estimated vector is close to its corresponding singular vector.The proof argues that a deviation at the first differing vector would violate the bound for that rank.Source: Proof of Theorem 8 · pp. 11–12

Related papers

Loading 1811.00414v3…