PaperlayerView exact revision on arXiv

Source-linked AI summary

Information-theoretic bounds on quantum advantage in machine learning

Hsin-Yuan Huang, Richard Kueng, John Preskill

arXiv:2101.02464v2quant-phcs.ITcs.LG

TL;DR

The paper studies how many uses of a possibly unknown quantum process are needed for classical and quantum ML models to predict experiment outcomes. It shows comparable query complexity for average-error prediction, but possible exponential quantum advantage for worst-case prediction, including Pauli-expectation estimation.

  • Problem

    The paper asks how classical and quantum ML models can approximate functions generated by physical processes while minimizing the number of process uses.

  • Method

    The paper compares classical models that measure each process use with quantum models that access the process coherently, using the number of process runs as the efficiency measure.

  • Results

    For average prediction error, classical ML matches quantum ML with at most a small polynomial query overhead; for worst-case error, quantum ML can achieve exponential advantage, using O(n) copies for all n-qubit Pauli expectations versus 2^Ω(n) classical copies.

  • Takeaways & Limitations

    Classical ML can be effective for average-case prediction, while coherent quantum measurements can provide exponential benefits for certain worst-case prediction tasks.

Abstract

from arXiv · show

We study the performance of classical and quantum machine learning (ML) models in predicting outcomes of physical experiments. The experiments depend on an input parameter $x$ and involve execution of a (possibly unknown) quantum process $\mathcal{E}$. Our figure of merit is the number of runs of $\mathcal{E}$ required to achieve a desired prediction performance. We consider classical ML models that perform a measurement and record the classical outcome after each run of $\mathcal{E}$, and quantum ML models that can access $\mathcal{E}$ coherently to acquire quantum data; the classical or quantum data is then used to predict outcomes of future experiments. We prove that for any input distribution $\mathcal{D}(x)$, a classical ML model can provide accurate predictions on average by accessing $\mathcal{E}$ a number of times comparable to the optimal quantum ML model. In contrast, for achieving accurate prediction on all inputs, we prove that exponential quantum advantage is possible. For example, to predict expectations of all Pauli observables in an $n$-qubit system $ρ$, classical ML models require $2^{Ω(n)}$ copies of $ρ$, but we present a quantum ML model using only $\mathcal{O}(n)$ copies. Our results clarify where quantum advantage is possible and highlight the potential for classical ML models to address challenging quantum problems in physics and chemistry.

I. INTRODUCTION

The paper studies when quantum machine learning can reduce the number of process runs needed to predict physical experiments. It finds comparable classical and quantum query complexity for average error, but possible exponential quantum advantage for worst-case prediction.

  • Learning problem: The framework predicts f(x) = tr(O E(|x⟩⟨x|)) for quantum experiments parameterized by a classical input x.Here E is an arbitrary possibly unknown CPTP map, O is a known observable, and the learned function h(x) should approximate f(x).
  • Applications: The settings model physical applications including quantum-chemistry reactions, molecular or material ground states, and neutral-atom simulators.New inputs represent previously unseen experimental parameters, such as chemicals, molecular descriptions, or laser intensities.
  • Learning problem: The comparison asks whether quantum ML needs fewer process uses than classical ML to achieve a specified prediction error.The metric counts runs of E during learning and disregards the runtime used to generate predictions.
  • Average-case prediction: For any input distribution, classical ML can achieve average prediction error comparable to quantum ML with at most a small polynomial-factor increase in process uses.Thus quantum ML has no exponential query advantage for small average prediction error, although computational-complexity advantages may still occur.
  • Worst-case prediction: For small worst-case prediction error, an exponential separation between classical and quantum process-use requirements is possible.The separation concerns accurately predicting f(x) for every input x rather than only on average.
  • Worst-case prediction: NQ = O(n) copies of an unknown n-qubit state suffice quantumly to predict all Pauli-observable expectation values, whereas classical ML requires NC = 2^Ω(n) copies.The classical lower bound holds even with arbitrary adaptive single-copy POVM measurements.

II. MACHINE LEARNING SETTINGS

