Source-linked AI summary
Predicting Features of Quantum Systems from Very Few Measurements
Hsin-Yuan Huang, Richard Kueng
TL;DR
Large quantum systems are difficult to reconstruct from measurements, although many tasks require only selected features. The paper builds a classical shadow from tractable measurements and uses it to predict many linear functions. For bounded Hilbert-Schmidt norms, the required measurement count scales logarithmically with the number of predictions and is independent of system size.
Problem
Full quantum-state reconstruction requires exponentially many measurement repetitions, memory, and computation as the number of system constituents grows.
Source: A. Motivation · p. 1Method
The protocol constructs a compact classical shadow from independent tractable measurements and applies median-of-means estimation to predict linear functions.
Source: A. Motivation · p. 2Results
For bounded Hilbert-Schmidt norms, a shadow of size proportional to log(M) predicts M linear functions, with scaling independent of system dimension and matching an information-theoretic lower bound.
Source: A. Motivation · p. 2Takeaways & Limitations
The method supports prediction of many features without reconstructing the full quantum state, including numerical tests on systems exceeding 160 qubits.
Source: B. Summary of classical shadows · p. 8When target observables have exponentially large Hilbert-Schmidt norm, such as Pauli spin-chain expectations, accurate shadow prediction can require exponentially many samples.
Source: D. Illustrative example applications · p. 3
Abstract
from arXiv · showhide
Predicting features of complex, large-scale quantum systems is essential to the characterization and engineering of quantum architectures. We present an efficient approach for constructing an approximate classical description, called the classical shadow, of a quantum system from very few quantum measurements that can later be used to predict a large collection of features. This approach is guaranteed to accurately predict M linear functions with bounded Hilbert-Schmidt norm from only order of log(M) measurements. This is completely independent of the system size and saturates fundamental lower bounds from information theory. We support our theoretical findings with numerical experiments over a wide range of problem sizes (2 to 162 qubits). These highlight advantages compared to existing machine learning approaches.
I. INTRODUCTION AND MAIN RESULTS
Full quantum-state reconstruction becomes impractical as system size grows, while many tasks need only selected features. The paper introduces a compact classical shadow built from tractable measurements and used to predict linear functions.
A. Motivation
- Full state reconstruction requires exponentially many measurements, memory, and computation, while structured tomography methods remain exponential for general systems.MPS and neural-network tomography use polynomial samples when the state has advantageous structure.Source: A. Motivation · p. 1
- Shadow tomography targets selected linear features rather than a full state description, but existing protocols require exponentially long circuits acting on quantum memories.Examples of target features include fidelities, entanglement witnesses, and observable expectation values.Source: A. Motivation · p. 1
- The method learns a compact classical shadow from independent, tractable measurements, then uses median-of-means estimation to predict linear functions.The paper combines feature prediction, statistical convergence guarantees, and the stabilizer formalism.Source: A. Motivation · p. 2, B. The procedure · p. 3
- Numerical simulations up to 162 qubits report favorable scaling and improvements over neural-network tomography in practically motivated tests.The reported comparisons concern prediction of relevant, non-local target functions.Source: A. Motivation · p. 2
B. The procedure
- Random Clifford measurements produce stored rotated basis states, with stabilizer-state descriptions requiring only O(n^2) bits.The stored array is processed in chunks to form independent linear estimators before median-of-means prediction.Source: B. The procedure · pp. 2–3
C. Rigorous performance guarantees
Classical shadows provide a sample bound for predicting many linear target functions, with the required size governed by their Hilbert-Schmidt norms.
C. Rigorous performance guarantees
- A shadow of size on the order of log(M) max_i tr(O_i^2)/ϵ^2 suffices to predict M linear target functions to accuracy ϵ.The theorem statement gives the scaling in terms of the largest target-function squared Hilbert-Schmidt norm.Source: C. Rigorous performance guarantees · p. 3
- For constant Hilbert-Schmidt norms, the sample scaling permits exponentially many predictions from polynomially many measurements.This sampling rate is independent of system dimension.Source: C. Rigorous performance guarantees · p. 3
D. Illustrative example applications
The paper illustrates classical-shadow prediction for fidelities and entanglement witnesses, while identifying observables whose norm makes prediction costly. It also gives an information-theoretic lower bound matching the method's scaling.
D. Illustrative example applications
- A dimension-independent-size shadow can estimate fidelity with any pure target, and polynomial size suffices for exponentially many pure-target fidelities.The stated base case improves on the cited direct-fidelity-estimation sample requirement of O(2^n/ϵ^4) in the worst case.Source: D. Illustrative example applications · p. 3
- Logarithmic-size shadows can check exponentially many maximally entangled-state witnesses simultaneously, without measurements tailored to individual witnesses.The discussion also states that these ideas extend to genuine multipartite entanglement detection.Source: D. Illustrative example applications · p. 3
- For a Pauli spin-chain expectation, tr(O^2)=2^n, so accurate prediction requires an exponential-size shadow, unlike direct spin measurement.The direct measurement uses order 1/ϵ^2 state copies for the same accuracy.Source: D. Illustrative example applications · p. 3
- A shadow of size n2^n/ϵ^2 predicts all spin expectation values simultaneously, improving by a square-root factor over naive direct measurement of all 4^n combinations.The passage says this scaling matches an optimal strategy that groups Pauli strings into 2^n+1 commuting sets.Source: D. Illustrative example applications · p. 4
E. Matching information-theoretic lower bounds
- Any linear prediction procedure based on a fixed set of independent measurements needs at least log(M) max_i tr(O_i^2)/ϵ^2 state copies.This lower bound matches the classical-shadow performance and establishes asymptotic optimality in that setting.Source: E. Matching information-theoretic… · p. 4
- The lower-bound scaling can be bypassed with joint measurements across copies or target-adapted measurements, but the cited shadow-tomography protocol uses exponential-size circuits.Those circuits depend on the M target functions and act simultaneously on copies of the unknown state.Source: E. Matching information-theoretic… · p. 4
II. NUMERICAL EXPERIMENTS
The experiments compare classical shadows with neural network quantum state tomography (NNQST) on GHZ and toric-code states. Classical shadows retain system-size-independent fidelity estimation in both settings, while NNQST scales unfavorably on toric-code states and can overestimate GHZ fidelity under phase error.
Toric code ground states
- For toric-code ground-state fidelity, NNQST measurement requirements scale unfavorably with system size, while classical-shadow estimation is system-size independent.Figure 3 compares NNQST using classical fidelity with classical shadows using quantum fidelity.Source: Figure 3 · p. 5, A. Direct fidelity estimation and… · pp. 5–6
GHZ states
- Classical shadows use constant-size sketches to estimate GHZ target fidelities regardless of system size, while NNQST training data for 0.99 fidelity scales linearly with qubit number.The experiments also include systems with more than 160 qubits.Source: A. Direct fidelity estimation and… · pp. 4–5
- For a GHZ source with phase error, classical-shadow estimates track the target-fidelity decrease, whereas NNQST overestimates it, even when the state is orthogonal to the target.The authors suggest the gap may reflect classical fidelity's status as an upper bound on quantum fidelity and the limits of local measurements for global phases.Source: A. Direct fidelity estimation and… · p. 5
B. Witnesses for tri-partite entanglement
For tripartite entanglement, classical shadows let one check a fixed list of witnesses with logarithmically many measurements, rather than measuring each witness separately. The related work contrasts this feature-prediction task with full-state tomography and other approaches whose efficiency depends on state structure or measurement resources.
B. Witnesses for tri-partite entanglement
- Classical shadows check a fixed list of M entanglement witnesses with log(M)-many measurements, versus at least linear scaling when measuring witnesses individually.For locally, randomly rotated GHZ states, the experiments report reaching witness-detection thresholds with exponentially fewer samples than the direct method.Source: B. Witnesses for tri-partite… · p. 6
A. Related work
- Full tomography requires order rank(ρ)D copies with joint measurements, or order rank(ρ)^2D for independent measurements, and general n-qubit states face an exponential scaling bottleneck.The cited work describes sample-optimal protocols that attain these respective bounds.Source: A. Related work · p. 7
- MPS tomography needs only polynomial samples when the state is well approximated by a low-bond-dimension MPS, but general states may not meet that condition.Neural-network tomography may apply more broadly than MPS tomography, although its efficiently representable and reconstructable system class remains unclear.Source: A. Related work · p. 7
- Stabilizer sketching compresses classical state descriptions, but still requires an exponentially sized classical description of the state in practice.Its description is noted as similar to classical shadows.Source: A. Related work · p. 7
- Direct fidelity estimation targets one pure-state fidelity, while shadow tomography predicts many measurement probabilities using joint quantum operations on state copies.The cited shadow-tomography protocol uses exponential-size circuits acting on all copies simultaneously.Source: A. Related work · p. 7
B. Summary of classical shadows
Classical shadows use independent Clifford measurements to create a compact classical sketch that supports prediction of linear target functions. The paper describes tractable acquisition and prediction, gives statistical guarantees, and identifies extensions to channel tomography and combinations with quantum memory or machine learning as open directions.
B. Summary of classical shadows
- Independent Clifford measurements produce a classical shadow that can be stored efficiently and used to predict arbitrary linear target functions.The data consist of stabilizer states, and prediction uses median-of-means estimation.Source: B. Summary of classical shadows · pp. 7–8
- A shadow of size B log(M)/ϵ^2 suffices to predict M target functions when B ≥ max_i tr(O_i^2), with ϵ-accuracy.For predictors of approximately constant Hilbert-Schmidt norm, this guarantee improves on Aaronson's; large-norm targets such as Pauli observables can instead favor shadow tomography.Source: B. Summary of classical shadows · p. 8
- Tractable prediction, especially for stabilizer-state fidelities, supports numerical experiments on systems exceeding 160 qubits and shows consistent improvement over the compared neural-network approach on relevant non-local targets.The comparison uses median-of-means estimation with classical shadows against neural-network methods based on local SIC/tetrahedral measurements.Source: B. Summary of classical shadows · p. 8
C. Outlook
- The proposed implementation prioritizes tractable Clifford circuits, computational-basis measurements, and classical stabilizer processing for potential use in state-of-the-art architectures.The authors state that practical performance remains to be tested.Source: C. Outlook · p. 8
- The authors identify combining classical shadows with quantum-channel tomography, joint quantum measurements, or machine learning as future research directions.They pose open questions about compressed channel sketches and improved guarantees from combining these approaches.Source: C. Outlook · p. 8
Appendix A: Proof of Theorem 1
The appendix develops stabilizer measurements as an estimator for linear features, then uses median-of-means estimation to control failures caused by outliers. Stabilizer states also provide a structured measurement family whose moments support the variance analysis.
1. The stabilizer formalism
- Random Clifford circuits followed by computational-basis measurements implement the stabilizer measurement, and stabilizer states reproduce Haar moments through order three.Clifford circuits map Pauli operators to Pauli operators and can be efficiently simulated classically.Source: §1 · p. 9
- A stabilizer measurement outcome defines an estimator for any Hermitian linear feature with the correct expectation and variance bounded by 3 tr(O²).The estimator is formed from the measured stabilizer state as (2^n + 1)|s⟩⟨s| − I.Source: §1 · p. 10, §2 · p. 10
2. Median of means estimation
- Median-of-means estimation makes the failure probability decrease exponentially with the number of batches, addressing the sample mean’s vulnerability to outliers.The sample mean can be distorted by rare, exponentially large contributions; the median estimator fails only when more than half of the batch means deviate.Source: §2 · p. 10
- For a random variable with variance σ², N = 34Kσ²/ϵ² samples suffice for median-of-means error probability at most 2e^(−K/2).This gives an exponential dependence on the number of batches K in the failure bound.Source: §2 · p. 10
3. Feature prediction using classical shadows and median of means
The section gives a sample bound for predicting a collection of linear features from independent stabilizer measurements using median-of-means estimation. It also describes alternative net-based protocols and a many-prediction improvement that matches lower bounds up to logarithmic factors.
3. Feature prediction using classical shadows and median of means
- N = 204 log(2M/δ) max_i tr(O_i²)/ϵ² stabilizer measurements suffice to predict all M features within ϵ with probability at least 1 − δ.The predictions use median-of-means estimation.Source: §3 · p. 11
- In the very-many-predictions regime, an improved concrete protocol predicts all feature values within ϵ and matches the lower bounds up to log-factors.The section identifies this regime as M > 2^(2n).Source: §3 · p. 11
- Three valid protocols estimate fidelities at net points and approximate the target features, allowing selection of the protocol with the smallest sample size.The net fineness determines the alternatives; one protocol truncates small eigenvalues while another omits truncation.Source: §3 · p. 11
Appendix B: Proof of Theorem 2
The appendix proves an information-theoretic lower bound for predicting linear features from agnostic measurements and relates it to a communication task. Its protocol uses a random rotation revealed only after measurement to model the feature-independent measurement setting.
1. Detailed statement and proof idea
- The lower bound exactly matches the constructive result in Theorem 4, making classical-shadow feature prediction sample-optimal among procedures based on agnostic measurements.The theorem concerns prediction of bounded linear features from fixed measurement procedures.Source: §1 · p. 12
- The proof embeds a prediction procedure in a communication protocol: Alice sends copies of a quantum state encoding a message, and Bob uses the device to decode it.Information theory relates the message length, proportional to log₂(M), to the number of state copies N.Source: §1 · p. 12
- A random rotation revealed only after Bob measures models measurements independent of the features; Bob can account for it by predicting rotated features.This preserves the communication protocol because tr(UO_iU† Uρ_XU†) = tr(O_iρ_X).Source: §1 · p. 12, §2 · p. 13
2. Description of the communication protocol
- The protocol has Alice encode a message in N copies, Bob measure them, use the predictions to identify the encoded state, and recover the message.The assumed prediction accuracy makes this communication procedure succeed with high probability.Source: §2 · p. 13
3. Information-theoretic analysis
The information-theoretic analysis bounds how much the measurement outcomes reveal about Alice’s message. Combining successful decoding with conditional mutual-information bounds yields a relation between the number of features and the number of measurements.
3. Information-theoretic analysis
- Because the message X is decoded with high probability and is chosen uniformly, Fano’s inequality supplies a lower bound on the information available from the outcomes.The random rotation U is independent of X, so I(X : U) = 0.Source: §3 · p. 14
- Conditional mutual information is bounded by summing the information contributions of individual measurement outcomes, using their independence given X and U.The derivation applies the entropy chain bound to Y₁, …, Y_N.Source: §3 · p. 14
- The analysis obtains Ω(log(M)) ≤ I(X : Y | U) ≤ 36Nϵ²/B, relating the number of features to measurements.Here Y denotes the measurement outcomes conditioned on the random unitary U.Source: §3 · p. 14
4. Detailed construction of quantum encoding and linear prediction decoding
The lower-bound construction seeks code states that are distinguishable by linear features while conveying little information about their identity. It uses low-overlap subspace projectors and an information-theoretic argument to establish the measurement lower bound.
4. Detailed construction of quantum encoding and linear prediction decoding
- The construction balances distinguishability by linear features against keeping the code states as similar as possible.The code states should convey as little information about their identity as possible, while each state remains distinguishable through its corresponding feature.Source: §4 · p. 14
- For case 1, rank-B/4 projectors with pairwise normalized overlap below 1/2 define the codebook, and O_i = 2P_i are the corresponding features.The probabilistic method is used to establish that such a projector configuration exists.Source: §4 · p. 14
- The projector construction satisfies the required conditions, completing the information-theoretic lower-bound proof for case 1.The text notes that cases 2 and 3 also yield the desired result, while focusing the proof on case 1, M ≤ exp(D/32).Source: §4 · pp. 14–15
Appendix C: Details regarding numerical experiments
The experiments use stabilizer-based classical simulation for larger systems and specify distinct data-generation and measurement procedures for the tested states. They also describe the neural-network comparison and the entanglement-witness evaluation.
Appendix C: Details regarding numerical experiments
- For systems above 100 qubits, the experiments focus on stabilizer states, which can be classically simulated using the Gottesman–Knill theorem and an improved algorithm [2].The protocol samples Clifford unitaries and measures in the Z basis using standard stabilizer-state procedures [2] [38].Source: Appendix C · pp. 16–17
- For neural-network tomography, the toric-code comparison uses the Psi2 POVM, a Z-basis measurement that is not tomographically complete.The authors report better model performance with Psi2, possibly because closed-loop patterns are more obvious and the figure of merit is classical fidelity.Source: Appendix C · p. 17
- Toric-code training data are sampled as uniformly random closed-loop configurations, using a tableau containing stabilizers and destabilizers.The toric-code stabilizers are X-stars and Z-plaquettes, together with two Z-strings over the torus loops.Source: Appendix C · pp. 17–18
- For tripartite entanglement, random witness candidates are tested, with α = 0.5 for genuine entanglement and α = 0.75 for GHZ-type entanglement.The classical-shadow procedure first sets the repetitions needed for simultaneous 0.1-accurate prediction, then estimates the witnesses.Source: Appendix C · p. 18