Quantum-Classical Separations in Shallow-Circuit-Based Learning with and without Noises

Hefei National Laboratory, Hefei 230088, China We study quantum-classical separations between classical and quantum supervised learning models based on constant depth (i.e., shallow) circuits, in scenarios with and without noises. This unconditional near-optimal quantum-classical separation originates from the quantum nonlocality property that distinguishes quantum circuits from their classical counterparts. We further derive the noise thresholds for demonstrating such a separation on near-term quantum devices under the depolarization noise model. We prove that this separation will persist if the noise strength is upper bounded by an inverse polynomial with respect to the system size, and vanish if the noise strength is greater than an inverse polylogarithmic function. In addition, for quantum devices with constant noise strength, we prove that no super-polynomial classical-quantum separation exists for any classification task defined by shallow Clifford circuits, independent of the structures of the circuits that specify the learning models. Quantum machine learning studies the interplay between relation problem, obtaining a separation originating from the machine learning and quantum physics [1-6]. In recent years, classical hardness of simulating the intrinsic nonlocality property a number of quantum learning algorithms have been proposed of quantum mechanics. In particular, it is proved that a [7-19], which may offer potential quantum advantages shallow quantum circuit can solve a relation problem such that over their classical counterparts.