PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum advantage in learning from experiments

Hsin-Yuan Huang, Michael Broughton, Jordan Cotler, Sitan Chen, Jerry Li, Masoud Mohseni, Hartmut Neven, Ryan Babbush, Richard Kueng, John Preskill, Jarrod R. McClean

arXiv:2112.00778v1quant-phcs.ITcs.LG

TL;DR

The paper asks whether quantum memories and processors can improve learning from physical experiments beyond conventional measurement followed by classical processing. It proves exponential experiment savings across state, principal-component, and dynamics-learning tasks, and demonstrates substantial advantages on noisy superconducting hardware.

  • Problem

    Conventional experiments measure each physical-system copy before classical processing, motivating whether quantum data storage and processing can reduce the experiments required for learning.

  • Method

    The paper proves exponential separations using learning-tree and distinguishing-task frameworks, then evaluates state and dynamics learning with quantum-enhanced experiments.

  • Results

    The paper reports exponential quantum advantages for predicting incompatible observables, quantum principal component analysis, and learning quantum processes and dynamics.

  • Takeaways & Limitations

    Quantum-enhanced learning can achieve these advantages with bounded processing, including protocols that use two copies of a state, while remaining effective in demonstrated noisy experiments.

Abstract

from arXiv · show

Quantum technology has the potential to revolutionize how we acquire and process experimental data to learn about the physical world. An experimental setup that transduces data from a physical system to a stable quantum memory, and processes that data using a quantum computer, could have significant advantages over conventional experiments in which the physical system is measured and the outcomes are processed using a classical computer. We prove that, in various tasks, quantum machines can learn from exponentially fewer experiments than those required in conventional experiments. The exponential advantage holds in predicting properties of physical systems, performing quantum principal component analysis on noisy states, and learning approximate models of physical dynamics. In some tasks, the quantum processing needed to achieve the exponential advantage can be modest; for example, one can simultaneously learn about many noncommuting observables by processing only two copies of the system. Conducting experiments with up to 40 superconducting qubits and 1300 quantum gates, we demonstrate that a substantial quantum advantage can be realized using today's relatively noisy quantum processors. Our results highlight how quantum technology can enable powerful new strategies to learn about nature.

Supplementary information

The supplementary information develops the paper’s theoretical framework, experimental methods, and demonstrations for learning states and dynamics with quantum-enhanced experiments.

  • Supplementary information: The supplementary material covers experimental details, quantum-information background, proofs of exponential advantage, and performance characterization.Its sections include learning incompatible observables, quantum principal component analysis, and polynomial-time quantum processes.
  • Mathematical framework: The mathematical framework represents classical algorithms as decision trees and analyzes distinguishing tasks, bounded quantum memories, and noise.These components support the paper’s proofs of conventional lower bounds and quantum-enhanced advantages.
  • Experimental platform: The experiments use a Google Sycamore processor with up to 53 superconducting transmon qubits, varying the working system from 4 to 40 qubits.Qubit subsets were selected to maximize performance and reduce connectivity-related overhead.
  • Experimental platform: The unknown states and dynamics are implemented directly on the processor, emulating physical data collection while retaining imperfect experimental conditions.This setup tests the proposed learning pipeline without requiring an external physical sensing system.

A.2. Experiments on learning physical states

The state-learning experiments compare conventional single-copy measurements with quantum-enhanced Bell measurements on pairs of copies, using Sycamore hardware and neural-network prediction.

  • Unknown-state preparation: The unknown states are unentangled states ρ = 2^-n(I + αP), with unknown Pauli operator P and α ∈ {−0.95, 0.95}.They are generated as ensembles of product states with strong non-local classical correlations.
  • Conventional experiments: Conventional experiments use randomized Pauli measurements and classical shadow tomography to estimate expectation values from separate copies of ρ.The randomized measurements sample X, Y, or Z independently on each qubit before computational-basis readout.
  • Quantum-enhanced experiments: Quantum-enhanced experiments perform an entangling Bell measurement across two copies of ρ stored in system and memory qubits.Each experiment produces a 2n-bit classical string for downstream prediction.
  • Data analysis: The quantum-enhanced data are processed by a supervised gated recurrent neural network trained on noiseless simulations and applied to noisy experimental data.The model receives Bell-measurement bitstrings and the two queried Pauli strings.

