PaperlayerView exact revision on arXiv

Source-linked AI summary

A survey on the complexity of learning quantum states

Anurag Anshu, Srinivasan Arunachalam

arXiv:2305.20069v1quant-phcs.CCcs.LG

TL;DR

The survey examines learnability as a complexity-theoretic lens on quantum states and synthesizes results across quantum learning models. It reports connections between quantum learning models and identifies unresolved constraints, including a bottleneck for matrix product state learning.

  • Problem

    A central question is how to distinguish simple from complex quantum states; learnability has emerged alongside measures such as correlation length, entanglement entropy, circuit size, and description size.

    Source: §1 · p. 1

  • Method

    The survey synthesizes results on which quantum-state classes are efficiently learnable and why some classes are hard to learn.

    Source: §1 · p. 1

  • Results

    Quantum differentially private PAC learning carries over a connection to representation dimension, classical communication complexity, and sfat(C) [AQS21].

    Source: §4.5 · p. 20

  • Takeaways & Limitations

    The survey argues that learnability is a powerful complexity metric that has revealed new properties of physically and computationally relevant quantum states.

    Source: §1 · p. 1

    For matrix product states, the lack of a two-dimensional analogue of is a key bottleneck, despite an area law for locally-gapped frustration-free spin systems [AAG22].

    Source: §3.5 · p. 14

Abstract

from arXiv · show

We survey various recent results that rigorously study the complexity of learning quantum states. These include progress on quantum tomography, learning physical quantum states, alternate learning models to tomography and learning classical functions encoded as quantum states. We highlight how these results are paving the way for a highly successful theory with a range of exciting open questions. To this end, we distill 25 open questions from these results.

1 Introduction

The introduction frames learnability as a complexity-theoretic way to study quantum states, alongside measures such as entanglement and circuit size. It outlines the survey’s coverage of tomography, physical states, alternate learning models, and classical functions encoded as states.

1 Introduction

  • Learnability has become a quantum-state complexity measure, complementing physics measures such as correlation length and entanglement entropy and computer-science measures such as circuit and description size.The survey argues that learnability reveals new properties of physically and computationally relevant states.Source: §1 · p. 1
  • The general framework gives a learner copies of an unknown state from a known class, uses quantum measurements, and outputs an accurate description.Its complexity measures are the number of copies used and the total number of gates.Source: §1 · p. 2

1.1 Organization of this survey

  • The survey brings together rigorous results on learning quantum states and highlights open questions about their complexity.Its concluding perspective concerns other work on sample and time complexity.Source: §1.1 · p. 2
  • The survey covers arbitrary-state tomography, physical-state learning, alternate learning models, and classical functions encoded as quantum states.The physical-state examples include stabilizer states, states from the Clifford hierarchy, Gibbs states, and matrix product states.Source: §1.1 · p. 2

2 Tomography

This section surveys quantum state tomography, which reconstructs an unknown state from copies and measures accuracy in trace distance. It presents sample-complexity bounds for general and single-copy measurements, proof ideas, and an open question about spectrum estimation.

2 Tomography

  • The section motivates tomography through applications including entanglement verification, correlation understanding, and noise calibration and control in quantum devices.It notes that earlier tomography algorithms had time complexity exponential in d, motivating the question of time-efficient procedures and single-copy measurements.Source: §2 · pp. 3–4
  • O(d2/δ2) copies suffice for tomography up to trace distance δ, while rank-r states have sample complexity ˜Θ(dr/ε) up to infidelity ε.The pure-state proof overview gives a ˜O(d/ε) bound, tight in d.Source: §2 · p. 3
  • Θ(d3/δ2) copies are necessary and sufficient for quantum state tomography using single-copy measurements.The lower bound also applies to adaptive single-copy measurements; the cited proof uses a learning-tree framework.Source: §2 · p. 4
  • The single-copy lower-bound proof uses a learning tree whose measurement nodes lead to classical outcomes and a hypothesis state at each leaf.For a hard distribution based on Gaussian ensemble matrices, the output is anti-concentrated around the target when tree depth is o(d3).Source: §2 · p. 4
  • Quantum spectrum estimation has an O(d2/ε2) upper bound and an Ω(d/ε2) lower bound in ℓ1 distance, leaving its tight sample complexity open.Spectrum learning is used as a subroutine in several property-testing algorithms.Source: §2 · p. 4

