01355nas a2200181 4500008004100000245008400041210006900125260001400194520077500208100001800983700002301001700002401024700001601048700002401064700002501088700002301113856003701136 2024 eng d00aEfficiently verifiable quantum advantage on near-term analog quantum simulators0 aEfficiently verifiable quantum advantage on nearterm analog quan c3/13/20243 a

Existing schemes for demonstrating quantum computational advantage are subject to various practical restrictions, including the hardness of verification and challenges in experimental implementation. Meanwhile, analog quantum simulators have been realized in many experiments to study novel physics. In this work, we propose a quantum advantage protocol based on single-step Feynman-Kitaev verification of an analog quantum simulation, in which the verifier need only run an O(λ2)-time classical computation, and the prover need only prepare O(1) samples of a history state and perform O(λ2) single-qubit measurements, for a security parameter λ. We also propose a near-term feasible strategy for honest provers and discuss potential experimental realizations.

1 aLiu, Zhenning1 aDevulapalli, Dhruv1 aHangleiter, Dominik1 aLiu, Yi-Kai1 aKollár, Alicia, J.1 aGorshkov, Alexey, V.1 aChilds, Andrew, M. uhttps://arxiv.org/abs/2403.0819501621nas a2200157 4500008004100000245006100041210005700102260001400159520113900173100002001312700002201332700002301354700002401377700002501401856003701426 2024 eng d00aThe Second Moment of Hafnians in Gaussian Boson Sampling0 aSecond Moment of Hafnians in Gaussian Boson Sampling c3/20/20243 a

Gaussian Boson Sampling is a popular method for experimental demonstrations of quantum advantage, but many subtleties remain in fully understanding its theoretical underpinnings. An important component in the theoretical arguments for approximate average-case hardness of sampling is anticoncentration, which is a second-moment property of the output probabilities. In Gaussian Boson Sampling these are given by hafnians of generalized circular orthogonal ensemble matrices. In a companion work [arXiv:2312.08433], we develop a graph-theoretic method to study these moments and use it to identify a transition in anticoncentration. In this work, we find a recursive expression for the second moment using these graph-theoretic techniques. While we have not been able to solve this recursion by hand, we are able to solve it numerically exactly, which we do up to Fock sector 2n=80. We further derive new analytical results about the second moment. These results allow us to pinpoint the transition in anticoncentration and furthermore yield the expected linear cross-entropy benchmarking score for an ideal (error-free) device.

1 aEhrenberg, Adam1 aIosue, Joseph, T.1 aDeshpande, Abhinav1 aHangleiter, Dominik1 aGorshkov, Alexey, V. uhttps://arxiv.org/abs/2403.1387801453nas a2200121 4500008004100000245004000041210004000081260001400121520111400135100002401249700002101273856003701294 2023 eng d00aBell sampling from quantum circuits0 aBell sampling from quantum circuits c10/6/20233 a

A central challenge in the verification of quantum computers is benchmarking their performance as a whole and demonstrating their computational capabilities. In this work, we find a universal model of quantum computation, Bell sampling, that can be used for both of those tasks and thus provides an ideal stepping stone towards fault-tolerance. In Bell sampling, we measure two copies of a state prepared by a quantum circuit in the transversal Bell basis. We show that the Bell samples are classically intractable to produce and at the same time constitute what we call a circuit shadow: from the Bell samples we can efficiently extract information about the quantum circuit preparing the state, as well as diagnose circuit errors. In addition to known properties that can be efficiently extracted from Bell samples, we give two new and efficient protocols, a test for the depth of the circuit and an algorithm to estimate a lower bound to the number of T gates in the circuit. With some additional measurements, our algorithm learns a full description of states prepared by circuits with low T-count.

1 aHangleiter, Dominik1 aGullans, Michael uhttps://arxiv.org/abs/2306.0008301443nas a2200121 4500008004100000245004000041210004000081260001400121520110400135100002401239700002101263856003701284 2023 eng d00aBell sampling from quantum circuits0 aBell sampling from quantum circuits c6/19/20233 a

A central challenge in the verification of quantum computers is benchmarking their performance as a whole and demonstrating their computational capabilities. In this work, we find a model of quantum computation, Bell sampling, that can be used for both of those tasks and thus provides an ideal stepping stone towards fault-tolerance. In Bell sampling, we measure two copies of a state prepared by a quantum circuit in the transversal Bell basis. We show that the Bell samples are classically intractable to produce and at the same time constitute what we call a circuit shadow: from the Bell samples we can efficiently extract information about the quantum circuit preparing the state, as well as diagnose circuit errors. In addition to known properties that can be efficiently extracted from Bell samples, we give two new and efficient protocols, a test for the depth of the circuit and an algorithm to estimate a lower bound to the number of T gates in the circuit. With some additional measurements, our algorithm learns a full description of states prepared by circuits with low T-count.

