02013nas a2200277 4500008004100000245008100041210006900122260001300191300001300204490000600217520120300223100002301426700001801449700002001467700002101487700002001508700002001528700001701548700002101565700001401586700001701600700002401617700002001641700001501661856005901676 2022 eng d00aQuantum computational advantage via high-dimensional Gaussian boson sampling0 aQuantum computational advantage via highdimensional Gaussian bos c1/5/2022 aeabi78940 v83 a

A programmable quantum computer based on fiber optics outperforms classical computers with a high level of confidence. Photonics is a promising platform for demonstrating a quantum computational advantage (QCA) by outperforming the most powerful classical supercomputers on a well-defined computational task. Despite this promise, existing proposals and demonstrations face challenges. Experimentally, current implementations of Gaussian boson sampling (GBS) lack programmability or have prohibitive loss rates. Theoretically, there is a comparative lack of rigorous evidence for the classical hardness of GBS. In this work, we make progress in improving both the theoretical evidence and experimental prospects. We provide evidence for the hardness of GBS, comparable to the strongest theoretical proposals for QCA. We also propose a QCA architecture we call high-dimensional GBS, which is programmable and can be implemented with low loss using few optical components. We show that particular algorithms for simulating GBS are outperformed by high-dimensional GBS experiments at modest system sizes. This work thus opens the path to demonstrating QCA with programmable photonic processors.

1 aDeshpande, Abhinav1 aMehta, Arthur1 aVincent, Trevor1 aQuesada, Nicolas1 aHinsche, Marcel1 aIoannou, Marios1 aMadsen, Lars1 aLavoie, Jonathan1 aQi, Haoyu1 aEisert, Jens1 aHangleiter, Dominik1 aFefferman, Bill1 aDhand, Ish uhttps://www.science.org/doi/abs/10.1126/sciadv.abi789402255nas a2200205 4500008004100000245005300041210005000094260001300144520167300157100002001830700002001850700002301870700002101893700001601914700002401930700002501954700001701979700001601996856003702012 2022 eng d00aA single T-gate makes distribution learning hard0 asingle Tgate makes distribution learning hard c7/7/20223 a

The task of learning a probability distribution from samples is ubiquitous across the natural sciences. The output distributions of local quantum circuits form 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. Our first result yields insight into the relationship between the efficient learnability and the efficient simulatability of these distributions. Specifically, we prove that the density modelling problem associated with Clifford circuits can be efficiently solved, while for depth d=nΩ(1) circuits the injection of a single T-gate into the circuit renders this problem hard. This result shows that efficient simulatability does not imply efficient learnability. Our second set of results provides insight into the potential and limitations of quantum generative modelling algorithms. We first show that the generative modelling problem associated with depth d=nΩ(1) local quantum circuits is hard for any learning algorithm, classical or quantum. As a consequence, one cannot use a quantum algorithm to gain a practical advantage for this task. We then show that, for a wide variety of the most practically relevant learning algorithms -- including hybrid-quantum classical algorithms -- even the generative modelling problem associated with depth d=ω(log(n)) Clifford circuits is hard. This result places limitations on the applicability of near-term hybrid quantum-classical generative modelling algorithms.

1 aHinsche, Marcel1 aIoannou, Marios1 aNietner, Alexander1 aHaferkamp, Jonas1 aQuek, Yihui1 aHangleiter, Dominik1 aSeifert, Jean-Pierre1 aEisert, Jens1 aSweke, Ryan uhttps://arxiv.org/abs/2207.0314002430nas a2200205 4500008004100000245007100041210006900112260001500181520180900196100002002005700002002025700002302045700002102068700001602089700002402105700002502129700001702154700001602171856003702187 2021 eng d00aLearnability of the output distributions of local quantum circuits0 aLearnability of the output distributions of local quantum circui c10/11/20213 a

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. 

1 aHinsche, Marcel1 aIoannou, Marios1 aNietner, Alexander1 aHaferkamp, Jonas1 aQuek, Yihui1 aHangleiter, Dominik1 aSeifert, Jean-Pierre1 aEisert, Jens1 aSweke, Ryan uhttps://arxiv.org/abs/2110.0551702003nas a2200253 4500008004100000245008100041210006900122260001400191520125700205100002301462700001801485700002001503700002101523700002001544700002001564700001701584700002101601700001401622700001701636700002401653700002001677700001501697856003701712 2021 eng d00aQuantum Computational Supremacy via High-Dimensional Gaussian Boson Sampling0 aQuantum Computational Supremacy via HighDimensional Gaussian Bos c2/24/20213 a

Photonics is a promising platform for demonstrating quantum computational supremacy (QCS) by convincingly outperforming the most powerful classical supercomputers on a well-defined computational task. Despite this promise, existing photonics proposals and demonstrations face significant hurdles. Experimentally, current implementations of Gaussian boson sampling lack programmability or have prohibitive loss rates. Theoretically, there is a comparative lack of rigorous evidence for the classical hardness of GBS. In this work, we make significant progress in improving both the theoretical evidence and experimental prospects. On the theory side, we provide strong evidence for the hardness of Gaussian boson sampling, placing it on par with the strongest theoretical proposals for QCS. On the experimental side, we propose a new QCS architecture, high-dimensional Gaussian boson sampling, which is programmable and can be implemented with low loss rates using few optical components. We show that particular classical algorithms for simulating GBS are vastly outperformed by high-dimensional Gaussian boson sampling experiments at modest system sizes. This work thus opens the path to demonstrating QCS with programmable photonic processors.

1 aDeshpande, Abhinav1 aMehta, Arthur1 aVincent, Trevor1 aQuesada, Nicolas1 aHinsche, Marcel1 aIoannou, Marios1 aMadsen, Lars1 aLavoie, Jonathan1 aQi, Haoyu1 aEisert, Jens1 aHangleiter, Dominik1 aFefferman, Bill1 aDhand, Ish uhttps://arxiv.org/abs/2102.12474