Simple Algorithm
Quantum Computing · Rydberg State · 28 min

Quantum State Tomography

Reconstructing a state from measurement statistics.

A density matrix is not an observable: no single measurement reveals it. Tomography reconstructs ρ\rho from the statistics of many measurements on many copies. How many copies it takes is one of the sharpest quantitative results in quantum information, with an exponential price for many qubits and some remarkable ways around it.

What you’ll learn

  • Define informational completeness and reconstruct a qubit from Pauli or SIC-POVM statistics by linear inversion.
  • Quantify shot noise and state the optimal sample complexities: Θ(d2/ε2)\Theta(d^2/\varepsilon^2) copies with collective and Θ(d3/ε2)\Theta(d^3/\varepsilon^2) with single-copy measurements.
  • Turn raw estimates into physical states (projection, maximum likelihood) and recognize their pitfalls.
  • Use classical shadows to predict many properties from few randomized measurements, with explicit sample bounds.

Informationally complete measurements

A density matrix on Cd\C^d has d2−1d^2-1 real parameters. A measurement {Ek}\{E_k\} yields only the numbers pk=Tr⁡(Ekρ)p_k = \Tr(E_k\rho), so it can pin down ρ\rho only if these numbers determine it uniquely.

For nn qubits (d=2nd = 2^n), the Pauli strings P∈{I,X,Y,Z}⊗nP\in\{\id,X,Y,Z\}^{\otimes n} form an orthogonal operator basis with Tr⁡(PQ)=2nδPQ\Tr(PQ) = 2^n\delta_{PQ}, so every state is fixed by its Pauli expectation values:

ρ=12n∑P∈{I,X,Y,Z}⊗nTr⁡(Pρ) P\rho = \frac{1}{2^n}\sum_{P\in\{\id,X,Y,Z\}^{\otimes n}}\Tr(P\rho)\,P
Measuring every qubit in one of the XX, YY, ZZ bases gives 3n3^n measurement settings. Each setting yields a distribution over 2n2^n outcomes, which also gives every Pauli string obtained by replacing some letters with I\id (just ignore those bits). So 3n3^n settings determine all 4n4^n expectation values.

For one qubit this is ρ=12(I+⟨X⟩X+⟨Y⟩Y+⟨Z⟩Z)\rho = \tfrac12\big(\id+\expval{X}X+\expval{Y}Y+\expval{Z}Z\big): three bases suffice. Reconstruct a mystery state yourself.

Think first Write down your estimate r⃗^\hat{\vec r}. What should it be close to, and how close?

The prepared state has θ=π/3\theta = \pi/3, φ=π/4\varphi = \pi/4, so r⃗=(sin⁡θcos⁡φ, sin⁡θsin⁡φ, cos⁡θ)≈(0.61, 0.61, 0.50)\vec r = (\sin\theta\cos\varphi,\ \sin\theta\sin\varphi,\ \cos\theta)\approx(0.61,\ 0.61,\ 0.50). Each component should typically land within about one standard error (±0.03\pm0.03) and almost always within ±0.1\pm0.1. Because this state is pure, ∣r⃗^∣\abs{\hat{\vec r}} will often come out slightly larger than 1: an unphysical estimate, a problem fixed in step 3.

How many copies?

Each run yields one outcome, so every estimate carries shot noise. Start with a single Pauli observable PP, estimated from NN runs:

DerivationShot noise for one expectation value
  1. μ^=1N∑t=1Nxt,E[μ^]=⟨P⟩\hat\mu = \frac1N\sum_{t=1}^Nx_t,\qquad \mathbb{E}[\hat\mu] = \expval{P}

    The outcomes xt∈{±1}x_t\in\{\pm1\} are i.i.d. with mean ⟨P⟩=Tr⁡(Pρ)\expval{P} = \Tr(P\rho). Use their sample mean:

  2. Var⁡[μ^]=1−⟨P⟩2N\operatorname{Var}[\hat\mu] = \frac{1-\expval{P}^2}{N}

    Since xt2=1x_t^2 = 1, each outcome has variance 1−⟨P⟩21-\expval{P}^2:

  3. Pr⁡[∣μ^−⟨P⟩∣≥ε]≤2e−Nε2/2\Pr\big[\abs{\hat\mu-\expval{P}}\ge\varepsilon\big]\le2e^{-N\varepsilon^2/2}

    Hoeffding's inequality for variables in [−1,1][-1,1] gives an exponential tail:

  4. N=2ε2ln⁡2MδN = \frac{2}{\varepsilon^2}\ln\frac{2M}{\delta}

    A union bound over MM observables: precision costs 1/ε21/\varepsilon^2, while the number of observables costs only log⁡M\log M. With this many shots per observable, all MM estimates are within ±ε\pm\varepsilon with probability at least 1−δ1-\delta:

Predict before you look

You want the standard error of your estimate of ⟨Z⟩≈0\expval{Z}\approx0 to be 0.010.01. How many shots do you need?

Show the answer

10000 shots

The standard error is (1−⟨Z⟩2)/N=1/N\sqrt{(1-\expval{Z}^2)/N} = 1/\sqrt N at ⟨Z⟩=0\expval{Z} = 0, so N=1/0.012=104N = 1/0.01^2 = 10^4. Halving the error costs four times as many shots.

Full tomography must estimate all d2−1d^2-1 parameters at once, and the measurement model changes the answer qualitatively:

Measurements allowedCopies for trace-distance error ε\varepsilon, full rankWhat it takes
CollectiveΘ(d2/ε2)\Theta(d^2/\varepsilon^2)a quantum memory holding all copies; Schur–Weyl-based measurements
Single-copy, adaptive or notΘ(d3/ε2)\Theta(d^3/\varepsilon^2)one copy at a time, e.g. random-basis measurements
Local Pauli bases on nn qubitsexponential in nn3n3^n settings just to be informationally complete
Here d=2nd = 2^n. Even the optimal rates are exponential in the number of qubits: full tomography is a small-system tool.

From numbers to a physical state

Linear inversion is unbiased, but with finite data it can return an operator with negative eigenvalues: for a nearly pure qubit, r⃗^\hat{\vec r} pokes outside the Bloch ball about half the time. Two standard repairs:

Check your understanding

Linear inversion on a qubit returns r⃗^=(0.6, 0, 0.9)\hat{\vec r} = (0.6,\,0,\,0.9). Which state does the Frobenius-norm projection return?

  1. r⃗^\hat{\vec r} itself: linear inversion is unbiased, so no correction is needed
  2. (0.6, 0, 0.8)(0.6,\,0,\,0.8), obtained by shrinking the largest component
  3. r⃗^/∣r⃗^∣≈(0.55, 0, 0.83)\hat{\vec r}/\abs{\hat{\vec r}}\approx(0.55,\,0,\,0.83), the radial projection onto the sphere
  4. I/2\id/2, because the estimate is unphysical
Show the answer

C. r⃗^/∣r⃗^∣≈(0.55, 0, 0.83)\hat{\vec r}/\abs{\hat{\vec r}}\approx(0.55,\,0,\,0.83), the radial projection onto the sphere

For qubits ∥ρ−σ∥F2=12∣r⃗−s⃗∣2\norm{\rho-\sigma}_F^2 = \tfrac12\abs{\vec r-\vec s}^2, so the closest physical state is the closest point of the ball: the radial projection, since ∣r⃗^∣=1.17≈1.08\abs{\hat{\vec r}} = \sqrt{1.17}\approx1.08. In eigenvalue language, μ=12(1±1.08)≈(1.04, −0.04)\mu = \tfrac12(1\pm1.08)\approx(1.04,\,-0.04) becomes (1, 0)(1,\,0): the estimate is projected to a pure state.

Classical shadows: predicting without reconstructing

Often you do not need ρ\rho at all, only MM numbers Tr⁡(Oiρ)\Tr(O_i\rho): energies, fidelities, correlators. Huang, Kueng & Preskill (2020) showed that a few randomized measurements suffice, at a cost logarithmic in MM.