1 aHangleiter, Dominik1 aGullans, Michael uhttps://arxiv.org/abs/2306.0008301026nas a2200349 4500008004100000022001400041245006600055210006600121260001400187100002100201700002200222700002400244700001900268700001800287700001800305700001800323700001800341700002300359700002400382700002800406700002000434700001500454700001300469700002800482700002300510700002200533700002100555700002000576700002000596700002300616856003700639 2023 eng d a1476-468700aLogical quantum processor based on reconfigurable atom arrays0 aLogical quantum processor based on reconfigurable atom arrays c12/7/20231 aBluvstein, Dolev1 aEvered, Simon, J.1 aGeim, Alexandra, A.1 aLi, Sophie, H.1 aZhou, Hengyun1 aManovitz, Tom1 aEbadi, Sepehr1 aCain, Madelyn1 aKalinowski, Marcin1 aHangleiter, Dominik1 aAtaides, Pablo, Bonilla1 aMaskara, Nishad1 aCong, Iris1 aGao, Xun1 aRodriguez, Pedro, Sales1 aKarolyshyn, Thomas1 aSemeghini, Giulia1 aGullans, Michael1 aGreiner, Markus1 aVuletic, Vladan1 aLukin, Mikhail, D. uhttps://arxiv.org/abs/2312.0398202008nas a2200181 4500008004100000245005800041210005800099260001400157300000900171490000600180520148900186100002201675700002001697700002401717700002301741700002501764856003701789 2023 eng d00aPage curves and typical entanglement in linear optics0 aPage curves and typical entanglement in linear optics c5/18/2023 a10170 v73 a

Bosonic Gaussian states are a special class of quantum states in an infinite dimensional Hilbert space that are relevant to universal continuous-variable quantum computation as well as to near-term quantum sampling tasks such as Gaussian Boson Sampling. In this work, we study entanglement within a set of squeezed modes that have been evolved by a random linear optical unitary. We first derive formulas that are asymptotically exact in the number of modes for the Rényi-2 Page curve (the average Rényi-2 entropy of a subsystem of a pure bosonic Gaussian state) and the corresponding Page correction (the average information of the subsystem) in certain squeezing regimes. We then prove various results on the typicality of entanglement as measured by the Rényi-2 entropy by studying its variance. Using the aforementioned results for the Rényi-2 entropy, we upper and lower bound the von Neumann entropy Page curve and prove certain regimes of entanglement typicality as measured by the von Neumann entropy. Our main proofs make use of a symmetry property obeyed by the average and the variance of the entropy that dramatically simplifies the averaging over unitaries. In this light, we propose future research directions where this symmetry might also be exploited. We conclude by discussing potential applications of our results and their generalizations to Gaussian Boson Sampling and to illuminating the relationship between entanglement and computational complexity.

1 aIosue, Joseph, T.1 aEhrenberg, Adam1 aHangleiter, Dominik1 aDeshpande, Abhinav1 aGorshkov, Alexey, V. uhttps://arxiv.org/abs/2209.0683802031nas a2200121 4500008004100000245006200041210006200103260001500165520165100180100001701831700002401848856003701872 2023 eng d00aSecret extraction attacks against obfuscated IQP circuits0 aSecret extraction attacks against obfuscated IQP circuits c12/15/20233 a

Quantum computing devices can now perform sampling tasks which, according to complexity-theoretic and numerical evidence, are beyond the reach of classical computers. This raises the question of how one can efficiently verify that a quantum computer operating in this regime works as intended. In 2008, Shepherd and Bremner proposed a protocol in which a verifier constructs a unitary from the comparatively easy-to-implement family of so-called IQP circuits, and challenges a prover to execute it on a quantum computer. The challenge problem is designed to contain an obfuscated secret, which can be turned into a statistical test that accepts samples from a correct quantum implementation. It was conjectured that extracting the secret from the challenge problem is NP-hard, so that the ability to pass the test constitutes strong evidence that the prover possesses a quantum device and that it works as claimed. Unfortunately, about a decade later, Kahanamoku-Meyer found an efficient classical secret extraction attack. Bremner, Cheng, and Ji very recently followed up by constructing a wide-ranging generalization of the original protocol. Their IQP Stabilizer Scheme has been explicitly designed to circumvent the known weakness. They also suggested that the original construction can be made secure by adjusting the problem parameters. In this work, we develop a number of secret extraction attacks which are effective against both new approaches in a wide range of problem parameters. The important problem of finding an efficient and reliable verification protocol for sampling-based proofs of quantum supremacy thus remains open.

