Prospects for quantum advantage in machine learning from the representability of functions

Quantum machine learning (QML) is recognized as a promising approach to harness quantum computing for learning tasks [1-3]. As with all quantum algorithms, a central question is whether QML holds potential for quantum advantage [4-7] over classical computing. The counter-narrative to quantum advantage is dequantization, where upon close inspection certain quantum algorithms yield no benefit over classical counterparts, as one can classically solve the task at hand. Dequantization of quantum algorithms for machine learning, in particular, has seen a surge of interest in recent years, leaving few claims of quantum advantage unchallenged [8-12]. While QML models for classical data can be studied from several perspectives, significant theoretical developments have emerged from investigating the function families that parametrized quantum circuits (PQCs) can give rise to [8, 10, 13-16]. Characterizing the functional forms arising from PQCs allows us to delineate the boundaries of quantum learning and guide the search for advantage.