A.3. Experiments on learning physical dynamics

The dynamics experiments test whether unsupervised machine learning can distinguish general unitary circuits from time-reversal-symmetric circuits using conventional or quantum-enhanced data.

  • Circuit families: The experiments generate random 1D and 2D quantum circuits, half general unitary and half time-reversal symmetric.Time-reversal-symmetric circuits use real orthogonal single-qubit gates and specially constructed two-qubit gates.
  • Conventional experiments: Conventional experiments evolve |0^n⟩ under the dynamics and measure the output in the Y basis.The choice exploits the vanishing expectation of purely imaginary observables for outputs of time-reversal-symmetric evolution.
  • Quantum-enhanced experiments: Quantum-enhanced experiments prepare system–memory Bell states, apply the unknown dynamics twice with an intermediate swap, and measure each pair in the Bell basis.Each experiment yields a 2n-bit string.
  • Unsupervised learning: The unsupervised model forms feature vectors from bitstring statistics and uses a learned one-dimensional representation to classify the two circuit classes.A two-dimensional representation additionally reveals structure related to evolution-depth parity.
  • Experimental results: The quantum-enhanced strategy shows a substantial accuracy advantage over conventional experiments in both physical experiments and noiseless simulations.The comparison is reported for distinguishing general unitary dynamics from time-reversal-symmetric dynamics.

A.5. Performance and characterization data

The characterization data describe Sycamore’s preparation, measurement, gate, and process-learning context, including the classical learning-tree framework and device error sources.

  • Unsupervised dynamics results: Supplementary Figure 3 represents distinct physical processes as points and separates time-reversal-symmetric from general dynamics by color and marker shape.Quantum-enhanced data reveal the symmetry pattern, whereas conventional data do not.
  • Unsupervised dynamics results: Supplementary Figure 4 plots classification accuracy against experiment count for conventional and quantum-enhanced settings, using physical experiments and noiseless simulations.The task classifies 100 general and 100 time-reversal-symmetric circuits at each system size.
  • Device characterization: Learning quantum dynamics is limited by both measurement errors and two-qubit gate errors, with typical two-qubit gate errors around 0.01 to 0.05.The circuits are more complex than the state-learning experiments.
  • Quantum processes: A quantum process is a completely positive, trace-preserving map that sends density matrices to density matrices and generalizes unitary evolution.It can be represented through unitary evolution on a larger system followed by tracing out an environment.
  • Learning-tree framework: The classical learning procedure is represented as a directed rooted tree whose depth equals the number of experiments.Distinct outgoing measurement outcomes lead to distinct successor nodes when the classical memory retains full information.

C.2. Many-versus-one distinguishing tasks

The many-versus-one framework lower-bounds classical experiments by reducing learning to distinguishing one null state or channel from many alternatives. Decision-tree memory and leaf-distribution total variation quantify how experiments improve distinguishability.

  • A classical learning protocol is represented as a decision tree whose depth equals the number of experiments and whose leaves encode final memory states.
  • The null hypothesis selects one state or channel X_0, while the alternative contains every element of 𝒳∖{X_0}.
  • The lower-bound question is whether a classical algorithm can distinguish the alternative hypothesis from the null hypothesis.
  • Each state or process induces a leaf probability distribution because experiment outcomes, and therefore memory transitions, depend on the unknown system.
  • The success probability requires a sufficiently large total variation distance between null and alternative leaf distributions, which yields a lower bound on experiment count T.

C.3. Many-versus-many distinguishing task

The many-versus-many framework distinguishes two hypotheses, each containing many possible states or channels, and extends the analysis to partially revealed information and noisy experiments. Noise cannot weaken classical lower bounds.

  • Hypotheses A and B are random elements of disjoint subsets 𝒜 and ℬ of the admissible states or channels 𝒳.
  • Classical learning trees bound the distinguishability of A and B through the total variation distance between their induced leaf distributions.
  • Partially revealing information about the underlying state or process makes the distinguishing task easier, but may still leave the null and alternative conditionally balanced.
  • The partially revealed setting produces a weaker experiment lower bound because the revealed information improves prediction accuracy.
  • Noise on input states, measurements, or processes can be absorbed into modified classical learning trees, so existing classical lower bounds remain valid.
  • The framework underlies exponential separations for learning physical systems and dynamics, extending prior work beyond polynomial separations and related tomography strategies.