1 aGross, David1 aHangleiter, Dominik uhttps://arxiv.org/abs/2312.1015601741nas a2200181 4500008004100000245006600041210006300107260001300170520118700183100001801370700002301388700002401411700002101435700002001456700002501476700002101501856003701522 2023 eng d00aA sharp phase transition in linear cross-entropy benchmarking0 asharp phase transition in linear crossentropy benchmarking c5/8/20233 a

Demonstrations of quantum computational advantage and benchmarks of quantum processors via quantum random circuit sampling are based on evaluating the linear cross-entropy benchmark (XEB). A key question in the theory of XEB is whether it approximates the fidelity of the quantum state preparation. Previous works have shown that the XEB generically approximates the fidelity in a regime where the noise rate per qudit ε satisfies εN≪1 for a system of N qudits and that this approximation breaks down at large noise rates. Here, we show that the breakdown of XEB as a fidelity proxy occurs as a sharp phase transition at a critical value of εN that depends on the circuit architecture and properties of the two-qubit gates, including in particular their entangling power. We study the phase transition using a mapping of average two-copy quantities to statistical mechanics models in random quantum circuit architectures with full or one-dimensional connectivity. We explain the phase transition behavior in terms of spectral properties of the transfer matrix of the statistical mechanics model and identify two-qubit gate sets that exhibit the largest noise robustness.

1 aWare, Brayden1 aDeshpande, Abhinav1 aHangleiter, Dominik1 aNiroula, Pradeep1 aFefferman, Bill1 aGorshkov, Alexey, V.1 aGullans, Michael uhttps://arxiv.org/abs/2305.0495401909nas a2200157 4500008004100000245006300041210006300104260001500167520141800182100002001600700002201620700002301642700002401665700002501689856003701714 2023 eng d00aTransition of Anticoncentration in Gaussian Boson Sampling0 aTransition of Anticoncentration in Gaussian Boson Sampling c12/13/20233 a

Gaussian Boson Sampling is a promising method for experimental demonstrations of quantum advantage because it is easier to implement than other comparable schemes. While most of the properties of Gaussian Boson Sampling are understood to the same degree as for these other schemes, we understand relatively little about the statistical properties of its output distribution. The most relevant statistical property, from the perspective of demonstrating quantum advantage, is the anticoncentration of the output distribution as measured by its second moment. The degree of anticoncentration features in arguments for the complexity-theoretic hardness of Gaussian Boson Sampling, and it is also important to know when using cross-entropy benchmarking to verify experimental performance. In this work, we develop a graph-theoretic framework for analyzing the moments of the Gaussian Boson Sampling distribution. Using this framework, we show that Gaussian Boson Sampling undergoes a transition in anticoncentration as a function of the number of modes that are initially squeezed compared to the number of photons measured at the end of the circuit. When the number of initially squeezed modes scales sufficiently slowly with the number of photons, there is a lack of anticoncentration. However, if the number of initially squeezed modes scales quickly enough, the output probabilities anticoncentrate weakly.

1 aEhrenberg, Adam1 aIosue, Joseph, T.1 aDeshpande, Abhinav1 aHangleiter, Dominik1 aGorshkov, Alexey, V. uhttps://arxiv.org/abs/2312.0843302171nas a2200289 4500008004100000245007500041210006900116260001400185520131000199100002201509700002001531700002001551700002401571700002401595700002001619700001901639700002001658700002901678700001801707700002001725700001801745700002301763700001701786700001701803700002401820856003701844 2023 eng d00aVerifiable measurement-based quantum random sampling with trapped ions0 aVerifiable measurementbased quantum random sampling with trapped c7/26/20233 a

Quantum computers are now on the brink of outperforming their classical counterparts. One way to demonstrate the advantage of quantum computation is through quantum random sampling performed on quantum computing devices. However, existing tools for verifying that a quantum device indeed performed the classically intractable sampling task are either impractical or not scalable to the quantum advantage regime. The verification problem thus remains an outstanding challenge. Here, we experimentally demonstrate efficiently verifiable quantum random sampling in the measurement-based model of quantum computation on a trapped-ion quantum processor. We create random cluster states, which are at the heart of measurement-based computing, up to a size of 4 x 4 qubits. Moreover, by exploiting the structure of these states, we are able to recycle qubits during the computation to sample from entangled cluster states that are larger than the qubit register. We then efficiently estimate the fidelity to verify the prepared states--in single instances and on average--and compare our results to cross-entropy benchmarking. Finally, we study the effect of experimental noise on the certificates. Our results and techniques provide a feasible path toward a verified demonstration of a quantum advantage.

