# Regensburg 2022 – wissenschaftliches Programm

## Bereiche | Tage | Auswahl | Suche | Aktualisierungen | Downloads | Hilfe

# QI: Fachverband Quanteninformation

## QI 12: Quantum Computing and Algorithms

### QI 12.10: Vortrag

### Donnerstag, 8. September 2022, 17:30–17:45, H8

A single T-gate makes distribution learning hard — •Marcel Hinsche^{1}, Marios Ioannou^{1}, Alexander Nietner^{1}, Jonas Haferkamp^{1}, Yihui Quek^{1}, Dominik Hangleiter^{2}, Jean-Pierre Seifert^{3}, Jens Eisert^{1,4,5}, and Ryan Sweke^{1} — ^{1}FU Berlin, 14195 Berlin, Germany — ^{2}University of Maryland, MD 20742, USA — ^{3}TU Berlin, 10587 Berlin, Germany — ^{4}Helmholtz-Zentrum Berlin, 14109 Berlin, Germany — ^{5}Fraunhofer 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.