The paper formalizes classical and quantum ML by contrasting measured classical training data with coherently stored quantum data. Both models learn during a query phase and use their stored data to predict future inputs.

  • General setup: The unknown process E is a CPTP map from n-qubit inputs to m-qubit outputs, while inputs are n-bit strings.The process may be any member of a specified set of CPTP maps, with arbitrary behavior apart from that membership.
  • Classical ML: Classical ML performs a POVM measurement after each queried experiment and stores the resulting pairs {(x_i, o_i)} in classical memory.A randomized algorithm selects inputs, and a second randomized algorithm constructs the prediction model from the training data.
  • Restricted classical ML: Restricted classical ML measures the target observable O directly, producing real outcomes with expectation tr(O E(|x_i⟩⟨x_i|)).This restriction contrasts with the general classical setting, which permits arbitrary POVM measurements.
  • Quantum ML: Quantum ML makes NQ coherent queries to E interleaved with quantum processing and stores the learned state ρE in quantum memory.A quantum computer later accesses ρE to produce predictions for new inputs.
  • Comparison: Quantum ML can process quantum data directly, whereas classical ML processes measurement outcomes, making the quantum setting strictly more powerful for some tasks.The paper identifies exponential quantum advantage as possible in such tasks.

III. AVERAGE-CASE PREDICTION ERROR

For average-case prediction under a fixed input distribution, the paper constructs a restricted classical model whose process-query cost is comparable to that of a quantum model.

  • Average-case prediction error: The average-case error is measured by averaging squared prediction errors over the input distribution D.The target quantity compares hC(x) with tr(OE(|x⟩⟨x|)).
  • Average-case prediction error: NC = O(mNQ/ϵ) experiments suffice for a restricted classical model to match the quantum model's small average-case prediction error.The guarantee holds with high probability under the theorem's stated assumptions.
  • Proof strategy: The proof covers the set of admissible CPTP maps with a maximal packing net and uses it to distinguish possible process-induced functions.Alice encodes a packing-net element into quantum data, which Bob uses to recover the corresponding message.
  • Classical construction: A restricted classical model samples inputs from D and measures the target observable O on each output state.The resulting outcomes estimate the expectation values used for prediction.
  • Average-case prediction error: The relation NC = O(mNQ/ϵ) is tight, with an appendix example achieving NC = Ω(mNQ/ϵ).Thus the theorem's polynomial overhead cannot generally be improved within this formulation.

IV. WORST-CASE PREDICTION ERROR

Worst-case prediction changes the comparison: exponential quantum advantage is possible for predicting every Pauli expectation value, with an efficient quantum model using logarithmic dependence on the number of observables.

  • Worst-case versus average-case: Exponential quantum advantage becomes possible when prediction must be accurate for every input rather than only on average.The setting requires accurate prediction of f(x) for all x ∈ {0, 1}^n.
  • Pauli expectation values: Predicting all 4^n Pauli expectation values in an unknown n-qubit state is the paper’s illustrative worst-case task.The input indexes one of the 4^n n-qubit Pauli operators, whose expectation value is predicted.
  • Quantum upper bound: The quantum procedure first estimates |tr(Pxρ)| and then determines its sign only when the magnitude is sufficiently large.It uses simultaneous measurements of Px ⊗ Px and a coherent majority vote across several copies for the sign.
  • Quantum upper bound: NQ = O(log(M/δ)/ϵ^4) copies suffice for estimating any M Pauli observables to error ϵ with probability at least 1 − δ.For all 4^n Pauli observables, the paper notes that this yields NQ = O(n) copies.
  • Classical lower bound: Classical ML requires exponentially many copies to predict all Pauli expectations with small error and constant success probability.The classical lower bound remains valid even when POVM measurements are chosen adaptively from previous outcomes.
  • Bounds summary: Table 2 compares achievable upper bounds with algorithm-independent lower bounds for worst-case prediction of all 4^n Pauli expectations.The classical upper bound can be achieved using classical shadows based on random Clifford measurements.

V. NUMERICAL EXPERIMENTS

Numerical experiments test worst-case prediction of all 4^n Pauli expectations for mixed and product n-qubit states. They show a clear exponential classical–quantum separation for mixed states but a much smaller separation for product states.

  • Experimental setup: The experiments evaluate prediction of all 4^n Pauli expectation values with small worst-case error for unknown n-qubit states.They use mixed states and product states as two underlying state classes.
  • State classes: Mixed states have the form ρ = (I + P)/2^n, with P a tensor product of n Pauli operators and rank 2^(n−1).These states are one of the two classes studied in the numerical experiments.
  • State classes: Product states are tensor products of single-qubit stabilizer states, chosen so the quantum ML model can be simulated classically at larger system sizes.Each single-qubit factor is one of six possible stabilizer states.
  • Results: Mixed states exhibit an exponential separation between the copies required by classical and quantum ML for predicting all Pauli expectations.The numerical experiment implements the best-known ML procedures.
  • Results: Product states show a much less pronounced, marginal separation between classical and quantum ML.Restricted classical ML gets one bit per copy, while arbitrary POVMs can provide up to n bits per copy.