1 aRingbauer, Martin1 aHinsche, Marcel1 aFeldker, Thomas1 aFaehrmann, Paul, K.1 aBermejo-Vega, Juani1 aEdmunds, Claire1 aPostler, Lukas1 aStricker, Roman1 aMarciniak, Christian, D.1 aMeth, Michael1 aPogorelov, Ivan1 aBlatt, Rainer1 aSchindler, Philipp1 aEisert, Jens1 aMonz, Thomas1 aHangleiter, Dominik uhttps://arxiv.org/abs/2307.1442400829nam a2200145 4500008004100000245007900041210006900120260002000189300001100209520027900220100002400499700002100523700002800544856011100572 2022 eng d00aAnalogue Quantum Simulation: A New Instrument for Scientific Understanding0 aAnalogue Quantum Simulation A New Instrument for Scientific Unde bSpringer Nature a83-1023 a

Analyzes analogue quantum simulation philosophically. Provides a framework to support the goals of scientists. Useful to both working scientists and philosophers of science.

1 aHangleiter, Dominik1 aCarolan, Jacques1 aThébault, Karim, P. Y. uhttps://www.quics.umd.edu/publications/analogue-quantum-simulation-new-instrument-scientific-understanding01081nas a2200157 4500008004100000245004200041210004200083260001300125520065300138100001600791700001400807700002400821700002000845700002100865856003700886 2022 eng d00aBoson Sampling for Generalized Bosons0 aBoson Sampling for Generalized Bosons c5/2/20223 a

We introduce the notion of "generalized bosons" whose exchange statistics resemble those of bosons, but the local bosonic commutator [ai,a†i]=1 is replaced by an arbitrary single-mode operator that is diagonal in the generalized Fock basis. Examples of generalized bosons include boson pairs and spins. We consider the analogue of the boson sampling task for these particles and observe that its output probabilities are still given by permanents, so that the results regarding hardness of sampling directly carry over. Finally, we propose implementations of generalized boson sampling in circuit-QED and ion-trap platforms.

1 aKuo, En-Jui1 aXu, Yijia1 aHangleiter, Dominik1 aGrankin, Andrey1 aHafezi, Mohammad uhttps://arxiv.org/abs/2204.0838901130nas a2200121 4500008004100000245005500041210005500096260001300151520076600164100002400930700001700954856003700971 2022 eng d00aComputational advantage of quantum random sampling0 aComputational advantage of quantum random sampling c6/8/20223 a

Quantum random sampling is the leading proposal for demonstrating a computational advantage of quantum computers over classical computers. Recently, first large-scale implementations of quantum random sampling have arguably surpassed the boundary of what can be simulated on existing classical hardware. In this article, we comprehensively review the theoretical underpinning of quantum random sampling in terms of computational complexity and verifiability, as well as the practical aspects of its experimental implementation using superconducting and photonic devices and its classical simulation. We discuss in detail open questions in the field and provide perspectives for the road ahead, including potential applications of quantum random sampling.

1 aHangleiter, Dominik1 aEisert, Jens uhttps://arxiv.org/abs/2206.0407902013nas 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.abi789401923nas a2200241 4500008004100000245007300041210006900114260001400183520110600197653004301303653002701346653002901373653003901402653003101441653005201472100002001524700002801544700001501572700002401587700001601611700001701627856003701644 2022 eng d00aScalably learning quantum many-body Hamiltonians from dynamical data0 aScalably learning quantum manybody Hamiltonians from dynamical d c9/28/20223 a

The physics of a closed quantum mechanical system is governed by its Hamiltonian. However, in most practical situations, this Hamiltonian is not precisely known, and ultimately all there is are data obtained from measurements on the system. In this work, we introduce a highly scalable, data-driven approach to learning families of interacting many-body Hamiltonians from dynamical data, by bringing together techniques from gradient-based optimization from machine learning with efficient quantum state representations in terms of tensor networks. Our approach is highly practical, experimentally friendly, and intrinsically scalable to allow for system sizes of above 100 spins. In particular, we demonstrate on synthetic data that the algorithm works even if one is restricted to one simple initial state, a small number of single-qubit observables, and time evolution up to relatively short times. For the concrete example of the one-dimensional Heisenberg model our algorithm exhibits an error constant in the system size and scaling as the inverse square root of the size of the data set.

