Optimal algorithms for learning quantum phase states

We analyze the complexity of learning n-qubit quantum phase states. A degree-d phase state is defined as a superposition of all 2n basis vectors x with amplitudes proportional to (-1)f(x), where f is a degree-d Boolean polynomial over n variables. We show that the sample complexity of learning an unknown degree-d phase state is Theta(nd) if we allow separable measurements and Theta(nd-1) if we allow entangled measurements. Our learning algorithm based on separable measurements has runtime textsfpoly(n) (for constant d) and is well-suited for near-term demonstrations as it requires only single-qubit measurements in the Pauli X and Z bases. We show similar bounds on the sample complexity for learning generalized phase states with complex-valued amplitudes. We further consider learning phase states when f has sparsity-s, degree-d in its mathbbF2 representation (with sample complexity O(2d sn)), f has Fourier-degree-t (with sample complexity O(22t)), and learning quadratic phase states with varepsilon-global depolarizing noise (with sample complexity O(n1+varepsilon)). These learning algorithms give us a procedure to learn the diagonal unitaries of the Clifford hierarchy and IQP~circuits.