3 Learning physical quantum states

The section asks whether physically relevant subclasses can be learned with polynomial sample or time complexity, following the exponential sample complexity associated with fully learning arbitrary states. It names several subclasses and notes a lower bound for algorithms using Schur sampling.

3 Learning physical quantum states

  • The section turns from arbitrary-state learning, which can require exponentially many copies, to physically relevant subclasses that may admit polynomial sample or time complexity.The stated aim is to identify classes learnable with polynomial resources.Source: §3 · p. 4
  • The surveyed physical-state classes include stabilizer states, states from the Clifford hierarchy, Gibbs states at different temperature regimes, and matrix product states.Source: §3 · p. 4
  • Algorithms based on Schur sampling require at least Ω(d2/ε2) samples.Source: §3 · p. 4

3.1 Stabilizer states

The section reviews efficient learning of stabilizer states and raises open questions about learning more complex stabilizer-state families and reducing space requirements. It describes stabilizer states through subspace supports and polynomial phases over F2.

3.1 Stabilizer states

  • Exactly learning n-qubit stabilizer states takes O(n) samples and O(n3) time.Earlier single-copy measurements require O(n2) copies, whereas Montanaro’s procedure uses O(n) copies with entangled measurements over two copies.Source: §3.1 · p. 5
  • An n-qubit stabilizer state can be written with support on a subspace A and a phase given by linear and quadratic polynomials over F2.Source: §3.1 · p. 5
  • The section asks whether stabilizer rank-n states can be learned in polynomial time.Stabilizer rank is defined as the minimum number of stabilizer states in a linear combination representing the state.Source: §3.1 · p. 5
  • The section asks for the sample complexity of learning stabilizer states with o(n2) classical space and whether sample-space tradeoffs hold with quantum space.The stated Bell-sampling approach uses O(n) copies and O(n2) classical space.Source: §3.1 · pp. 5–6

3.2 Learning circuits with non-Clifford gates

The survey reports polynomial-query learning for T-depth-one circuits with O(log n) T gates, then identifies higher T-depth and larger T-gate counts as open questions. It also notes polynomial-time learning results for states prepared by Clifford circuits with O(log n) T gates.

3.2 Learning circuits with non-Clifford gates

  • For T-depth-one circuits with O(log n) T gates, poly(n) queries recover a circuit equivalent on computational-basis inputs [LC22].The result is stated for queries to the circuit and equivalence restricted to computational-basis inputs.Source: §3.2 · p. 6
  • Despite hardness for learning output distributions of Clifford circuits with a single T gate [HIN+22], T-depth-one circuits are learnable in polynomial time.The survey describes this contrast as surprising.Source: §3.2 · p. 6
  • The complexity of learning circuits with T-depth t for t ≥ 2 remains an open question.Source: §3.2 · p. 6
  • Grewal et al. report polynomial-time algorithms for learning states prepared by Clifford circuits with O(log n) T gates [GIKL23a] [GIKL23b] [GIKL23c].They also report learning the circuits' output states in polynomial time.Source: §3.2 · p. 6
  • Whether n-qubit states and circuits with ω(log n) T gates can be learned, or are conditionally hard to learn, remains open.Source: §3.2 · p. 6

3.3 Learning phase states

The survey reviews learning classical low-degree Boolean functions encoded in phase states, including separable-measurement bounds and a derivative-based learning approach. It also identifies open questions about learning circuits with non-diagonal gates and testing degree-d phase states.