VI. CONCLUSION AND OUTLOOK

The paper finds that quantum advantage depends on the prediction objective: classical and quantum ML require comparable process queries for average-case accuracy, whereas exponential quantum advantages can arise for worst-case accuracy. It concludes that classical ML remains promising for quantum-science applications, while further work is needed to identify practically useful quantum-advantage tasks.

  • Conclusion: Comparable process-query complexity limits quantum advantage when the objective is a specified average prediction error.This bound applies to any quantum ML model.
  • Outlook: Classical ML models using measurements after each process query can be surprisingly effective for average-case prediction.The authors contrast this with the greater implementation challenges of coherent quantum ML models.
  • Conclusion: Exponential quantum advantages are possible for problems requiring a specified worst-case prediction error.The paper interprets this as a separation between coherent and classical measurements.
  • Outlook: Further research should identify additional learning problems that allow substantial quantum advantage and point toward practical quantum-technology applications.The paper identifies this as an important future direction rather than an established application.
  • Paper organization: The paper supports its conclusions through theoretical query-complexity bounds, numerical experiments, and mathematical proofs across the main appendices.Appendix C treats average prediction errors, while Appendix D gives a stylized tightness example.

b. Proof strategy I: mutual information analysis

The first proof strategy converts a successful quantum predictor into a communication protocol and bounds how much information its queried channel copies can convey. Combining packing-net information requirements with Holevo’s theorem yields a lower bound on quantum query complexity, which is then compared with a classical upper bound.

  • Communication reduction: The proof encodes randomly selected packing-net functions as messages that a quantum learner must decode from its prediction model.Accurate prediction ensures perfect decoding with probability at least 2/3.
  • Communication reduction: Fano’s inequality lower-bounds the mutual information required to decode a message selected from the packing net.The required information depends on the packing-net cardinality.
  • Quantum information bound: Holevo’s theorem upper-bounds the accessible classical information obtained by measuring the quantum state produced by the learner.The argument applies data processing to the measurement outcome used for decoding.
  • Quantum information bound: The quantum computation’s Holevo information grows by at most a bounded amount per channel query, proved inductively over the learner’s sequence of operations.The induction uses entropy bounds, partial traces, and the fact that channel actions can be traced out in the relevant subsystem.
  • Conclusion: Combining the information lower and upper bounds produces a lower bound on the minimal quantum query complexity in terms of packing-net size.This is the central output of the mutual-information proof strategy.

c. Proof strategy II: polynomial method

The second proof strategy represents quantum-learning output probabilities as bounded-degree polynomials in channel parameters. A full-rank matrix argument then constrains the number of quantum queries, while complementary concentration analysis establishes the classical training-data scaling.

  • Scope: The polynomial proof is a weaker alternative whose stated applicability is restricted to m ≤ n.The authors include it for completeness and insight.
  • Rank argument: A matrix of mix-up probabilities between packing-net elements is shown to have full column rank through diagonal dominance.The matrix dimensions are determined by the packing-net cardinality.
  • Polynomial representation: Quantum-model answer probabilities become homogeneous polynomials of degree NQ in channel parameters and their conjugates.The channel is parametrized through a Kraus representation.
  • Rank argument: The full-rank condition yields a lower bound on quantum query complexity after rearrangement under the assumption n ≤ m.This connects the polynomial dimension to the number of distinguishable packing-net functions.
  • Classical concentration: The concentration proof separately controls ideal training error and measurement fluctuations before combining the resulting high-probability events.The statistical analysis distinguishes expectation values from single-shot measurement outcomes.
  • Classical concentration: N = Θ(log(|M_p4ϵ(Ff)|)/ϵ) suffices for the classical concentration analysis, improving on the usual 1/ϵ^2 dependence.The improvement follows because low-error functions have small variance, while larger fluctuations for high-error functions remain diagnostically useful.

d. Prediction error for functions in the maximal packing net

