Recent theoretical results in quantum machine learning have demonstrated a
general trade-off between the expressive power of quantum neural networks
(QNNs) and their trainability; as a corollary of these results, practical
exponential separations in expressive power over classical machine learning
models are believed to be infeasible as such QNNs take a time to train that is
exponential in the model size. We here circumvent these negative results by
constructing a hierarchy of efficiently trainable QNNs that exhibit
unconditionally provable, polynomial memory separations of arbitrary constant
degree over classical neural networks in performing a classical sequence
modeling task. Furthermore, each unit cell of the introduced class of QNNs is
computationally efficient, implementable in constant time on a quantum device.
The classical networks we prove a separation over include well-known examples
such as recurrent neural networks and Transformers. We show that quantum
contextuality is the source of the expressivity separation, suggesting that
other classical sequence learning problems with long-time correlations may be a
regime where practical advantages in quantum machine learning may exist.

最近的量子机器学习的理论结果表明了量子神经网络（QNNs）的表达能力和可训练性之间的一般性权衡；作为这些结果的推论，实际中在表达能力上超过经典机器学习模型的指数级差异被认为是不可行的，因为这样的 QNNs 训练所需的时间与模型大小的指数成正比。我们通过构建一种层次化的可高效训练的 QNNs，成功地绕过了这些负面结果，其在经典序列建模任务中展示了无条件可证的多项式内存分离性能，而且所引入的 QNNs 的每个单元均在量子设备上能够以恒定的时间进行计算。我们证明了这种分离性能在经典神经网络类型中成立，包括循环神经网络和 Transformer 等众所周知的网络。我们展示了量子背景的特殊性是导致表达能力分离的根源，这表明在具有长时间相关性的其他经典序列学习问题中，量子机器学习可能存在实际上的优势。