Optimal algorithms for learning quantum phase states
share
We analyze the complexity of learning n-qubit quantum phase states. A degree-d phase state is defined as a superposition of all 2^n 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 Θ(n^d) if we allow separable measurements and Θ(n^d-1) if we allow entangled measurements. Our learning algorithm based on separable measurements has runtime (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 𝔽_2 representation (with sample complexity O(2^d sn)), f has Fourier-degree-t (with sample complexity O(2^2t)), and learning quadratic phase states with ε-global depolarizing noise (with sample complexity O(n^1+ε)). These learning algorithms give us a procedure to learn the diagonal unitaries of the Clifford hierarchy and IQP circuits.
READ FULL TEXT