Before revision:  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:  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 learning algorithm and show that the quantum sample complexity depends on the ``compatibility structure" of such measurement classes -- the more compatible the class is, the lower the quantum sample complexity will be. We further introduce k-junta measurements as a special class of low-depth quantum circuits whose Fourier spectrum is concentrated on low degrees .