PaperlayerView exact revision on arXiv

Source-linked AI summary

Exponential separations between learning with and without quantum memory

Sitan Chen, Jordan Cotler, Hsin-Yuan Huang, Jerry Li

arXiv:2111.05881v2quant-phcs.CCcs.ITcs.LG

TL;DR

The paper addresses whether quantum memory provides an inherent advantage for learning quantum systems and dynamics. It develops flexible lower-bound frameworks and establishes exponential separations, while identifying an open gap between lower and upper bounds in one setting.

  • Problem

    Quantum learning algorithms with and without external quantum memory can have different data requirements, motivating rigorous separations between these algorithmic models.

  • Method

    The paper develops flexible mathematical frameworks for proving lower bounds against learning algorithms without quantum memory.

  • Results

    The results establish learning problems where quantum-memory algorithms require O(n) bits of quantum memory while memoryless algorithms require Ω(2^n) copies.

  • Takeaways & Limitations

    The bounds are already noticeable at tens of qubits and suggest that quantum computers with fewer than one hundred qubits could assist experiments beyond conventional memoryless protocols.

  • Takeaways & Limitations

    For one upper-bound result, a gap between the lower and upper bounds remains an open question.

Abstract

from arXiv · show

We study the power of quantum memory for learning properties of quantum systems and dynamics, which is of great importance in physics and chemistry. Many state-of-the-art learning algorithms require access to an additional external quantum memory. While such a quantum memory is not required a priori, in many cases, algorithms that do not utilize quantum memory require much more data than those which do. We show that this trade-off is inherent in a wide range of learning problems. Our results include the following: (1) We show that to perform shadow tomography on an $n$-qubit state rho with $M$ observables, any algorithm without quantum memory requires $Ω(\min(M, 2^n))$ samples of rho in the worst case. Up to logarithmic factors, this matches the upper bound of [HKP20] and completely resolves an open question in [Aar18, AR19]. (2) We establish exponential separations between algorithms with and without quantum memory for purity testing, distinguishing scrambling and depolarizing evolutions, as well as uncovering symmetry in physical dynamics. Our separations improve and generalize prior work of [ACQ21] by allowing for a broader class of algorithms without quantum memory. (3) We give the first tradeoff between quantum memory and sample complexity. We prove that to estimate absolute values of all $n$-qubit Pauli observables, algorithms with $k < n$ qubits of quantum memory require at least $Ω(2^{(n-k)/3})$ samples, but there is an algorithm using $n$-qubit quantum memory which only requires $O(n)$ samples. The separations we show are sufficiently large and could already be evident, for instance, with tens of qubits. This provides a concrete path towards demonstrating real-world advantage for learning algorithms with quantum memory.

1 Introduction

The paper develops flexible lower-bound techniques showing that external quantum memory can yield exponential learning advantages across quantum systems and dynamics. It resolves shadow-tomography questions, establishes separations for several tasks, and gives a quantitative memory–sample tradeoff.

  • Learning models: Quantum-memory algorithms retain and jointly process quantum data, whereas memoryless algorithms measure each experiment and process only classical outcomes.The two models abstract future quantum-assisted experiments and conventional experimental platforms, respectively.
  • Main separation: Exponential separations arise because some problems require O(n) quantum-memory bits but Ω(2^n) copies without quantum memory.The paper states that these gaps are already noticeable at the scale of tens of qubits.
  • Learning physical systems: Shadow tomography without quantum memory requires Ω(min(M, 2^n)) samples in the worst case, nearly matching the best known upper bound.This resolves the previously open sample-complexity question up to logarithmic factors.
  • Learning physical systems: Predicting all Pauli expectation values without quantum memory requires Ω(2^n) copies, tightening a prior, substantially looser lower bound.The paper emphasizes that the new proof is much simpler than the earlier approach.
  • Learning physical systems: Purity testing without external quantum memory requires Ω(2^(n/2)) samples, matching an unentangled-measurement upper bound up to constant factors.The task distinguishes a pure state from the maximally mixed state.
  • Smooth tradeoffs for learning with quantum memory: With k qubits of quantum memory, predicting absolute Pauli expectations requires Ω(2^((n-k)/3)) copies, while n-qubit memory permits O(n) copies.The lower bound establishes a smooth tradeoff between available quantum memory and sample complexity.
  • Learning quantum dynamics: For quantum dynamics, the paper removes prior restrictions on ancilla qubits and proves exponential separations for general algorithms with and without quantum memory.This extends and strengthens earlier lower bounds for learning physical processes.

