@article {3490, title = {Efficiently verifiable quantum advantage on near-term analog quantum simulators}, year = {2024}, month = {3/13/2024}, abstract = {

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.

}, url = {https://arxiv.org/abs/2403.08195}, author = {Zhenning Liu and Dhruv Devulapalli and Dominik Hangleiter and Yi-Kai Liu and Alicia J. Koll{\'a}r and Alexey V. Gorshkov and Andrew M. Childs} } @article {3488, title = {The Second Moment of Hafnians in Gaussian Boson Sampling}, year = {2024}, month = {3/20/2024}, abstract = {

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.

}, url = {https://arxiv.org/abs/2403.13878}, author = {Adam Ehrenberg and Joseph T. Iosue and Abhinav Deshpande and Dominik Hangleiter and Alexey V. Gorshkov} } @article {3310, title = {Bell sampling from quantum circuits}, year = {2023}, month = {6/19/2023}, abstract = {

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.

}, url = {https://arxiv.org/abs/2306.00083}, author = {Dominik Hangleiter and Michael Gullans} } @article {3365, title = {Bell sampling from quantum circuits}, year = {2023}, month = {10/6/2023}, abstract = {

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.

}, url = {https://arxiv.org/abs/2306.00083}, author = {Dominik Hangleiter and Michael Gullans} } @article {3315, title = {Page curves and typical entanglement in linear optics}, journal = {Quantum}, volume = {7}, year = {2023}, month = {5/18/2023}, pages = {1017}, abstract = {

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{\'e}nyi-2 Page curve (the average R{\'e}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{\'e}nyi-2 entropy by studying its variance. Using the aforementioned results for the R{\'e}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.

}, doi = {10.22331/q-2023-05-23-1017}, url = {https://arxiv.org/abs/2209.06838}, author = {Joseph T. Iosue and Adam Ehrenberg and Dominik Hangleiter and Abhinav Deshpande and Alexey V. Gorshkov} } @article {3312, title = {A sharp phase transition in linear cross-entropy benchmarking}, year = {2023}, month = {5/8/2023}, abstract = {

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.

}, url = {https://arxiv.org/abs/2305.04954}, author = {Brayden Ware and Abhinav Deshpande and Dominik Hangleiter and Pradeep Niroula and Bill Fefferman and Alexey V. Gorshkov and Michael Gullans} } @article {3399, title = {Transition of Anticoncentration in Gaussian Boson Sampling}, year = {2023}, month = {12/13/2023}, abstract = {

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.

}, url = {https://arxiv.org/abs/2312.08433}, author = {Adam Ehrenberg and Joseph T. Iosue and Abhinav Deshpande and Dominik Hangleiter and Alexey V. Gorshkov} } @article {3363, title = {Verifiable measurement-based quantum random sampling with trapped ions}, year = {2023}, month = {7/26/2023}, abstract = {

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.

}, doi = {https://doi.org/10.48550/arXiv.2307.14424}, url = {https://arxiv.org/abs/2307.14424}, author = {Martin Ringbauer and Marcel Hinsche and Thomas Feldker and Paul K. Faehrmann and Juani Bermejo-Vega and Claire Edmunds and Lukas Postler and Roman Stricker and Christian D. Marciniak and Michael Meth and Ivan Pogorelov and Rainer Blatt and Philipp Schindler and Jens Eisert and Thomas Monz and Dominik Hangleiter} } @book {2982, title = {Analogue Quantum Simulation: A New Instrument for Scientific Understanding}, year = {2022}, pages = {83-102}, publisher = {Springer Nature}, organization = {Springer Nature}, abstract = {

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

}, doi = {https://doi.org/10.1007/978-3-030-87216-8_6}, author = {Dominik Hangleiter and Jacques Carolan and Karim P. Y. Th{\'e}bault} } @article {3067, title = {Boson Sampling for Generalized Bosons}, year = {2022}, month = {5/2/2022}, abstract = {

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.

}, url = {https://arxiv.org/abs/2204.08389}, author = {En-Jui Kuo and Yijia Xu and Dominik Hangleiter and Andrey Grankin and Mohammad Hafezi} } @article {3066, title = {Computational advantage of quantum random sampling}, year = {2022}, month = {6/8/2022}, abstract = {

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.

}, url = {https://arxiv.org/abs/2206.04079}, author = {Dominik Hangleiter and Jens Eisert} } @article {2983, title = {Quantum computational advantage via high-dimensional Gaussian boson sampling}, journal = {Science Advances}, volume = {8}, year = {2022}, month = {1/5/2022}, pages = {eabi7894}, abstract = {

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.

}, doi = {10.1126/sciadv.abi7894}, url = {https://www.science.org/doi/abs/10.1126/sciadv.abi7894}, author = {Abhinav Deshpande and Arthur Mehta and Trevor Vincent and Nicolas Quesada and Marcel Hinsche and Marios Ioannou and Lars Madsen and Jonathan Lavoie and Haoyu Qi and Jens Eisert and Dominik Hangleiter and Bill Fefferman and Ish Dhand} } @article {3065, title = {A single T-gate makes distribution learning hard}, year = {2022}, month = {7/7/2022}, abstract = {

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.

}, url = {https://arxiv.org/abs/2207.03140}, 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 {2924, title = {How to engineer a quantum wavefunction}, year = {2021}, month = {12/2/2021}, abstract = {

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.\ 

}, url = {https://arxiv.org/abs/2112.01105}, author = {Peter W. Evans and Dominik Hangleiter and Karim P. Y. Th{\'e}bault} } @article {2869, title = {Learnability of the output distributions of local quantum circuits}, year = {2021}, month = {10/11/2021}, abstract = {

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 {2827, title = {Precise Hamiltonian identification of a superconducting quantum processor}, year = {2021}, month = {8/18/2021}, abstract = {

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.

}, url = {https://arxiv.org/abs/2108.08319}, author = {Dominik Hangleiter and Ingo Roth and Jens Eisert and Pedram Roushan} } @article {2773, title = {Quantum Computational Supremacy via High-Dimensional Gaussian Boson Sampling}, year = {2021}, month = {2/24/2021}, abstract = {

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.

}, url = {https://arxiv.org/abs/2102.12474}, author = {Abhinav Deshpande and Arthur Mehta and Trevor Vincent and Nicolas Quesada and Marcel Hinsche and Marios Ioannou and Lars Madsen and Jonathan Lavoie and Haoyu Qi and Jens Eisert and Dominik Hangleiter and Bill Fefferman and Ish Dhand} }