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 2nbasis 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 Θ(nd) if we allow separable measurements and Θ(nd-1) if we allow entangled measurements. Our learning algorithm based on separable measurements has runtime poly(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 F2 representation (with sample complexity O(2dsn)), f has Fourier-degree-T (with sample complexity O(22t)), and learning quadratic phase states with ϵ-global depolarizing noise (with sample complexity O(n1+ϵ)). These learning algorithms give us a procedure to learn the diagonal unitaries of the Clifford hierarchy and IQP circuits.