Regensburg 2022 – scientific programme
Parts | Days | Selection | Search | Updates | Downloads | Help
QI: Fachverband Quanteninformation
QI 12: Quantum Computing and Algorithms
QI 12.10: Talk
Thursday, September 8, 2022, 17:30–17:45, H8
A single T-gate makes distribution learning hard — •Marcel Hinsche1, Marios Ioannou1, Alexander Nietner1, Jonas Haferkamp1, Yihui Quek1, Dominik Hangleiter2, Jean-Pierre Seifert3, Jens Eisert1,4,5, and Ryan Sweke1 — 1FU Berlin, 14195 Berlin, Germany — 2University of Maryland, MD 20742, USA — 3TU Berlin, 10587 Berlin, Germany — 4Helmholtz-Zentrum Berlin, 14109 Berlin, Germany — 5Fraunhofer Heinrich Hertz Institute, 10587 Berlin, Germany
The task of probabilistic modelling is at the core of many practical applications. As such, the efficient learnability of natural classes of probability distributions is a question of both fundamental and practical interest. The output distributions of local quantum circuits is a particularly interesting class of distributions, of key importance both to quantum advantage proposals and a variety of quantum machine learning algorithms. In this work, we provide an extensive characterization of the learnability of the output distributions of local quantum circuits. We prove that the density modelling problem can be solved efficiently in case of Clifford circuits, while adding a single T gate renders the task computationally hard. Evidently, the simulability of this class does not imply its learnability. Next we show that the generative modelling task is hard for depth nΩ(1) universal local quantum circuits for both, classical and quantum algorithms. Finally we obtain a similar hardness result already for depth ω(log(n)) local Clifford circuits when restricting to practically relevant learning algorithms, such hybrid-quantum classical algorithms.