2 Technical Overview

The technical overview reduces lower bounds for adaptive, memoryless learning algorithms to comparing outcome distributions under a null hypothesis and a mixture of alternatives. It represents adaptivity with trees and develops edge-based, path-based, and bounded-memory analyses for controlling total variation and likelihood ratios.

  • Lower-bound framework: Le Cam’s two-point method frames the lower bounds as distinguishing a simple null hypothesis from a mixture of alternatives.The analysis seeks to show that outcome distributions under the two scenarios remain close when the sample count is small.
  • Tree representation: Adaptive experiments are represented by rooted trees whose nodes encode prior outcomes and whose leaves induce the distributions being compared.The choice of experiment at each node may depend on all earlier measurement outcomes.
  • Analysis techniques: Edge-based analysis bounds information gained on individual edges, while path-based analysis uses multilinear structure and higher moments across entire paths.The two approaches apply in different regimes: edge-based analysis controls per-edge discrepancies, whereas path-based analysis handles settings requiring higher-moment information.
  • Edge-based analysis: For shadow tomography, average edge discrepancies are converted through convexity and one-sided likelihood-ratio bounds into total-variation lower bounds.The framework introduces a quantity measuring the relevant discrepancy for a collection of observables and applies the argument to general observables using Haar-random choices.
  • Edge-based analysis: One-sided likelihood-ratio control is necessary because small average edge discrepancies do not prevent discrepancies from compounding along individual paths.A direct average absolute-difference bound could yield only a T = Ω(n/ε) lower bound in the illustrated computational-basis example.
  • Bounded quantum memory: With k-qubit memory, nodes carry 2^k × 2^k positive-semidefinite memory states and edges act as completely positive maps, requiring pruning rather than the earlier convexity argument.The pruning argument uses Markov’s inequality to identify paths on which discrepancies remain small for many random Paulis.

3 Related Work

Prior work established quantum learning problems and quantum-memory separations, while leaving important questions about memoryless algorithms, adaptive lower bounds, and memory–sample tradeoffs.

  • Learning properties of quantum states: Quantum tomography requires exponentially many samples in the number of qubits, motivating shadow tomography as a lower-sample alternative.
  • Learning properties of quantum states: Shadow-tomography algorithms often use heavily entangled measurements and therefore require substantial quantum memory.
  • Learning properties of quantum states: Existing quantum property-testing separations were at most polynomial in settings considered before this work.
  • Quantum memory tradeoffs for learning: Prior work posed the power of memoryless algorithms as an open question in shadow tomography, spectrum testing, and general state tomography.
  • Learning quantum dynamics: Quantum process tomography studies full channel descriptions, while later work often restricts dynamics to structured classes such as Hamiltonian or Pauli channels.

4 Preliminaries

The preliminaries define the quantum states, measurements, channels, observables, permutation operators, and statistical tools used to formulate the paper’s learning models and lower bounds.

  • Quantum-information objects: A quantum channel is a linear operator mapping operators on n qubits to operators on m qubits.
  • Measurements: POVMs specify positive-semidefinite measurement elements whose probabilities determine classical outcomes, while post-measurement states describe the retained quantum system.
  • Measurements: Rank-1 POVMs can simulate arbitrary POVMs when only classical outcomes are retained, so they are information-theoretically sufficient for memoryless analyses.
  • Observables and operators: Pauli observables are tensor products of single-qubit Pauli operators, and their tensor-product sum is related to the swap operator.
  • Operators and integration: Permutation operators reorder tensor factors, providing the notation used in Haar integration and later moment calculations.
  • Lower-bound framework: Lower bounds reduce distinguishing performance to total-variation distance between transcript distributions via binary hypothesis testing and Le Cam’s two-point method.

