Shadow bootstrapping: Nearly minimal-setting pure-state tomography with shallow Clifford measurements

Abstract

We present a pure-state tomography algorithm that uses a nearly minimal number of measurement settings while achieving optimal sample complexity with nonadaptive single-copy shallow Clifford measurements. For an arbitrary $n$-qubit pure state $|\psi ⟩\in {\mathbb{C}}^d$, where $d=2^n$, the algorithm uses $O(d/\epsilon )$ copies and $\tilde{O}(1)$ measurement settings to output a state vector $|\hat{\psi }⟩$ satisfying $1-|⟨\psi |\hat{\psi }⟩{|}^2\le \epsilon$ with high probability. Each measurement is implemented by a Clifford circuit of depth $O(\log n)$. Reusing each measurement setting allows the data to be stored compactly as per-basis outcome histograms. Given these histograms, classical post-processing runs in $\tilde{O}(d)$ time. Our key technique, \textit{shadow bootstrapping}, uses the current estimate to reduce the variance of subsequent residual estimation, enabling progressively more accurate reconstruction with only a constant number of new measurement settings per stage.