3.3 Learning phase states

  • Degree-d phase states encode degree-d functions in their amplitudes, and the survey notes applications in cryptography, pseudorandomness, and measurement-based quantum computing [BS19] [INN+22] [AQY21] [RHBM13] [TMH19] [ABDY22].Source: §3.3 · p. 6
  • Earlier results give O(n) samples for degree-1 and O(n2) for degree-2 binary phase states; degree-d learning for d ≥ 3 remained open before [ABDY22].The survey says generalized phase-state sample complexity had not previously been studied.Source: §3.3 · p. 7
  • A separable-measurement approach learns f by sampling constraints on its first derivatives and repeating the process across n directions.The method uses a POVM whose outcome differs with certainty from the target derivative value, then reconstructs f from the learned derivatives.Source: §3.3 · p. 7
  • Even with arbitrary single-copy measurements, learning a uniformly random degree-d function from its phase state requires Ω(nd) copies.For a typical function, one measured copy provides at most O(1) bits of information, while the function has entropy Ω(nd).Source: §3.3 · p. 7
  • Learning circuits with non-diagonal gates in the Clifford hierarchy from copies of their output states remains open, despite a procedure for learning the hierarchy with circuit query access [Low09].The survey also notes a procedure for learning circuits consisting of diagonal gates in the Clifford hierarchy that produce phase states [ABDY22].Source: §3.3 · pp. 7–8
  • The copy complexity of testing whether a state is a degree-d phase state or ε-far from that set remains an open question.Source: §3.3 · p. 8

3.4 Gibbs states of local Hamiltonians

This section surveys learning local Hamiltonians from Gibbs states, with algorithms based on sufficient statistics and localized marginals. It distinguishes commuting and high-temperature settings and ends with open questions about efficient learning beyond those regimes.

3.4 Gibbs states of local Hamiltonians

  • Learning outputs estimates of bounded-strength local interaction coefficients from Gibbs-state copies, assuming the interaction graph is known; applications include effective and entanglement Hamiltonians.The section notes that sparsity alone does not currently suffice to learn the underlying graph in the quantum setting.Source: §3.4 · pp. 8–9

3.4.1 Sufficient statistics

  • The local expectation values Tr(Eα ρβ(H)) are sufficient statistics: they form the gradient of the convex log partition function, whose gradient identifies the parameters.Figure 1 illustrates uniqueness of the point matching the gradient.Source: §3.4.1 · p. 9, Figure 1 · p. 10
  • Matching expectation values makes Gibbs states close, but does not by itself guarantee that the corresponding Hamiltonians are close.Strong convexity supports a robust gradient-descent approach; its runtime depends on computing the partition-function gradient, which is efficient in high-temperature, stoquastic, and 1D cases but large for arbitrary low-temperature Hamiltonians.Source: §3.4.1 · pp. 9–10

3.4.2 Commuting Hamiltonians

  • For commuting Hamiltonians, learning is efficient at any temperature when the interaction graph is known, using local marginals whose effective Hamiltonian differs by a boundary correction.The algorithm tomographs a region around each interaction and takes the logarithm of its marginal to estimate the local term.Source: §3.4.2 · p. 10

3.4.3 High temperature Gibbs states

  • At high temperature, cluster expansion gives a boundary correction decaying exponentially with region radius; an early local approach can require super-polynomial samples for sufficiently accurate local-term estimates, while [HKT22a] gives tight sample and time complexity for β < βc.The local approach uses radius O(log 1/ε), with an additional sample factor exp(rD).Source: §3.4.3 · pp. 11–12

3.4.4 Discussion

  • Efficient Hamiltonian learning at arbitrary β on fixed geometry remains open; the section asks whether approximate conditional independence or pseudorandomness can clarify learnability.Approximate conditional independence is known in 1D and conjectured in every dimension [KB19].Source: §3.4.4 · p. 12

3.5 Matrix product states