5 Exponential separations in learning quantum states

This section develops lower bounds for memoryless learning of quantum states, showing exponential sample requirements for broad shadow-tomography tasks and purity testing while matching them with upper bounds.

  • Framework: A memoryless learner is represented by a measurement tree whose nodes encode prior classical outcomes and whose edges apply adaptive POVMs.
  • Shadow tomography: The lower-bound strategy reduces shadow tomography to distinguishing the maximally mixed state from a family of states with separated observable expectations.
  • Shadow tomography: Theorem 5.5 gives a general lower bound for memoryless prediction of many traceless observables satisfying the stated symmetry condition.
  • Shadow tomography: For random observables, memoryless shadow tomography requires Ω(min(M/log(M), 2^n)/ε^2) copies, and Pauli observables achieve the corresponding exponential regime.
  • Shadow tomography: For arbitrary observables, a memoryless upper bound uses O(min(M log(M), 2^n log(M))/ε^2) copies, matching the lower bound up to logarithmic factors in relevant cases.
  • Purity testing: Purity testing requires Ω(2^(n/2)) copies without quantum memory, while a memoryless algorithm succeeds with O(2^(n/2)) copies.

6 Exponential separation with bounded quantum memory

The section characterizes a quantum-memory/sample-complexity tradeoff for estimating Pauli expectations, proving exponential lower bounds for bounded memory and an efficient full-memory algorithm.

  • Lower bound: For k-qubit quantum memory, estimating all absolute Pauli expectations requires Ω(2^((n-k)/3)) copies.
  • Lower-bound model: The bounded-memory model tracks a k-qubit unnormalized memory state at each node while measurements act jointly on memory and a fresh copy of the unknown state.
  • Lower-bound proof: The proof controls transcript distinguishability by separating Pauli observables that are bad on measurement-tree edges from those that remain good.
  • Upper bound: With n qubits of quantum memory, estimating squared absolute Pauli expectations for M observables requires O(log(M)/ε^2) copies.
  • Upper bound: The full-memory algorithm stores one previous copy and performs entangled Bell-basis measurements on pairs of copies.

7.1 Prerequisites

This section models memoryless quantum learning as a classical-memory tree and defines channel-distinction tasks for depolarizing, unitary, orthogonal, and symplectic dynamics.

  • A channel-learning protocol is represented by a rooted tree whose nodes encode the classical memory state and whose depth counts experiments.
  • Each non-leaf node prepares a possibly auxiliary-entangled state, applies the channel, and measures the entire system with a node-dependent POVM.
  • Channel distinction tasks: The fixed unitary task distinguishes a completely depolarizing channel from a fixed Haar-random unitary channel, with orthogonal and symplectic variants.
  • Channel distinction tasks: The symmetry distinction task identifies whether dynamics belong to unitary, orthogonal, or symplectic time-reversal symmetry classes.
  • Channel distinction tasks: Two-hypothesis channel distinction samples from distributions D_A or D_B and asks the learner to identify the source distribution.

7.2 Review of the Weingarten calculus

This section reviews Haar integration for unitary, orthogonal, and symplectic groups, expressing moments through permutations or pair partitions and associated Weingarten functions.

  • Haar measures on U(d), O(d), and Sp(d/2) are invariant under left and right group multiplication and support the later proofs.
  • Unitary calculus: Unitary Haar moments are expressed using permutations in S_k and the unitary Weingarten function Wg^U.
  • Unitary calculus: The unitary Weingarten function is defined through the inverse of a matrix indexed by permutations, enabling computation of Haar moments of U^⊗k and U†⊗k.
  • Orthogonal and symplectic calculus: Orthogonal and symplectic Haar moments instead use pair partitions of 2k elements and corresponding Weingarten functions.
  • Orthogonal and symplectic calculus: Pair partitions pair 2k elements, while their cycle types are constructed from alternating applications of the pairing and identity maps.

