Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates

Quantum 9, 1907 (2025).

https://doi.org/10.22331/q-2025-11-06-1907

We give a pair of algorithms that efficiently learn a quantum state prepared by Clifford gates and $O(log n)$ non-Clifford gates. Specifically, for an $n$-qubit state $|psirangle$ prepared with at most $t$ non-Clifford gates, our algorithms use $mathsf{poly}(n,2^t,1/varepsilon)$ time and copies of $|psirangle$ to learn $|psirangle$ to trace distance at most $varepsilon$.
The first algorithm for this task is more efficient, but requires entangled measurements across two copies of $|psirangle$. The second algorithm uses only single-copy measurements at the cost of polynomial factors in runtime and sample complexity. Our algorithms more generally learn any state with sufficiently large stabilizer dimension, where a quantum state has stabilizer dimension $k$ if it is stabilized by an abelian group of $2^k$ Pauli operators. We also develop an efficient property testing algorithm for stabilizer dimension, which may be of independent interest.