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

arXiv:2405.00770v1 Announce Type: cross
Abstract: 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 …

abstract arxiv circuits classification construct cs.cc cs.lg network neural network prove quant-ph quantum study supervised learning type