Speaker: Jens Eisert
Title: A Single T-Gate Makes Quantum Distribution Learning Hard
Abstract: There has been substantial excitement recently in identifying tasks for which quantum devices could possibly outperform classical devices. Recent experimental implementations on random circuit sampling have provided strong evidence that quantum devices can outperform classical computers on paradigmatic tasks [1]. Also, quantum simulators seem to reach regimes out of scope for classical computers. These developments invite further studies to see what further applications of quantum devices could be found. Notions of quantum-assisted machine learning are seen as candidates for this. In this talk, we will have a look at such notions of quantum-assisted machine learning, driven by the hope that quantum algorithms could fare better than classical ones in instances of learning tasks. These advantages could refer to computational speedups, but also to better generalization and other figures of merit. We will discuss the comparative power of classical and quantum learners for generative modelling within the probably approximately correct framework, for which we prove a separation between the quantum and classical settings [2, 3]. In the light of new findings on the PAC learnability of the output distributions of local quantum circuits, we will discuss how much structure is actually expected to be required to hope for quantum advantages in quantum-assisted machine learning [4]. We prove that the injection of a single T-gate into Clifford circuits renders the task of learning evaluators from samples infeasible in polynomial time. This is in stark contrast to the case of Clifford circuits for which we provide an efficient learning algorithm based on Gaussian elimination [5]. This work will provide a roadmap of what next steps are to be taken for work in quantum machine learning, and will flesh out the potential and limitations of quantum probabilistic modelling.

[1] Computational advantage of quantum random sampling, D. Hangleiter, J. Eisert, review for Rev. Mod. Phys., arXiv:2206.04079 (2022).

[2] On the quantum versus classical learnability of discrete distributions, R. Sweke, J.-P. Seifert, D. Hangleiter, J. Eisert, Quantum 5, 417 (2021).

[3] A super-polynomial quantum-classical separation for density modelling, N. Pirnay, R. Sweke, J. Eisert, and J.-P. Seifert, in preparation (2022).

[4] Learnability of the output distributions of local quantum circuits, M. Hinsche, M. Ioannou, A. Nietner, J. Haferkamp, Y. Quek, D. Hangleiter, J.-P. Seifert, J. Eisert, R. Sweke, arXiv:2110.05517 (2021).

[5] A single T-gate makes distribution learning hard, M. Hinsche, M. Ioannou, A. Nietner, J. Haferkamp, Y. Quek, D. Hangleiter, J.-P. Seifert, J. Eisert, R. Sweke, arXiv:2207.03140 (2022).