D.1. Exponential advantage in predicting absolute value of a single observable

For a task predicting |tr(Oρ)| when both an n-qubit state and observable are unknown, quantum-enhanced experiments achieve a constant-copy upper bound while conventional experiments require exponentially many copies.

  • O(n log(M)/ϵ^4) copies suffice to predict M arbitrary observables with quantum memory, including exponentially many observables using polynomially many copies.
  • The separation instance mixes the maximally mixed state with states ρ=(I+0.9sP)/2^n, where P is an unknown nonidentity n-qubit Pauli observable.
  • The states in this instance contain no quantum entanglement, yet still yield an exponential-versus-constant separation.
  • The exact state family with coefficient 1, ρ=(I+sP)/2^n, presents a technical difficulty whose fundamental status remains unclear.
  • The task asks the learner to predict |tr(Oρ)| after learning about the unknown state ρ and observable O.
  • O(1) copies suffice for quantum-enhanced experiments to achieve additive error 0.25 with probability at least 0.8.
  • Ω(2^n) copies are necessary for conventional experiments to achieve additive error 0.25 with probability at least 0.8.

D.2. A constant upper bound for quantum-enhanced experiments

The quantum-enhanced protocol uses two-copy entangling Bell measurements to estimate absolute Pauli expectation values. Their outcome statistics equal squared expectation values, enabling a constant-copy guarantee for the separation instance.

  • The protocol separates learning, where entangled measurements are performed, from prediction, where the desired properties are estimated.
  • Each round measures corresponding qubits from two copies of ρ in the Bell basis, producing outcomes S_k for k=1,…,n.
  • The collected measurement data use 2^nN_Q classical bits, and the estimator can be computed in time O(nN_Q).
  • For a single-qubit Pauli σ, the Bell outcome expectation equals tr((σ⊗σ)(ρ⊗ρ))=|tr(σρ)|^2.
  • For an n-qubit Pauli observable O, the tensor product of Bell outcomes is an eigenstate of O⊗O with eigenvalue ±1.
  • The entangling Bell measurement therefore estimates |tr(Oρ)| for every observable in the separation instance.
  • N_Q=Θ(log(1/δ)/ϵ^2) measurement rounds provide an accurate estimate with probability at least 1−δ.
  • N_Q=O(1) rounds estimate |tr(Oρ)| to error 0.25 with probability at least 0.8, establishing the constant quantum upper bound.

D.3. An exponential lower bound for conventional experiments

The proof reduces conventional learning to a partially revealed many-versus-one distinguishing problem, then bounds the information available from classical experiment records. This yields an exponential lower bound on conventional experiments.

  • Reduction to distinguishing: The proof reduces the learning task to a partially-revealed many-versus-one distinguishing task.The subsequent argument bounds the total variation distance between the resulting leaf-probability distributions.
  • Distinguishing task: The null hypothesis uses the maximally mixed state and a uniformly random nonidentity Pauli observable.Under this hypothesis, the observable is sampled independently from the state.
  • Distinguishing task: The alternative hypothesis correlates a state polarized by 0.9 along a random Pauli operator with that same observable.The sign s is sampled uniformly from {±1}.
  • Reduction to distinguishing: A predictor estimating |tr(Oρ)| to 0.25 error would distinguish the null and alternative hypotheses with success probability at least 1 − δ.The two hypotheses produce target absolute values 0 and 0.9, respectively.
  • Lower bound: The resulting lower bound shows that conventional experiments require exponentially many measurements for success probability at least 0.8.This conclusion follows after setting δ = 0.2.

D.4. An exponential lower bound for comparing absolute values

This section analyzes a task that compares the absolute values of two Pauli observables on an unknown state. Quantum-enhanced strategies achieve the task with logarithmically many experiments, whereas conventional strategies require an exponential number.

  • Task definition: The task asks the learner to classify which of two distinct observables has the larger absolute expectation value.The observables are randomly ordered, and success means correctly distinguishing the two possible inequalities.
  • Quantum-enhanced upper bound: Quantum-enhanced strategies achieve classification accuracy at least 1 − δ using only O(log(1/δ)) experiments.The strategy uses the procedure described in Appendix D.2.
  • Conventional lower bound: Conventional strategies require at least the theorem’s stated number of experiments to reach accuracy 1 − δ.The theorem establishes the exponential lower bound for this comparison task.
  • Proof strategy: The proof upper-bounds conventional classification accuracy through total variation distance between distributions over the algorithm’s final memory leaf.It applies a distinguishing argument to the two possible observable assignments.
  • Proof conclusion: Combining the total-variation upper and lower bounds yields the desired conventional sample lower bound stated in Theorem 7.The final algebraic combination appears after the separate bounds are established.