The packing-net analysis shows how the restricted classical learner selects a low-error hypothesis with high probability. Maximal packing nets provide both separated representatives and nearby approximations, enabling simultaneous control of low- and high-error candidates.

  • Conclusion: Together, the events bound the prediction error of the empirically selected restricted classical model.Low-error representatives remain competitive while high-error functions are excluded by their larger empirical errors.
  • Packing-net geometry: A maximal packing net is also a covering net, so every target function has a sufficiently close representative in the net.The covering property follows from maximality: otherwise another function could be added.
  • Event 1: low-error candidate: Event 1 establishes a packing-net function with small prediction error and an empirical training error below the selection threshold.The argument uses the covering property of a maximal packing net.
  • Event 2: high-error candidates: Event 2 ensures that every packing-net function with large prediction error has an empirical training error above the threshold.This prevents highly inaccurate candidates from being selected by empirical-error minimization.
  • High-probability guarantee: The two events hold simultaneously with probability at least 1 − 2δ after a union-bound argument.The stated training-data condition is N ≥ 38 log(2|M_p4ϵ(Ff)|/δ)/ϵ.

e. Prediction error for functions produced by restricted classical ML

The restricted classical ML model selects a packing-net function by minimizing empirical training error, and its average prediction error is bounded with high probability. This supports a classical construction whose query complexity can be compared directly with quantum lower bounds.

  • N ≥ 38 log(4 |M p 4ϵ(Ff)| /δ)/ϵ training examples ensure the required concentration relations with probability 1 −δ.The relations are used to compare empirical training errors across packing-net elements.
  • The empirical minimizer f∗ cannot have prediction error at least 12ϵ, because that would contradict its strictly smaller empirical training error.The contradiction argument excludes packing-net functions with sufficiently large prediction error.
  • Proposition 1 guarantees E_x∼D |f∗(x) − fE(x)|^2 < 12ϵ with probability at least 1 −δ.The guarantee applies to the packing-net element minimizing empirical training error.
  • A quantum model achieving the stated average error with probability at least 2/3 must access E at least NQ times.This is the quantum query lower-bound side of the comparison.
  • The proposition also supplies a restricted classical model achieving the corresponding average error for any E ∈ F using NC accesses.Together, the classical upper bound and quantum lower bound establish the comparison used in Theorem 1.

Appendix D: Examples saturating the maximum information-theoretic advantage

The appendix constructs a learning problem in which one coherent query reveals a hidden bit-string label, while restricted classical ML requires linearly many queries in the output size for small average error. It also identifies this construction as a near-maximum separation and leaves unrestricted classical ML tightness open.

  • Lower bound on the classical query complexity: NC = Ω(m/ϵ) classical training examples are required for small average prediction error with high probability.The lower bound follows by using accurate predictions to recover the hidden label and bounding the information in binary outcomes.
  • The construction yields the largest possible separation targeted here, while whether unrestricted classical ML matches this separation remains open.The stated separation is a small polynomial factor in this appendix’s formulation.
  • Learning problem formulation: 2^n CPTP maps are indexed by hidden labels a ∈ {0,1}^n, with n = m−1 and an (n+1)-qubit observable O = Z ⊗ I^⊗n.The observable measures the first output qubit in the Z basis.
  • Upper bound on the quantum query complexity: NQ = 1 suffices to extract a with certainty by querying the map once, discarding the first qubit, and measuring the remaining n qubits computationally.The remaining qubits encode the hidden label directly after the query.
  • Upper bound on the quantum query complexity: NQ = 1 achieves zero prediction error for every input distribution and is optimal because zero queries reveal no information about the underlying map.Once a is known, the closed-form function predicts future values exactly.
  • The example targets small worst-case prediction error, contrasting with the average-prediction setting analyzed elsewhere.The appendix introduces it as an example where exponential quantum advantage is possible.

2. Sample complexity of a quantum ML algorithm

The quantum algorithm estimates many Pauli expectations by separating magnitude estimation from sign estimation. Bell measurements provide magnitudes from pairs of copies, while sequential measurements on quantum memory recover signs for appreciable expectations.

  • O(log(100 × 4^n)/ϵ^4) = O(n/ϵ^4) copies suffice to accurately predict all 4^n Pauli expectation values.Each channel access supplies one copy of the unknown state ρ.
  • Theorem 4 produces estimates p̂_i satisfying |p̂_i − tr(P_iρ)| ≤ ϵ simultaneously for M Pauli operators with probability at least 1 −δ.The procedure consumes copies of the unknown state through POVM measurements.
  • Two-block memory procedure: The protocol stores Bell-measurement data classically for magnitude estimates and retains N2 quantum copies for sign estimation.This division lets the quantum memory focus on Pauli operators whose expectations are not close to zero.
  • Magnitude estimation: Bell-basis measurements estimate |tr(Pρ)|^2, allowing the algorithm to recover the absolute value of each Pauli expectation efficiently.For one qubit and for n-qubit tensor products, Bell outcomes encode the squared expectation magnitude.
  • Magnitude estimation: N1 = Θ(log(1/δ)/ϵ^4) repetitions suffice to estimate a Pauli expectation’s absolute value with high probability.The estimate is obtained from repeated two-copy Bell measurements.
  • Sign estimation: N2 = Θ(log(M/δ)/ϵ^2) copies suffice for sequentially recovering the signs of M Pauli expectations whose magnitudes exceed ϵ.A quantum union bound controls the probability that all sequential sign measurements are correct.