DerivationThe estimator (random Pauli bases)
  1. record (U,b),U=U1⊗⋯⊗Un,b∈{0,1}n\text{record } (U,b),\qquad U = U_1\otimes\cdots\otimes U_n,\quad b\in\{0,1\}^n

    In each round, measure every qubit jj in a uniformly random basis XX, YY or ZZ; equivalently, apply a random single-qubit Clifford UjU_j and measure in the computational basis. Record the bases and the outcome bits bjb_j.

  2. M(ρ):=E[U†∣b⟩ ⁣⟨b∣U]=ρ+Tr⁡(ρ) I3,M−1(X)=3X−Tr⁡(X) I\mathcal M(\rho) := \mathbb{E}\big[U^\dagger\dyad{b}U\big] = \frac{\rho+\Tr(\rho)\,\id}{3},\qquad \mathcal M^{-1}(X) = 3X-\Tr(X)\,\id

    Averaged over bases and outcomes, one qubit's snapshot U†∣b⟩ ⁣⟨b∣UU^\dagger\dyad{b}U is a depolarized copy of ρ\rho:

  3. ρ^=⨂j=1n(3 Uj†∣bj⟩ ⁣⟨bj∣Uj−I)\hat\rho = \bigotimes_{j=1}^n\Big(3\,U_j^\dagger\dyad{b_j}U_j-\id\Big)

    Invert this channel on the classical record, qubit by qubit. The resulting snapshot is an unbiased estimator, E[ρ^]=ρ\mathbb{E}[\hat\rho] = \rho, even though ρ^\hat\rho itself is not a state:

  4. Estimate each Tr⁡(Oiρ)\Tr(O_i\rho) by a median of means of the numbers Tr⁡(Oiρ^)\Tr(O_i\hat\rho), computed classically from the stored snapshots.

Two features stand out. NN grows only logarithmically with the number of observables, because every snapshot is reused for all of them; and for local observables it does not depend on the number of qubits at all. The Clifford version makes fidelities with pure targets cheap, since Tr⁡(O2)=1\Tr(O^2) = 1 for O=∣ψ⟩ ⁣⟨ψ∣O = \dyad\psi. Huang, Kueng and Preskill also proved that these scalings are close to optimal.

Key takeaways

  • Tomography needs an informationally complete measurement, whose effects span all d2d^2 Hermitian directions; for nn qubits, 3n3^n Pauli settings suffice.
  • Each expectation value costs about 1/ε21/\varepsilon^2 shots. Full-rank tomography costs Θ(d2/ε2)\Theta(d^2/\varepsilon^2) copies with collective and Θ(d3/ε2)\Theta(d^3/\varepsilon^2) with single-copy measurements: exponential in nn either way.
  • Linear inversion can be unphysical; projection or maximum likelihood repairs it, and honest error bars need care and a trusted measurement model.
  • Classical shadows predict MM local properties from O(log⁡M)\order{\log M} randomized snapshots, independently of system size.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

How many measurement settings does standard Pauli tomography of nn qubits use, and why not 4n4^n?

  1. 4n4^n, one per Pauli string
  2. 3n3^n: each setting fixes XX, YY or ZZ on every qubit, and strings containing I\id are read off by ignoring bits
  3. 2n2^n, one per computational basis state
  4. 4n−14^n-1, one per free parameter
Show the answer

B. 3n3^n: each setting fixes XX, YY or ZZ on every qubit, and strings containing I\id are read off by ignoring bits

Measuring every qubit in a chosen Pauli basis gives the joint distribution of all nn outcomes. Marginalizing gives every string obtained by replacing some letters with I\id, so 3n3^n settings cover all 4n4^n strings.

Question 2

