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

Understand

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.

• We construct a classification problem defined by a noiseless shallow quantum circuit and rigorously prove that any classical neural network with bounded connectivity requires logarithmic depth to output correctly with a larger-than-exponentially-small probability.
• 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.