c. Sample complexity analysis

The full protocol first estimates all Pauli magnitudes, then measures signs only when magnitudes are sufficiently large, combining both estimates into uniformly accurate predictions. Implementation can exploit commuting groups among the relevant observables.

  • The protocol uses union-bound-controlled estimates of all Pauli magnitudes before deciding which signs require quantum measurements.Magnitude estimation is followed by sign estimation only for operators exceeding the threshold 2ϵ/3.
  • For small expectation values, the protocol can omit sign measurements without significantly affecting prediction accuracy.Only Pauli observables with comparatively large absolute expectations receive sign measurements.
  • With probability at least 1 −δ, the magnitude and sign events hold together and yield accurate estimates for every tested Pauli expectation.The final estimate combines the measured sign with the estimated magnitude, or uses zero when the magnitude is small.
  • Implementation considerations: Bell-basis magnitude measurements are relatively accessible on current devices, whereas sign measurements can be difficult on near-term hardware.The sign procedure is applied selectively to reduce this implementation burden.
  • Implementation considerations: Large Pauli expectations can often be partitioned into a few mutually commuting sets because anticommuting observables cannot both have large expectations.Commuting sets can be measured in shared bases, reducing the number of measurement settings.

3. Sample complexity lower bound for restricted classical ML algorithms

The paper establishes exponential lower bounds for classical learning of Pauli expectation values, first for restricted measurements and then for non-adaptive arbitrary POVMs. These bounds contrast with quantum models that can access the state coherently.

  • Restricted classical ML algorithms: N ≥ (1/4)2^n = Ω(2^n) queries are necessary for learning point functions with worst-case error below 1/2 and success probability at least 2/3.The lower bound follows by reducing the classical learning task to identifying an unknown point function.
  • Restricted classical ML algorithms: N ≥ (1/4)4^n = Ω(4^n) samples are required to predict all n-qubit Pauli expectation values with the restricted classical model.The reduction encodes inputs and Pauli labels as bit strings of size 2n, yielding the stronger exponential bound.
  • Non-adaptive arbitrary POVMs: Ω(n2^n) copies are necessary for non-adaptive arbitrary POVM measurements when predicting all n-qubit Pauli observables.Classical shadows with random Clifford measurements achieve the matching upper bound O(n2^n).
  • Adaptive measurements: Adaptive single-copy measurements also require at least Ω(2^(n/3)) copies, although the paper states that this bound is not yet tight.Each adaptive POVM may depend on previous outcomes, but the exponential lower bound still holds.

a. Non-adaptive measurements

For arbitrary POVMs, the paper proves exponential classical sample-complexity lower bounds for predicting all Pauli expectations, while general entangled quantum measurements require only linearly many copies. The adaptive-measurement bound is exponential but explicitly not tight.

  • a. Non-adaptive measurements: Ω(n2^n) copies are necessary for non-adaptive single-copy POVMs to predict all Pauli expectation values with small worst-case error.The argument reduces prediction to distinguishing encoded Pauli states and bounds the information obtained from each measurement.
  • b. Adaptive measurements: Predicting all Pauli expectations distinguishes among 4^n possible states, reducing the learning problem to a two-hypothesis discrimination task.The completely mixed state and a randomly selected Pauli-encoded state induce distinguishable outcome distributions once the prediction error is sufficiently small.
  • b. Adaptive measurements: TV(p1, p2) ≤ 2N/(2^n + 1)^(1/3) remains small until N is exponentially large in n.Here p1 and p2 are the joint outcome distributions under the completely mixed state and a randomly chosen encoded state.
  • General entangled measurements: N = Ω(n) copies suffice and are necessary for quantum ML models using general entangled measurements on N copies of ρ.The lower bound matches the sample complexity of the quantum ML model considered in the paper.
Loading 2101.02464v2…