The section surveys learning matrix product states (MPS), including how measurement restrictions affect reconstruction and output bond dimension. It also identifies unresolved questions for injective MPS and PEPS.

3.5 Matrix product states

  • An MPS represents a spin-chain state using site matrices, and learning seeks a fidelity approximation whose output bond dimension remains close to the input dimension D.Many physically relevant states, including gapped ground states, can be approximated by MPS with bond dimension polynomial in n.Source: §3.5 · p. 12
  • Global-but-efficient measurements support polynomial-time MPS learning with output bond dimension D′ = poly(D) [CPF+10b].The learner learns a sequential circuit that prepares the MPS.Source: §3.5 · pp. 12–13
  • For injective MPS, O(log D)-qudit marginals determine the parent Hamiltonian, but [LVV15, ALVV17] can output bond dimension poly(n), while [CPF+10b] lacks a closeness guarantee.Question 10 asks whether local-measurement learning can achieve output bond dimension poly(D); Question 11 asks whether [LVV15, ALVV17] can be improved under an MPS ground-state promise.Source: §3.5 · p. 13
  • For injective PEPS, the section asks whether a polynomial-time, polynomial-sample approximation to the parent Hamiltonian can yield a similar PEPS description.The stated bottleneck is the absence of a two-dimensional analogue of, despite an area law for locally-gapped frustration-free spin systems [AAG22].Source: §3.5 · pp. 13–14

4 Alternate models of learning quantum states

The section surveys learning models that relax full-state tomography by changing the learner’s goal or interaction with the state. It presents sample-efficient PAC learning and shadow tomography alongside online learning, while noting their distinct guarantees and limitations.

4.1 PAC learning and online learning

  • Unlike tomography’s trace-distance goal, quantum PAC learning requires measurement predictions to be accurate only for most measurements under a distribution.The learner receives examples consisting of measurements and their expectation values.Source: §4.1 · p. 14
  • O(n·poly(1/ε, 1/δ, 1/γ)) samples suffice to PAC-learn n-qubit quantum states.The guarantee concerns agreement on most measurements drawn from the learning distribution.Source: §4.1 · pp. 14–15
  • Open questions concern the time complexity of PAC learning Clifford-circuit states with t T gates and the sample complexity for stabilizer-rank k states; noisy stabilizer-state learning is as hard as learning parities with noise [GL22].The cited hardness result is for a restrictive statistical-query model with depolarizing noise.Source: §4.1 · p. 15
  • Online learning uses sequential state copies and measurement descriptions to predict expectation values; its mistake bound is at most O(n/ε^2) for n-qubit states [ACH+18].The learner aims to make only finitely many mistakes before predicting correctly on all future rounds.Source: §4.1 · p. 15

4.2 Shadow tomography

  • Shadow tomography seeks estimates of Tr(ρE_i) for many specified operators, improving on either full tomography or estimating each observable separately.Its learner uses a quantum OR lemma variant to identify a mismatched observable, then updates its state estimate.Source: §4.2 · pp. 15–16
  • Shadow tomography estimates m observables with exponentially fewer samples in both m and n than the naive protocols, but its running time remains exponential in n.The stated sample bound is eO((n log^4 m)/ε^4) copies of ρ.Source: §4.2 · pp. 15–16

4.3 Max-entropy principle and Matrix Multiplicative Weight Update

The section connects shadow tomography to the maximum-entropy principle and describes an alternative based on updating a Gibbs-state representation. It also notes a condition under which the updates can support Hamiltonian learning.

4.3 Max-entropy principle and Matrix Multiplicative Weight Update

  • The maximum-entropy state matching specified expectation values is a Gibbs state, providing a representation for shadow-tomography estimates.The section motivates this choice by seeking a state no more informative than needed to match the observables.Source: §4.3 · p. 16
  • The alternative algorithm starts from the maximally mixed state and updates the weight of an observable whose expectation remains mismatched.The maximally mixed state is represented as the Gibbs state of the trivial Hamiltonian 0, so updates can be made directly to the Hamiltonian.Source: §4.3 · pp. 16–17
  • When ρ is itself a Gibbs state, strong convexity from ensures that updating basis-operator weights until expectations are close learns the Hamiltonian to the desired error.Source: §4.3 · p. 17

