There is currently a large interest in understanding the potential advantages quantum devices can offer for probabilistic modelling. In this work we investigate, within two different oracle models, the probably approximately correct (PAC) learnability of quantum circuit Born machines, i.e., the output distributions of local quantum circuits. We first show a negative result, namely, that the output distributions of super-logarithmic depth Clifford circuits are not sample-efficiently learnable in the statistical query model, i.e., when given query access to empirical expectation values of bounded functions over the sample space. This immediately implies the hardness, for both quantum and classical algorithms, of learning from statistical queries the output distributions of local quantum circuits using any gate set which includes the Clifford group. As many practical generative modelling algorithms use statistical queries -- including those for training quantum circuit Born machines -- our result is broadly applicable and strongly limits the possibility of a meaningful quantum advantage for learning the output distributions of local quantum circuits. As a positive result, we show that in a more powerful oracle model, namely when directly given access to samples, the output distributions of local Clifford circuits are computationally efficiently PAC learnable by a classical learner. Our results are equally applicable to the problems of learning an algorithm for generating samples from the target distribution (generative modelling) and learning an algorithm for evaluating its probabilities (density modelling). They provide the first rigorous insights into the learnability of output distributions of local quantum circuits from the probabilistic modelling perspective.\

}, url = {https://arxiv.org/abs/2110.05517}, author = {Marcel Hinsche and Marios Ioannou and Alexander Nietner and Jonas Haferkamp and Yihui Quek and Dominik Hangleiter and Jean-Pierre Seifert and Jens Eisert and Ryan Sweke} } @article {2921, title = {Resource theory of quantum uncomplexity}, year = {2021}, month = {10/21/2021}, abstract = {Quantum complexity is emerging as a key property of many-body systems, including black holes, topological materials, and early quantum computers. A state\&$\#$39;s complexity quantifies the number of computational gates required to prepare the state from a simple tensor product. The greater a state\&$\#$39;s distance from maximal complexity, or {\textquoteleft}{\textquoteleft}uncomplexity,\&$\#$39;\&$\#$39; the more useful the state is as input to a quantum computation. Separately, resource theories -- simple models for agents subject to constraints -- are burgeoning in quantum information theory. We unite the two domains, confirming Brown and Susskind\&$\#$39;s conjecture that a resource theory of uncomplexity can be defined. The allowed operations, fuzzy operations, are slightly random implementations of two-qubit gates chosen by an agent. We formalize two operational tasks, uncomplexity extraction and expenditure. Their optimal efficiencies depend on an entropy that we engineer to reflect complexity. We also present two monotones, uncomplexity measures that decline monotonically under fuzzy operations, in certain regimes. This work unleashes on many-body complexity the resource-theory toolkit from quantum information theory.

}, url = {https://arxiv.org/abs/2110.11371}, author = {Nicole Yunger Halpern and Naga B. T. Kothakonda and Jonas Haferkamp and Anthony Munson and Jens Eisert and Philippe Faist} }