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

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 mathsfpoly(n,2t,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 2k Pauli operators. We also develop an efficient property testing algorithm for stabilizer dimension, which may be of independent interest.