7.3 Depolarizing channel versus random unitary

The section proves exponential sample lower bounds for distinguishing depolarizing dynamics from fixed random unitary, orthogonal, or symplectic channels without quantum memory, even with arbitrary auxiliary systems.

  • Any memoryless algorithm requires exponentially many experiments to distinguish a completely depolarizing channel from a fixed Haar-random unitary channel with success probability at least 2/3.
  • The same exponential hardness holds for distinguishing depolarizing dynamics from fixed Haar-random orthogonal and symplectic matrix channels.
  • Proof strategy: The unitary proof relies on permutation combinatorics, whereas the orthogonal and symplectic proofs use pair-permutation combinatorics.
  • Proof strategy: The generalized lower bounds allow arbitrary auxiliary systems, removing the prior restriction to protocols without ancilla qubits.
  • Proof strategy: The proofs use a tree representation of the learner, Haar averaging, and Cauchy–Schwarz-based bounds over root-to-leaf paths.

Second term

The proof bounds the second nonidentity contribution in the Haar expansion using norm inequalities and a previously established moment estimate.

  • The second term sums the absolute contributions indexed by nonidentity permutations.
  • Cauchy–Schwarz and Hölder inequalities reduce this term to a trace expression involving a positive semidefinite matrix.
  • The resulting contribution is bounded by O(T^2/d) using Lemma 6 of [ACQ21].

Third term

The proof bounds the third term by reorganizing trace products according to permutation cycles and root-to-leaf paths, then combines these estimates into a final bound that is o(1) when T is sufficiently small relative to d^(1/3).

  • Trace bounds: Positive semidefiniteness converts relevant trace-norm expressions into traces, enabling bounds through Cauchy-Schwarz and operator norm inequalities.For positive semidefinite operators, the 1-norm can be replaced by the trace, after which trace products are bounded by products of traces.
  • Cycle analysis: Cycle decompositions separate the analysis into even- and odd-length cycles, with each case reorganized into products of trace terms.The cycles are indexed within a fixed permutation, and their contributions are bounded separately before being recombined.
  • Path induction: Each reorganized summand contains every eρ_vi exactly once, which supports an inductive extraction of factors along root-to-leaf paths.The proof encodes single- and paired-index trace terms using the sets S(t)_1 and S(t)_2 and processes them inductively.
  • Path induction: Even cycles contribute |C_m|/2 pairs, while odd cycles contribute floor(|C_m|/2) pairs and one additional single element to the index sets.These counts determine the combinatorial structure used in the subsequent bound.
  • Final bound: When T = o(d^(1/3)), the resulting quantity is o(1) for an absolute constant c > 0.This conclusion follows after combining the preceding estimates and bounding the permutation contributions by the longest cycle length.

7.3.3 Proof of Theorems 7.10 and 7.11

The proof of Theorems 7.10 and 7.11 bounds orthogonal and symplectic contributions term by term using Cauchy-Schwarz, trace-norm inequalities, cycle decompositions, and pair partitions.

  • Proof strategy: Pair partitions organize the proof of both the orthogonal and symplectic cases.The argument treats corresponding terms separately in the O(d) and Sp(d/2) settings.
  • Norm bounds: Cauchy-Schwarz and 1-norm inequalities reduce diagrammatic expressions to products of trace or trace-norm factors.Positive semidefiniteness further identifies relevant 1-norms with traces, while the symplectic case also uses ||J||∞ = ||J^t||∞ = 1.
  • Orthogonal case: The orthogonal-case contribution is bounded by O(T^7/d^2) + O(T^2/d).This estimate combines Corollary 7.7 with Lemma 8 of [ACQ21].
  • Symplectic case: The symplectic-case contribution is bounded by O(T^(7/2)/d^2) + O(T^2/d).The bound uses Corollary 7.8 together with Lemma 10 of [ACQ21].
  • Cycle analysis: Cycle analysis distinguishes even and odd M2T-cycles, whose lengths are defined as half their numbers of elements.The resulting products are reorganized into terms indexed by cycles and then bounded using trace inequalities.

