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

05/22/2023

∙

by   Sabee Grewal, et al.

∙

0

∙

share

We give an algorithm that efficiently learns a quantum state prepared by Clifford gates and O(log(n)) non-Clifford gates. Specifically, for an n-qubit state |ψ⟩ prepared with at most t non-Clifford gates, we show that 𝗉𝗈𝗅𝗒(n,2^t,1/ϵ) time and copies of |ψ⟩ suffice to learn |ψ⟩ to trace distance at most ϵ. This result follows as a special case of an algorithm for learning states with 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.