10aFOS: Computer and information sciences10aFOS: Physical sciences10aMachine Learning (cs.LG)10aQuantum Gases (cond-mat.quant-gas)10aQuantum Physics (quant-ph)10aStrongly Correlated Electrons (cond-mat.str-el)1 aWilde, Frederik1 aKshetrimayum, Augustine1 aRoth, Ingo1 aHangleiter, Dominik1 aSweke, Ryan1 aEisert, Jens uhttps://arxiv.org/abs/2209.1432801867nas a2200205 4500008004100000245006500041210006500106260001500171520119000186653003701376653004301413653002701456653003101483100001801514700002301532700002401555700002501579700002001604856003701624 2022 eng d00aSharp complexity phase transitions generated by entanglement0 aSharp complexity phase transitions generated by entanglement c12/20/20223 a

Entanglement is one of the physical properties of quantum systems responsible for the computational hardness of simulating quantum systems. But while the runtime of specific algorithms, notably tensor network algorithms, explicitly depends on the amount of entanglement in the system, it is unknown whether this connection runs deeper and entanglement can also cause inherent, algorithm-independent complexity. In this work, we quantitatively connect the entanglement present in certain quantum systems to the computational complexity of simulating those systems. Moreover, we completely characterize the entanglement and complexity as a function of a system parameter. Specifically, we consider the task of simulating single-qubit measurements of k--regular graph states on n qubits. We show that, as the regularity parameter is increased from 1 to n−1, there is a sharp transition from an easy regime with low entanglement to a hard regime with high entanglement at k=3, and a transition back to easy and low entanglement at k=n−3. As a key technical result, we prove a duality for the simulation complexity of regular graph states between low and high regularity.

10aComputational Complexity (cs.CC)10aFOS: Computer and information sciences10aFOS: Physical sciences10aQuantum Physics (quant-ph)1 aGhosh, Soumik1 aDeshpande, Abhinav1 aHangleiter, Dominik1 aGorshkov, Alexey, V.1 aFefferman, Bill uhttps://arxiv.org/abs/2212.1058202255nas 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.0314001060nas a2200133 4500008004100000245004300041210004300084260001400127520067500141100002100816700002400837700002800861856003700889 2021 eng d00aHow to engineer a quantum wavefunction0 aHow to engineer a quantum wavefunction c12/2/20213 a

In a conventional experiment, inductive inferences between source and target systems are typically justified with reference to a uniformity principle between systems of the same material type. In an analogue quantum simulation, by contrast, scientists aim to learn about target quantum systems of one material type via an experiment on a source quantum system of a different material type. In this paper, we argue that such an inference can be justified by reference to the two quantum systems being of the same empirical type. We illustrate this novel experimental practice of wavefunction engineering with reference to the example of Bose-Hubbard systems. 

1 aEvans, Peter, W.1 aHangleiter, Dominik1 aThébault, Karim, P. Y. uhttps://arxiv.org/abs/2112.0110502430nas 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.0551701886nas a2200145 4500008004100000245007800041210006900119260001400188520142500202100002401627700001501651700001701666700002001683856003701703 2021 eng d00aPrecise Hamiltonian identification of a superconducting quantum processor0 aPrecise Hamiltonian identification of a superconducting quantum  c8/18/20213 a

The required precision to perform quantum simulations beyond the capabilities of classical computers imposes major experimental and theoretical challenges. Here, we develop a characterization technique to benchmark the implementation precision of a specific quantum simulation task. We infer all parameters of the bosonic Hamiltonian that governs the dynamics of excitations in a two-dimensional grid of nearest-neighbour coupled superconducting qubits. We devise a robust algorithm for identification of Hamiltonian parameters from measured times series of the expectation values of single-mode canonical coordinates. Using super-resolution and denoising methods, we first extract eigenfrequencies of the governing Hamiltonian from the complex time domain measurement; next, we recover the eigenvectors of the Hamiltonian via constrained manifold optimization over the orthogonal group. For five and six coupled qubits, we identify Hamiltonian parameters with sub-MHz precision and construct a spatial implementation error map for a grid of 27 qubits. Our approach enables us to distinguish and quantify the effects of state preparation and measurement errors and show that they are the dominant sources of errors in the implementation. Our results quantify the implementation accuracy of analog dynamics and introduce a diagnostic toolkit for understanding, calibrating, and improving analog quantum processors.

1 aHangleiter, Dominik1 aRoth, Ingo1 aEisert, Jens1 aRoushan, Pedram uhttps://arxiv.org/abs/2108.0831902003nas 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