7.3.4 Corollaries involving state distinction

The corollaries transfer channel-distinction lower bounds to state-distinction tasks, yielding sample requirements for distinguishing maximally mixed states from fixed Haar-random states.

  • Complex Haar-random states: Any learning algorithm without quantum memory requires the stated lower bound to distinguish a maximally mixed n-qubit state from a fixed Haar-random pure state with probability at least 2/3.The proof reduces state distinction to unitary distinction by applying the unknown channel to |0⟩^⊗n.
  • Reduction strategy: These corollaries exemplify a strategy that derives state-distinction learning bounds from channel-distinction bounds.The text presents the strategy as general and notes that the first corollary is weaker than Theorem 5.11.
  • Real Haar-random states: The same type of lower bound applies when the Haar-random pure state is restricted to be real.The reduction uses Haar-random orthogonal or symplectic matrices, with the symplectic theorem providing the stronger bound mentioned in the passage.

7.3.5 Upper bound without quantum memory

Without quantum memory, scrambling-unitary channels can still be distinguished from completely depolarizing channels by reducing the task to purity testing of repeated output states.

  • Upper-bound algorithm: T = O(2^(n/2)) channel accesses suffice without quantum memory to distinguish a fixed Haar-random unitary channel from a completely depolarizing channel.The algorithm repeatedly inputs |0⟩^⊗n, measures each output in the computational basis, and classifies the resulting classical data.
  • Upper-bound algorithm: The reduction produces a fixed pure output state for a scrambling unitary and a completely mixed output state for a depolarizing channel.The outputs are then distinguished using the purity-testing upper bound.

7.3.6 Upper bound with quantum memory

With quantum memory, distinguishing a completely depolarizing channel from a fixed Haar-random unitary requires only a constant number of channel applications. A swap test uses quantum interference between stored copies to achieve this efficiency.

  • Upper bound with quantum memory: O(1) channel applications suffice to distinguish a completely depolarizing channel from a fixed Haar-random unitary with constant probability.The algorithm is also gate efficient, with O(n) gate complexity.
  • Upper bound with quantum memory: The protocol uses a swap test on a state produced by the channel and a stored copy of that state.The n-qubit quantum memory stores one copy, enabling the required quantum interference.
  • Upper bound with quantum memory: Quantum memory enables interference between channel outputs whose purities differ for depolarizing and unitary evolutions.The cited expressions distinguish the two cases through their output-state purities.

7.4 Symmetry distinction problem

The symmetry-distinction problem asks whether an unknown fixed Haar-random channel is unitary, orthogonal, or symplectic. Without quantum memory, achieving success probability at least 2/3 requires exponentially many channel uses, while tomography-based processing provides an upper bound and leaves a gap.

  • Problem formulation: The task distinguishes unitary, orthogonal, and symplectic channels, corresponding to different types of symmetry in the quantum evolution.Orthogonal and symplectic channels encode different time-reversal symmetries, whereas the unitary channel represents general evolution.
  • Lower bound: The lower-bound proof represents a memoryless learning algorithm as a tree and bounds its success probability over the tree's leaves.The leaf output identifies one of the three channel classes.
  • Lower bound: T = Ω(2^(2n/7)) channel uses are necessary for algorithms without quantum memory to achieve success probability at least 2/3.For T = o(2^(2n/7)), the success probability is at most 1/3 + o(1).
  • Open question: The sample-complexity landscape remains open because the stated upper and lower bounds do not yet coincide.The paper explicitly leaves the gap between these bounds as an open question.
  • Upper bound: The upper-bound algorithm performs state tomography on three channel outputs and compares estimated overlaps to classify the channel.It tests two overlaps against 1/2, first identifying the symplectic case, then the orthogonal case, with the remainder classified as unitary.
Loading 2111.05881v2…