Arbitrary Polynomial Separations in Trainable Quantum Machine Learning
This work addresses the problem of overcoming theoretical limitations in quantum machine learning for researchers, by demonstrating that polynomial separations are feasible despite previous negative results, though it is incremental in showing specific separations rather than broad exponential gains.
The authors tackled the trade-off between expressive power and trainability in quantum neural networks (QNNs) by constructing a hierarchy of efficiently trainable QNNs that achieve unconditionally provable, polynomial memory separations of arbitrary constant degree over classical neural networks, including Transformers, in a classical sequence modeling task, with each unit cell having constant gate complexity.
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.