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

arXiv: https://arxiv.org/abs/2405.00770 · HTML: https://mlsanity.com/paper/2405.00770/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 73 references that are in the map.
- First posted on arXiv 1 May 2024.

## Builds on (most cited first, 18 of 18)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Segment Anything](https://mlsanity.com/paper/2304.02643/) (2023)
- [Sequence to Sequence Learning with Neural Networks](https://mlsanity.com/paper/1409.3215/) (2014)
- [Variational Quantum Algorithms](https://mlsanity.com/paper/2012.09265/) (2020)
- [Supervised learning with quantum enhanced feature spaces](https://mlsanity.com/paper/1804.11326/) (2018)
- [Power of data in quantum machine learning](https://mlsanity.com/paper/2011.01938/) (2020)
- [Quantum Machine Learning](https://mlsanity.com/paper/1611.09347/) (2016)
- [A rigorous and robust quantum speed-up in supervised machine learning](https://mlsanity.com/paper/2010.02174/) (2020)
- [Noise-Induced Barren Plateaus in Variational Quantum Algorithms](https://mlsanity.com/paper/2007.14384/) (2020)
- [Information-theoretic bounds on quantum advantage in machine learning](https://mlsanity.com/paper/2101.02464/) (2021)
- [Quantum machine learning: a classical perspective](https://mlsanity.com/paper/1707.08561/) (2017)
- [Quantum-enhanced machine learning](https://mlsanity.com/paper/1610.08251/) (2016)
- [Enhancing Generative Models via Quantum Correlations](https://mlsanity.com/paper/2101.08354/) (2021)
- [Experimental quantum adversarial learning with programmable superconducting qubits](https://mlsanity.com/paper/2204.01738/) (2022)
- [On establishing learning separations between classical and quantum machine learning with classical data](https://mlsanity.com/paper/2208.06339/) (2022)
- [Can Error Mitigation Improve Trainability of Noisy Variational Quantum Algorithms?](https://mlsanity.com/paper/2109.01051/) (2021)
- [Quantum Neural Network Classifiers: A Tutorial](https://mlsanity.com/paper/2206.02806/) (2022)
- [The Complexity of NISQ](https://mlsanity.com/paper/2210.07234/) (2022)

## Built on by (most cited first, 3 of 3)

- [Quantum delegated and federated learning via quantum homomorphic encryption](https://mlsanity.com/paper/2409.19359/) (2024)
- [Entanglement-induced provable and robust quantum learning advantages](https://mlsanity.com/paper/2410.03094/) (2024)
- [Probing many-body Bell correlation depth with superconducting qubits](https://mlsanity.com/paper/2406.17841/) (2024)

## Abstract (arXiv)

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. 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.