E. Performing quantum principal component analysis

Quantum principal component analysis uses copies of a mixed state to access its leading eigenvector and estimate an observable on that component. Under a constant spectral-gap assumption, quantum-enhanced experiments use O(1) copies while conventional experiments require Ω(2^(n/2)) copies for the stated prediction tasks.

  • Task definition: Quantum PCA targets the leading eigenvector of an unknown mixed state and predicts the expectation of a fixed observable on that eigenvector.The leading eigenvalue is assumed to exceed all other eigenvalues by a constant factor independent of n.
  • Quantum PCA procedure: The quantum PCA protocol approximates conditional evolution under ρ, measures an eigenvalue, and prepares the corresponding eigenstate for observable measurement.Quantum Fourier analysis of the auxiliary register enables eigenvalue readout and eigenstate preparation.
  • Quantum-enhanced upper bound: A constant number of repetitions estimates the leading-eigenvector observable to constant accuracy when the largest eigenvalue and spectral separation are constant.The procedure prepares the top eigenstate with sufficient probability and fidelity under the theorem’s assumptions.
  • Theorem 8: O(1) copies suffice for quantum-enhanced prediction of ⟨φ|Z1|φ⟩ to 0.25 error with probability at least 0.8.This is the upper bound in Theorem 8.
  • Theorem 8: Ω(2^(n/2)) copies are required conventionally for the same 0.25-error prediction with probability at least 0.8.The lower bound applies to algorithms accessing ρ only through conventional experiments.
  • Near-term quantum PCA: For a related near-term PCA quantity, quantum-enhanced estimation also uses O(1) copies while conventional estimation requires Ω(2^(n/2)) copies.The quantity is tr(Z1ρ^2)/tr(ρ^2), under the theorem’s constant spectral-separation condition.

E.1. An exponential lower bound for conventional experiments

The conventional setting requires exponentially many experiments for quantum principal component analysis and related distinguishing tasks. This lower bound also extends to efficiently generated pseudorandom states under cryptographic assumptions.

  • Conventional lower bound: Distinguishing the two hypotheses yields lower bounds for both quantum principal component analysis theorems.The hypotheses differ in their principal components and in predictions of a Z1 observable, including a 0.25-error, 0.8-success criterion.
  • Conventional lower bound: Ω(2^n/2) experiments are required for the conventional lower bound established in Theorem 8.The proof reduces the task to a many-versus-many distinguishing problem and bounds the total variation distance.
  • Conventional lower bound: The construction using Haar-random states is not realistic because preparing such states requires circuit depth exponential in n.The authors therefore cannot prepare the corresponding hard states in realistic circumstances.
  • Pseudorandomness: Pseudorandom states provide a computational alternative that is plausibly indistinguishable from Haar-random states for polynomial-time quantum algorithms.The construction relies on the unproven but widely believed existence of quantum-secure one-way functions.
  • Pseudorandomness: Any polynomial-time conventional algorithm with binary output cannot distinguish the corresponding pseudorandom-state hypotheses, while the quantum-enhanced advantage is not strictly exponential in this setting.Theorem 10 supplies the indistinguishability result, and the paper states that its consequence holds for arbitrary polynomial-time quantum learning algorithms versus conventional ones.

F.2. Rigorous statements

