Source-linked AI summary
Shadow Tomography of Quantum States
Scott Aaronson
TL;DR
Shadow tomography asks how to estimate many measurements of an unknown quantum state without the infeasible copy burden of full tomography. The paper settles this question affirmatively, providing a procedure whose sample complexity scales logarithmically with the number of measurements and state dimension, while leaving tighter bounds and efficient special-case algorithms open.
Problem
Full quantum state tomography can require astronomically many measurements for entangled states, motivating the question of estimating many known measurements more efficiently.
Method
The paper uses a shadow-tomography procedure and analyzes gentle-measurement-based approaches, including a promise-gap variant for deciding measurement outcomes.
Results
The procedure estimates each measurement probability within additive error ε, with sample-complexity factors including log^4 M · log D.
Takeaways & Limitations
The main result settles the shadow-tomography question affirmatively and connects the problem to applications involving quantum advice and one-way communication.
Takeaways & Limitations
The paper conjectures that its sample-complexity bound is not tight, and it does not provide an algorithm from its ε-cover intuition because early measurements may irreparably damage the state.
Abstract
from arXiv · showhide
We introduce the problem of *shadow tomography*: given an unknown $D$-dimensional quantum mixed state $ρ$, as well as known two-outcome measurements $E_{1},\ldots,E_{M}$, estimate the probability that $E_{i}$ accepts $ρ$, to within additive error $\varepsilon$, for each of the $M$ measurements. How many copies of $ρ$ are needed to achieve this, with high probability? Surprisingly, we give a procedure that solves the problem by measuring only $\widetilde{O}\left( \varepsilon^{-4}\cdot\log^{4} M\cdot\log D\right)$ copies. This means, for example, that we can learn the behavior of an arbitrary $n$-qubit state, on all accepting/rejecting circuits of some fixed polynomial size, by measuring only $n^{O\left( 1\right)}$ copies of the state. This resolves an open problem of the author, which arose from his work on private-key quantum money schemes, but which also has applications to quantum copy-protected software, quantum advice, and quantum one-way communication. Recently, building on this work, Brandão et al. have given a different approach to shadow tomography using semidefinite programming, which achieves a savings in computation time.
1 Introduction
Shadow tomography asks whether selected measurement behavior of an unknown quantum state can be learned without reconstructing its full density matrix. The paper answers this affirmatively, using carefully designed measurements and substantially fewer copies than full tomography, while leaving tight sample complexity and computational efficiency open.
- Motivation: Full tomography can be astronomically expensive for n-qubit states because their Hilbert-space dimension is D = 2^n.The paper notes that full tomography had reached only 10-qubit states, requiring millions of measurements.
- Problem: Shadow tomography estimates Tr(E_iρ) for every known two-outcome measurement E_i to additive error ε, with high probability.The task measures copies of ρ and outputs estimates b_i satisfying the required error bound simultaneously.
- Main result: The main result settles affirmatively whether exponentially dimensional states can be characterized on exponentially many observables using polynomially many copies.The procedure measures copies carefully so that successive measurements do not destroy the information needed for later observables.
- Open issues: The paper does not establish tight general sample complexity, and implementing its measurement may require circuit size polynomial in both M and D.The authors identify both sample complexity and computational complexity as open directions.
- Main result: The method requires more than the Gentle Measurement Lemma alone, because no promise gap may exist and knife-edge measurements can severely damage the remaining copies.This is the central obstacle addressed by the paper.
- Method: Only Θ(log D) postselected-learning iterations are needed before the hypothesis state approximates the unknown state on every listed measurement.The iteration bound is the mechanism behind the logarithmic dependence on the state dimension.
2 Motivation
The paper connects shadow tomography to applications in quantum money, copy-protected software, quantum advice, and one-way communication. Its central consequence is that exponentially many behaviors can be learned from polynomially many copies, though computation and apparatus remain costly.
- Quantum Advice and Circuits: Corollary 6 estimates an n-qubit state’s acceptance probability for every polynomial-size quantum circuit using (n/ε)^O(1) copies.The guarantee applies simultaneously to all circuits with at most p(n) gates.
- Open Questions: The paper identifies tighter copy bounds and cheaper computation or measurement apparatus as open practical goals.The stated focus remains the information-theoretic number of copies rather than computational complexity.
- Quantum Money: Theorem 2 implies that private-key quantum money schemes permit counterfeiting with exponentially many computations but without queries to the bank.The counterfeiter estimates verification acceptance for every secret key and then searches for an acceptable state.
- Quantum Copy-Protected Software: Quantum copy-protection, if possible, requires computational assumptions because shadow tomography enables piracy of polynomial-qubit quantum programs.The pirate uses polynomially many program copies and exponential computation time to produce programs with similar acceptance behavior.
- Quantum Advice: For PromiseBQP/qpoly, shadow tomography generates the complete truth table on all inputs using polynomially many advice copies, at the cost of exponential computation.The algorithm approximates acceptance probabilities even without knowing which inputs satisfy the promise.
3 Preliminaries
This section defines mixed states, two-outcome measurements, trace distance, and gentle measurement tools used later. These preliminaries explain when measurements can be applied while preserving the state approximately.
- Quantum States: A D-dimensional mixed state is a trace-one Hermitian positive semidefinite matrix, with pure states and classical distributions as special cases.Rank-one states are pure, while diagonal states represent classical probability distributions.
- Distance: Trace distance generalizes variation distance and equals the maximum single-shot measurement bias for distinguishing two mixed states.It is defined from the eigenvalues of the difference between the states.
- Measurements: A two-outcome POVM is represented by a Hermitian matrix E with eigenvalues in [0,1], accepting ρ with probability Tr(Eρ).The rejection probability is 1−Tr(Eρ).
- Gentle Measurement: The Gentle Measurement Lemma bounds post-measurement disturbance when a measurement accepts with probability at least 1−ε.Conditioned on acceptance, the recovered state is close to the original in trace norm.
- Quantum Union Bound: The Quantum Union Bound extends gentle behavior to successive measurements that each accept with high probability.It lower-bounds the probability that all measurements accept and controls the resulting post-measurement state.
4 Gentle Search Procedure
The gentle search procedure reduces finding a highly accepting measurement to repeated quantum decision tests and binary search. It finds an approximately good measurement while accounting for accumulated error and the need for fresh copies.
- Procedure: The procedure searches a known list of measurements for one that accepts an unknown state with high probability, using a polylogarithmic number of copies as input.It serves as a subroutine for shadow tomography.
- Related Work: Harrow, Lin, and Montanaro’s corrected Quantum OR Bound underlies the method, while the soundness of Aaronson’s simpler random-order procedure remains open.Their approaches use more complicated measurements involving an ancilla register.
- Quantum OR Bound: A one-copy test achieves different acceptance probabilities in the two promised cases, supplying the decision primitive for search.The stated bounds are at least (1−ε)^2/7 in the positive case and at most 4ΔM in the negative case.
- Quantum OR Bound: The Quantum OR Bound distinguishes whether some measurement accepts with high probability under a promise about the list.Its test uses collective measurements and has copy complexity independent of Hilbert-space dimension D.
- Binary Search: Binary search recursively partitions the measurement list, but acceptance guarantees degrade and error probabilities accumulate at each level.Fresh copies are required at every recursion level.
- Gentle Search: Gentle Search finds a measurement accepting with probability at least c−ε whenever some listed measurement accepts with probability at least c.The procedure succeeds with probability at least 1−δ using the copy bound specified in Lemma 15.
5 Main Result
The paper estimates all specified measurement expectations by iteratively refining a classical hypothesis state and gently searching for measurements on which it is inaccurate. Its improved analysis achieves a sample complexity with ε^-4 dependence and logarithmic dependence on M and D.
- Iterative refinement: The procedure maintains a hypothesis ρ_t and repeatedly searches for a measurement whose predicted acceptance probability differs from the unknown state by more than ε.If no such measurement is found, the current hypothesis supplies all requested estimates.
- Iterative refinement: Each successful iteration postselects on an amplified measurement outcome to refine the hypothesis, using fresh copies of ρ.The implementation stores the hypothesis classically, so updates involving postselection need not be physically performed on the state.
- Termination: The process terminates with a hypothesis ρ_T satisfying |Tr(E_iρ_T) − Tr(E_iρ)| ≤ ε for every measurement.The proof bounds the number of iterations by tracking the probability that all postselection steps succeed.
- Sample complexity: The original analysis used ε^-5 dependence, while a newer online-learning algorithm improves this to ε^-4 up to lower-order amplification terms.The overall complexity comes from multiplying the refinement-iteration cost by the gentle-search cost within each iteration.
- Sample complexity: The improved sample complexity is approximately ε^-4 log^4 M · log D, matching an information-theoretic lower bound for the state-learning component.The result is obtained by combining the improved online-learning algorithm with the Gentle Search Procedure.
6 Lower Bound
The paper proves information-theoretic lower bounds for shadow tomography, first in a classical setting and then for quantum mixed states. The construction encodes a hidden index into distributions or subspaces so that accurate measurement estimates reveal the index, requiring many copies.
- Classical lower bound: Estimating every specified measurement to additive error ε is sufficient to identify the hidden index in the classical construction.The measurements are standard-basis tests for carefully chosen subsets S_i, and the distributions are biased toward their corresponding subsets.
- Classical lower bound: The lower-bound construction encodes a uniformly random index i containing Ω(N) bits, so recovering it requires mutual information at least log_2(K).For independent classical samples, each sample contributes at most log_2 N − H(D_i) information about the index.
- Classical lower bound: Ω samples from D_i are information-theoretically necessary for the classical construction, and the resulting lower bound applies even when the quantum state and measurements are diagonal.The theorem states that any shadow-tomography strategy with constant success probability requires this many copies.
- Quantum lower bound: The quantum construction replaces subsets by Haar-random half-dimensional subspaces and uses their projectors as the two-outcome measurements.Each state is maximally mixed on its associated subspace, while overlaps between distinct subspaces are controlled probabilistically.
- Quantum lower bound: Accurate estimates of Tr(P_jσ_i) for every projector P_j determine the hidden subspace index, forcing quantum mutual information Ω(...) and many copies.The proof bounds the information carried by T copies using von Neumann entropy and the eigenvalue structure of the constructed states.
- Matching cases: A promise-gap version admits a matching upper bound using O(...) copies, whereas the paper identifies its general lower bounds as the best currently known.The promise distinguishes whether each measurement acceptance probability is at least c_i or at most c_i − ε.
7 Open Problems
The paper identifies open problems concerning tighter sample-complexity bounds, experimentally friendlier measurements, computational efficiency, and further applications of shadow tomography.
- Tight Bounds: The authors conjecture that the current sample-complexity upper bound is far from tight and ask whether stronger lower bounds can be proved.They specifically ask whether complexity can be independent of D and whether any lower bound of the form ω(log M) is possible.
- Shadow Tomography with Restricted Kinds of Measurements: The procedure’s experimental drawbacks include collective measurements, non-demolition measurements, and implementation requirements beyond amplified measurements.It requires collective measurements on roughly log D/ε^2 copies and either maintains states across many sequential measurements or uses extremely long circuits.
- Computational Efficiency: The paper asks whether shadow tomography can be made computationally efficient while respecting input-loading, measurement-application, and output-size obstacles.It estimates the procedure’s complexity as eO(ML)+D^O(log log D), while noting Brandão et al.’s alternative approach and output-circuit formulation.
- Computational Efficiency: The authors propose restricting measurements to uniform quantum algorithms and define hyperefficient shadow tomography as producing an approximating circuit in poly(log M, log D, 1/ε) time.In the classical case, such a circuit can hardwire polynomially many samples and return empirical means for each measurement index.
- Computational Efficiency: Hyperefficient shadow tomography would imply BQP/qpoly = BQP/poly and make quantum copy-protected software impossible.The paper also notes a quantum oracle relative to which hyperefficient shadow tomography is impossible.
- Applications: Further open directions include stabilizer measurements, low-dimensional matrix product states, more than two outcomes, gentle search, alternative norms, and applications beyond those already identified.The paper cites quantum money, software, advice, and communication protocols as existing applications and seeks additional uses in quantum information theory and possibly experiment.