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.

我们研究了基于浅层电路的经典和量子监督学习模型之间的量子经典分离，并在有和无噪声的情况下进行了研究。我们构建了一个由无噪声的浅层量子电路定义的分类问题，并严格证明了任何有界连接性的经典神经网络需要对数深度才能以超指数小的概率正确输出。这种无条件下最接近最优的量子经典分离源自区分量子电路和它们的经典对应物之间的量子非局域性属性。我们进一步基于退极化噪声模型推导了体现这种分离的近期量子设备的噪声阈值。我们证明了如果噪声强度相对于系统大小的逆多项式被上界限制，则这种分离将持续存在，如果噪声强度大于逆对数多项式函数，则会消失。此外，对于具有恒定噪声强度的量子设备，我们证明了独立于指定学习模型的电路结构，任何由浅层克里福德电路定义的分类任务都不存在超多项式的经典 - 量子分离。