A Low Degree Learning Algorithm for Quantum Data via Quantum Fourier

Advances in quantum information processing compel us to explore learning from quantum data. We consider a classical-quantum learning problem in which the samples are quantum states with classical labels and the predictors are quantum measurements. To study this problem, we introduce a quantum counterpart of PAC framework. We argue that the major difficulties arising from the quantum nature of the problem are the compatibility of the measurements and the no-cloning principle. With that in mind, we establish bounds on the quantum sample complexity for a family of quantum concept classes called concentrated measurements. Using a quantum Fourier expansion on qubits, we propose a quantum low-degree learning algorithm which is a quantum counterpart of (Linial et al., 1993).