The paper gives rigorous process-learning bounds: quantum-enhanced experiments learn approximate quantum processes with polynomially many accesses, whereas conventional experiments may require exponentially many.

  • Polynomial upper bound: A quantum-enhanced learner uses at most Õ(poly(n) log(1/δ)/ε^4) accesses to learn an approximate quantum process.The guarantee holds with probability at least 1−δ, with Õ hiding factors logarithmic in 1/ε.
  • Exponential lower bound: An exponential lower bound applies to conventional learning of a process that always generates the specified hard state.Any conventional algorithm meeting the approximate-model condition must use at least Ω(2^n) accesses to the process.
  • Process construction: The proof illustration represents process learning as selecting a close element from a covering net using quantum data stored in quantum memory.The net covers polynomial-time quantum processes, and quantum hypothesis selection identifies the approximate physical process.
  • Process construction: The process construction uses O(n) two-qubit gates and always outputs a state of the specified form, regardless of its input state.The construction prepares the maximally mixed or Pauli-biased state using ancillary and system qubits.
  • Exponential lower bound: Ω(2^n) accesses are required because an approximate process model would predict an observable of the generated state to 0.25 error.The trace-norm guarantee implies the required observable prediction, which invokes the state-learning lower bound.

F.3. Proof of polynomial upper bound in Theorem 11

Theorem 11 is proved by discretizing polynomial-time quantum processes with a covering net, collecting outputs on sampled inputs, and applying quantum hypothesis selection.

  • Covering-net construction: An ε-covering net contains a nearby representative for every process in the considered process space.The process space is specified by n-qubit inputs, m ancillary qubits, and p two-qubit gates.
  • Covering-net construction: The covering net is built by approximating each two-qubit gate and composing the approximations with a per-gate error ε′/p.The analysis uses the diamond norm, a telescoping sum, and trace-norm contractivity under quantum channels.
  • Hypothesis selection: The learner samples Nin input states and obtains Nout copies of each true process output for every candidate process in the net.All resulting output states are stored in quantum memory before hypothesis selection.
  • Error analysis: Hoeffding’s inequality and a union bound control the empirical input-output error simultaneously across the covering net.The required number of sampled inputs scales as Ω(log(1/δ′)/ε^2) before accounting for the net size.
  • Hypothesis selection: Quantum hypothesis selection returns a net element whose product output state is close to the true product state.The selection theorem uses copies of the observed product state and provides a trace-distance approximation with probability at least 1−δ.
  • Error analysis: The constant-confidence protocol uses Õ(p^4/ε^4) accesses to the process, and repetition increases confidence to general δ.The general-confidence construction repeats the protocol Θ(log(1/δ)) times and clusters the resulting candidates.

G.1. Background and statement of results

The section contrasts classical-only learning protocols with bounded quantum-memory protocols and formalizes the latter using an adaptive learning tree. The framework tracks classical measurement transcripts alongside unnormalized quantum-memory states across experiments.

  • Background: Classical protocols discard each post-measurement quantum state, retaining only classical POVM outcomes that can adapt later measurements.
  • Background: With n+k qubit registers, k qubits remain available as quantum memory while arbitrary classical data may be stored and processed externally.
  • Background: Prior work established an Ω(2^((n−k)/3)) copy lower bound, but exponential gate complexity prevented realizing its memory advantage on quantum devices.
  • Task 3: Task 3 asks the learner to estimate |tr(Oρ)| after receiving T copies of an unknown state and learning the revealed observable O only afterward.
  • Learning tree framework: The learning-tree representation assigns each node a measurement-outcome transcript and a k-qubit unnormalized memory state, with adaptive POVMs defining child nodes.
  • Learning tree framework: Alternating quantum processes and POVMs can be rewritten as a single POVM, while later measurements adapt to the complete prior outcome transcript.

G.3. Hardness result for small quantum memories

This section proves that estimating a revealed observable remains sample-hard when quantum memory is substantially smaller than the n-qubit input. The proof bounds how much bounded-memory learning trees can distinguish the relevant states.

  • Hardness theorem: Theorem 13 proves that any algorithm with n+k qubit registers needs Ω(2^((n−k)/3)) copies of ρ to determine |tr(Oρ)| with probability at least 2/3.
  • Hardness theorem: The task distinguishes the maximally mixed state I/2^n from states (I+P)/2^n, where P is a random nonidentity Pauli string.
  • Good and bad Paulis: Good Paulis correspond to states remaining hard to distinguish from I/2^n along a learning-tree path, whereas bad Paulis reveal too much information.
  • Good and bad Paulis: For any learning-tree edge, at most 2^(-(n−k)/3)·(4^n−1) Paulis are bad, limiting distinguishability accumulated along a path.
  • Proof conclusion: If the final distinguishing advantage is Ω(1), the accumulated bound forces T≥Ω(2^((n−k)/3)) copies.
Loading 2112.00778v1…