Before revision:  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) .
After revision:  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 -- prohibiting sample reuse. Then, after introducing a Fourier expansion through Pauli's operators, we study learning with respect to an infinite class of quantum measurements whose operator's Fourier spectrum is concentrated on low degree terms. We propose a quantum low-degree learning algorithm which is a quantum counterpart of (Linial et al., 1993) .