2022/08/16 by Arunachalam, Srinivasan, Bravyi, Sergey, Dutt, Arkopal +1 · 4 citations
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Physics (quant-ph)
paper · doi:10.48550/arxiv.2208.07851
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 Θ(nd) if we allow separable measurements and Θ(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 ε-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.