Prospects for quantum advantage in machine learning from the representability of functions
This work provides a conceptual map for researchers in quantum machine learning to navigate opportunities for quantum advantage, though it is incremental in clarifying existing simulation pathways.
The paper tackles the challenge of identifying quantum advantage in machine learning by introducing a framework that links quantum circuit properties to the functions they can learn, showing how factors like depth and gate count affect classical simulability and revealing distinctions between fully simulatable, classically tractable, and robustly quantum models.
Demonstrating quantum advantage in machine learning tasks requires navigating a complex landscape of proposed models and algorithms. To bring clarity to this search, we introduce a framework that connects the structure of parametrized quantum circuits to the mathematical nature of the functions they can actually learn. Within this framework, we show how fundamental properties, like circuit depth and non-Clifford gate count, directly determine whether a model's output leads to efficient classical simulation or surrogation. We argue that this analysis uncovers common pathways to dequantization that underlie many existing simulation methods. More importantly, it reveals critical distinctions between models that are fully simulatable, those whose function space is classically tractable, and those that remain robustly quantum. This perspective provides a conceptual map of this landscape, clarifying how different models relate to classical simulability and pointing to where opportunities for quantum advantage may lie.