Why must an informationally complete POVM on Cd\C^d have at least d2d^2 outcomes?

  1. Its effects must span the d2d^2-dimensional real vector space of Hermitian operators
  2. Each outcome reveals one amplitude, and a dd-dimensional state has d2d^2 amplitudes
  3. Each outcome needs its own copy of the state, and tomography needs d2d^2 copies
  4. It need not: a projective measurement in a well-chosen basis, with dd outcomes, suffices
Show the answer

A. Its effects must span the d2d^2-dimensional real vector space of Hermitian operators

If the span of the EkE_k missed a Hermitian direction Δ\Delta, which is automatically traceless since I=∑kEk\id = \sum_kE_k is in the span, then ρ\rho and ρ+tΔ\rho+t\Delta would give identical statistics. Spanning a d2d^2-dimensional space takes at least d2d^2 vectors.

Question 3

Using random-Pauli classical shadows, you want to estimate M=106M = 10^6 different 2-local observables, each with ∥O∥∞≤1\norm{O}_\infty\le1, to accuracy ε\varepsilon. How does the required number of snapshots scale?

  1. O(M/ε2)\order{M/\varepsilon^2}, one batch of shots per observable
  2. O(4n/ε2)\order{4^n/\varepsilon^2}, because the state must effectively be reconstructed
  3. O(16log⁡M/ε2)\order{16\log M/\varepsilon^2}, independent of the number of qubits nn
  4. O(log⁡M/ε)\order{\log M/\varepsilon}
Show the answer

C. O(16log⁡M/ε2)\order{16\log M/\varepsilon^2}, independent of the number of qubits nn

The shadow norm of a kk-local observable is at most 4k∥O∥∞2=164^k\norm{O}_\infty^2 = 16 for k=2k = 2, and median-of-means gives N=O(16log⁡(M/δ)/ε2)N = \order{16\log(M/\delta)/\varepsilon^2}, with no dependence on nn. Every snapshot is reused for all MM observables.

Question 4

Which statement about tomography of a full-rank dd-dimensional state to trace-distance error ε\varepsilon is correct?

  1. Collective and single-copy measurements both need Θ(d2/ε2)\Theta(d^2/\varepsilon^2) copies
  2. Collective measurements need Θ(d3/ε2)\Theta(d^3/\varepsilon^2) copies and single-copy ones Θ(d2/ε2)\Theta(d^2/\varepsilon^2)
  3. Adaptive single-copy measurements match collective ones at Θ(d2/ε2)\Theta(d^2/\varepsilon^2)
  4. Collective measurements need Θ(d2/ε2)\Theta(d^2/\varepsilon^2) copies; single-copy ones need Θ(d3/ε2)\Theta(d^3/\varepsilon^2), even when chosen adaptively
Show the answer

D. Collective measurements need Θ(d2/ε2)\Theta(d^2/\varepsilon^2) copies; single-copy ones need Θ(d3/ε2)\Theta(d^3/\varepsilon^2), even when chosen adaptively

Measurements entangled across copies (built on Schur–Weyl duality) reach d2/ε2d^2/\varepsilon^2. Without a quantum memory each copy is measured on its own, the optimal rate is d3/ε2d^3/\varepsilon^2, and adaptivity does not close the gap.

Further reading

  • Z. Hradil, "Quantum-state estimation", Physical Review A 55, R1561 (1997).
  • D. Gross, Y.-K. Liu, S. T. Flammia, S. Becker & J. Eisert, "Quantum state tomography via compressed sensing", Physical Review Letters 105, 150401 (2010).
  • J. Haah, A. W. Harrow, Z. Ji, X. Wu & N. Yu, "Sample-optimal tomography of quantum states", IEEE Transactions on Information Theory (2017); R. O'Donnell & J. Wright, "Efficient quantum tomography", STOC (2016).
  • H.-Y. Huang, R. Kueng & J. Preskill, "Predicting many properties of a quantum system from very few measurements", Nature Physics 16, 1050 (2020).
  • J. M. Renes, R. Blume-Kohout, A. J. Scott & C. M. Caves, "Symmetric informationally complete quantum measurements", Journal of Mathematical Physics 45, 2171 (2004).