4.4 Subsequent works building on shadow tomography

Follow-up work develops classical shadows as a time-efficient alternative to shadow tomography, improves its complexity and applies it to quantum agnostic learning, and studies limits under separable measurements.

4.4.1 Classical shadows

  • O((log m) · B/ε2) copies suffice to estimate m expectation values, and the classical-shadows procedure is independent of the observables being estimated.For one observable, Theorem 9 gives O(B/ε2 log(1/δ)) copies when Tr(M2) ≤ B.Source: §4.4.1 · p. 17

4.4.2 Improved shadow tomography and agnostic learning

  • ˜O((n·log2 m)/ε2) copies give the best known dependence on n, m, and ε; [BO21] use shadow tomography for quantum agnostic learning with α = 3.Open questions ask whether α = 1 is possible and which classes, including stabilizer states, can be learned time-efficiently.Source: §4.4.2 · p. 18

4.4.3 Shadow tomography with separable measurements

  • With separable measurements, shadow tomography requires ˜Ω(min{m, d}) copies, matching the Huang et al. [HKP20] upper bound; estimating all n-qubit Pauli expectations requires Ω(2^n) copies.The latter lower bound follows from a learning-tree argument and a bound on δ for the Pauli observables.Source: §4.4.3 · pp. 18–19
  • For separable-measurement lower bounds, the proof uses a learning tree whose nodes represent measurements and whose leaves represent target expectation values.For the Paulis, δ(P1, . . . , P2^n) is exactly 1/(2^n + 1).Source: §4.4.3 · p. 19
  • Shadow tomography also applies to adaptive and non-adaptive measurement settings, while [GA22] give a protocol for m k-outcome measurements using poly(k, log m, n, 1/ε) copies.Adaptive learners may base measurements on previous outcomes; non-adaptive learners choose the sequence in advance.Source: §4.4.3 · p. 19

4.5 Equivalence between quantum learning models

[AQS21] establish equivalences among quantum learning models, linking results across frameworks while noting that only a few implications are efficient in both sample and time complexity. Their proof sketch adapts connections through online learning, stability, and differential privacy to the quantum setting.

4.5 Equivalence between quantum learning models

  • [AQS21] show equivalences among PAC, online, communication-complexity, and shadow-tomography models, but only a few implications are efficient in both sample and time complexity.The other implications are primarily information-theoretic.Source: §4.5 · p. 19
  • [AQS21] carry over the connection from differentially private PAC learning to small representation dimension, which upper-bounds communication complexity and sfat(C).The paper sketches adapting the classical chain of connections to the quantum setting.Source: §4.5 · p. 20
  • For finite sfat(C), [AQS21] construct an RSOA online learner making at most sfat(C) mistakes; it makes explicit an algorithm achieving the upper bound sfat(C) ≤ n from [ACH+18].The RSOA is robust to adversarial imprecision in training feedback.Source: §4.5 · p. 20
  • [AQS21] adapt the stability construction by injecting examples that force RSOA mistakes, addressing real-valued functions and ε-uncertainty in adversarial feedback.The construction uses the fact that RSOA identifies the target after at most d mistakes when sfat(C) = d.Source: §4.5 · p. 20
  • To make a stable quantum learner differentially private, [AQS21] modify Stable Histograms because near-identical quantum states make a “most frequent” output ill-defined.The classical wrapper runs a stable algorithm repeatedly and adds Laplacian noise to its most frequent output.Source: §4.5 · p. 20

5 Learning classical functions through quantum encoding

Section 5 surveys quantum examples for learning classical functions, statistical-query models for learning from those examples, and quantum kernel methods that estimate similarities before classical classification. It reports both model-specific learning guarantees and open questions about quantum advantages.

