Arbitrary Polynomial Separations in Trainable Quantum Machine Learning

作者：Eric R. Anschuetz, Xun Gao · 发表于：Quantum · 年份：2026 · DOI：10.22331/q-2026-01-20-1976 · 被引用次数：3 · 研究领域：Quantum Computing Algorithms and Architecture、Quantum Information and Cryptography、Computational Physics and Python Applications

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—including state-of-the-art models, such as Transformers—in performing a classical sequence modeling task. This construction is also computationally efficient, as each unit cell of the introduced class of QNNs only has constant gate complexity. We show that contextuality—informally, a quantitative notion of semantic ambiguity—is the source of the expressivity separation, suggesting that other learning tasks with this property may be a natural setting for the use of quantum learning algorithms.