One T Gate Makes Distribution Learning Hard

The task of learning a probability distribution from samples is ubiquitous across the natural sciences. The output distributions of local quantum circuits are of central importance in both quantum advantage proposals and a variety of quantum machine learning algorithms. In this work, we extensively characterize the learnability of output distributions of local quantum circuits. Firstly, we contrast learnability with simulatability by showing that Clifford circuit output distributions are efficiently learnable, while the injection of a single T gate renders the density modeling task hard for any depth d 1/4 n & omega;o1 thorn . We further show that the task of generative modeling universal quantum circuits at any depth d 1/4 n & omega;o1 thorn is hard for any learning algorithm, classical or quantum, and that for statistical query algorithms, even depth d 1/4 & omega;1/2logon thorn ⠂ Clifford circuits are hard to learn. Our results show that one cannot use the output distributions of local quantum circuits to provide a separation between the power of quantum and classical generative modeling algorithms, and therefore provide evidence against quantum advantages for practically relevant probabilistic modeling tasks.

Automated summary

The task of learning a probability distribution from samples is common in the natural sciences. This study extensively characterizes the learnability of output distributions from local quantum circuits. The results show that Clifford circuit output distributions are efficiently learnable, but the injection of a single T gate makes density modeling task difficult. Additionally, generative modeling of universal quantum circuits is hard for any learning algorithm, classical or quantum, indicating no quantum advantage for probabilistic modeling tasks.