5.1 Learning Boolean functions

  • Quantum examples have mixed PAC results: they help under uniform and product distributions and for noisy parities, but not distribution-independently or for uniform circuit families.In distribution-independent random-classification-noise and agnostic learning, quantum sample complexity equals classical sample complexity up to constant factors; only parities are noted as polynomial-time learnable in the former setting.Source: §5.1 · p. 21

5.2 Statistical query model

  • QSQ learners make single-copy measurements rather than entangled measurements, and known uniform-distribution PAC results for parities, DNF formulas, and juntas can be implemented in this model.The survey asks whether QSQ separates from quantum PAC learning with separable measurements and what diagonal-QSQ complexity is needed for constant-depth circuit output distributions.Source: §5.2 · p. 22
  • Under uniform-distribution QSQ, parities, juntas, DNF formulas, and sparse functions can be learned; the proof strategy estimates Fourier mass through QSQ queries.The survey notes that the learning algorithms use Fourier sampling, and that the Fourier-mass observation yields the result.Source: §5.2 · p. 22

5.3 Kernel Methods

  • Quantum kernel methods map classical data to quantum feature states, estimate pairwise kernel entries with a quantum circuit, then use a classical optimizer to find a separating classifier.The circuit estimates each entry from the transition amplitude associated with U†(xj)U(xi).Source: §5.3 · p. 23, Figure 6 · p. 24
  • A discrete-log classification task shows quantum kernel methods can solve a classically intractable learning problem despite finite sampling noise.The particular task requires a fault-tolerant quantum computer; the survey presents it as formal evidence of quantum advantage using kernel methods.Source: §5.3 · pp. 23–24
  • An open question is whether quantum kernel methods offer an unconditional polynomial advantage over classical learning for a natural problem.The cited discrete-log result requires fault tolerance, while the survey identifies the unconditional-advantage question as unresolved.Source: §5.3 · pp. 23–24

6 Perspective on other works

The survey places quantum learning at the intersection of computer science and physics and points to related work and open questions beyond canonical learning tasks. These directions include quantum communication, simple witnesses for Hamiltonian problems, coset-state learning, and functions of density matrices.

Other related works

  • Related directions include quantum noise and channel tomography, ground-state properties, quantum dynamics and simulation, matrix product states, Born machines, Hamiltonian learning, neural networks, and time-evolution unitaries.The survey also notes efficient algorithms for learning unitaries defined by time evolution e^−iHt.Source: §6 · p. 24

Sample complexity as a measure in quantum communication

  • In quantum communication, estimating ⟨ψ|M|ϕ⟩ from multiple copies motivates comparing sample complexity under classical versus quantum communication.For M = I, the cited work [ALL22] showed an exponential sample-complexity separation between classical and quantum communication.Source: §6 · p. 25

Sample complexity as a measure in the Local Hamiltonian problem

  • For simple quantum witnesses, the survey asks whether sample-complexity lower bounds can be proved for estimating a Hamiltonian’s ground energy, including when the Hamiltonian is sparse and available by oracle.Low-depth or stabilizer witnesses can have very small overlap with some ground states, but their usefulness for estimating ground energy by other means is unclear.Source: §6 · p. 25

Time-efficient learning coset states

  • For coset states, sample complexity is known, but time-efficient learning for arbitrary groups remains open; the survey asks about alternate models and approaches avoiding second-register measurement.The standard HSP approach measures the second register, motivating the question of whether non-Abelian HSP can avoid doing so.Source: §6 · pp. 25–26

Sample complexity of generalizing LMR

  • The survey asks for the sample complexity of approximately implementing e^−if(ρ)t for functions f acting on density matrices, extending the question beyond the LMR protocol.For e^−iρt, the LMR protocol uses O(t/δ^2) copies to achieve diamond-norm error δ, and that sample complexity was shown optimal.Source: §6 · p. 26
Loading 2305.20069v1…