TY - JOUR T1 - Effect of non-unital noise on random circuit sampling Y1 - 2023 A1 - Bill Fefferman A1 - Soumik Ghosh A1 - Michael Gullans A1 - Kohdai Kuroiwa A1 - Kunal Sharma AB -
In this work, drawing inspiration from the type of noise present in real hardware, we study the output distribution of random quantum circuits under practical non-unital noise sources with constant noise rates. We show that even in the presence of unital sources like the depolarizing channel, the distribution, under the combined noise channel, never resembles a maximally entropic distribution at any depth. To show this, we prove that the output distribution of such circuits never anticoncentrates — meaning it is never too "flat" — regardless of the depth of the circuit. This is in stark contrast to the behavior of noiseless random quantum circuits or those with only unital noise, both of which anticoncentrate at sufficiently large depths. As consequences, our results have interesting algorithmic implications on both the hardness and easiness of noisy random circuit sampling, since anticoncentration is a critical property exploited by both state-of-the-art classical hardness and easiness results.
UR - https://arxiv.org/abs/2306.16659 ER - TY - JOUR T1 - A sharp phase transition in linear cross-entropy benchmarking Y1 - 2023 A1 - Brayden Ware A1 - Abhinav Deshpande A1 - Dominik Hangleiter A1 - Pradeep Niroula A1 - Bill Fefferman A1 - Alexey V. Gorshkov A1 - Michael J. Gullans AB -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.
UR - https://arxiv.org/abs/2305.04954 ER - TY - JOUR T1 - Importance of the Spectral gap in Estimating Ground-State Energies JF - PRX Quantum Y1 - 2022 A1 - Abhinav Deshpande A1 - Alexey V. Gorshkov A1 - Bill Fefferman AB -The field of quantum Hamiltonian complexity lies at the intersection of quantum many-body physics and computational complexity theory, with deep implications to both fields. The main object of study is the LocalHamiltonian problem, which is concerned with estimating the ground-state energy of a local Hamiltonian and is complete for the class QMA, a quantum generalization of the class NP. A major challenge in the field is to understand the complexity of the LocalHamiltonian problem in more physically natural parameter regimes. One crucial parameter in understanding the ground space of any Hamiltonian in many-body physics is the spectral gap, which is the difference between the smallest two eigenvalues. Despite its importance in quantum many-body physics, the role played by the spectral gap in the complexity of the LocalHamiltonian is less well-understood. In this work, we make progress on this question by considering the precise regime, in which one estimates the ground-state energy to within inverse exponential precision. Computing ground-state energies precisely is a task that is important for quantum chemistry and quantum many-body physics.
In the setting of inverse-exponential precision, there is a surprising result that the complexity of LocalHamiltonian is magnified from QMA to PSPACE, the class of problems solvable in polynomial space. We clarify the reason behind this boost in complexity. Specifically, we show that the full complexity of the high precision case only comes about when the spectral gap is exponentially small. As a consequence of the proof techniques developed to show our results, we uncover important implications for the representability and circuit complexity of ground states of local Hamiltonians, the theory of uniqueness of quantum witnesses, and techniques for the amplification of quantum witnesses in the presence of postselection.
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.
VL - 8 U4 - eabi7894 UR - https://www.science.org/doi/abs/10.1126/sciadv.abi7894 U5 - 10.1126/sciadv.abi7894 ER - TY - JOUR T1 - Quantum Computational Supremacy via High-Dimensional Gaussian Boson Sampling Y1 - 2021 A1 - Abhinav Deshpande A1 - Arthur Mehta A1 - Trevor Vincent A1 - Nicolas Quesada A1 - Marcel Hinsche A1 - Marios Ioannou A1 - Lars Madsen A1 - Jonathan Lavoie A1 - Haoyu Qi A1 - Jens Eisert A1 - Dominik Hangleiter A1 - Bill Fefferman A1 - Ish Dhand AB -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.
UR - https://arxiv.org/abs/2102.12474 ER - TY - JOUR T1 - Tight bounds on the convergence of noisy random circuits to uniform Y1 - 2021 A1 - Abhinav Deshpande A1 - Bill Fefferman A1 - Alexey V. Gorshkov A1 - Michael Gullans A1 - Pradeep Niroula A1 - Oles Shtanko AB -We study the properties of output distributions of noisy, random circuits. We obtain upper and lower bounds on the expected distance of the output distribution from the uniform distribution. These bounds are tight with respect to the dependence on circuit depth. Our proof techniques also allow us to make statements about the presence or absence of anticoncentration for both noisy and noiseless circuits. We uncover a number of interesting consequences for hardness proofs of sampling schemes that aim to show a quantum computational advantage over classical computation. Specifically, we discuss recent barrier results for depth-agnostic and/or noise-agnostic proof techniques. We show that in certain depth regimes, noise-agnostic proof techniques might still work in order to prove an often-conjectured claim in the literature on quantum computational advantage, contrary to what was thought prior to this work.
UR - https://arxiv.org/abs/2112.00716 ER - TY - JOUR T1 - Complexity phase diagram for interacting and long-range bosonic Hamiltonians Y1 - 2019 A1 - Nishad Maskara A1 - Abhinav Deshpande A1 - Minh C. Tran A1 - Adam Ehrenberg A1 - Bill Fefferman A1 - Alexey V. Gorshkov AB -Recent years have witnessed a growing interest in topics at the intersection of many-body physics and complexity theory. Many-body physics aims to understand and classify emergent behavior of systems with a large number of particles, while complexity theory aims to classify computational problems based on how the time required to solve the problem scales as the problem size becomes large. In this work, we use insights from complexity theory to classify phases in interacting many-body systems. Specifically, we demonstrate a "complexity phase diagram" for the Bose-Hubbard model with long-range hopping. This shows how the complexity of simulating time evolution varies according to various parameters appearing in the problem, such as the evolution time, the particle density, and the degree of locality. We find that classification of complexity phases is closely related to upper bounds on the spread of quantum correlations, and protocols to transfer quantum information in a controlled manner. Our work motivates future studies of complexity in many-body systems and its interplay with the associated physical phenomena.
UR - https://arxiv.org/abs/1906.04178 ER - TY - JOUR T1 - Quantum Computer Systems for Scientific Discovery Y1 - 2019 A1 - Yuri Alexeev A1 - Dave Bacon A1 - Kenneth R. Brown A1 - Robert Calderbank A1 - Lincoln D. Carr A1 - Frederic T. Chong A1 - Brian DeMarco A1 - Dirk Englund A1 - Edward Farhi A1 - Bill Fefferman A1 - Alexey V. Gorshkov A1 - Andrew Houck A1 - Jungsang Kim A1 - Shelby Kimmel A1 - Michael Lange A1 - Seth Lloyd A1 - Mikhail D. Lukin A1 - Dmitri Maslov A1 - Peter Maunz A1 - Christopher Monroe A1 - John Preskill A1 - Martin Roetteler A1 - Martin Savage A1 - Jeff Thompson A1 - Umesh Vazirani AB -The great promise of quantum computers comes with the dual challenges of building them and finding their useful applications. We argue that these two challenges should be considered together, by co-designing full stack quantum computer systems along with their applications in order to hasten their development and potential for scientific discovery. In this context, we identify scientific and community needs, opportunities, and significant challenges for the development of quantum computers for science over the next 2-10 years. This document is written by a community of university, national laboratory, and industrial researchers in the field of Quantum Information Science and Technology, and is based on a summary from a U.S. National Science Foundation workshop on Quantum Computing held on October 21-22, 2019 in Alexandria, VA.
UR - https://arxiv.org/abs/1912.07577 ER - TY - JOUR T1 - Dynamical phase transitions in sampling complexity JF - Phys. Rev. Lett. Y1 - 2018 A1 - Abhinav Deshpande A1 - Bill Fefferman A1 - Minh C. Tran A1 - Michael Foss-Feig A1 - Alexey V. Gorshkov AB -We make the case for studying the complexity of approximately simulating (sampling) quantum systems for reasons beyond that of quantum computational supremacy, such as diagnosing phase transitions. We consider the sampling complexity as a function of time
A critical milestone on the path to useful quantum computers is quantum supremacy - a demonstration of a quantum computation that is prohibitively hard for classical computers. A leading near-term candidate, put forth by the Google/UCSB team, is sampling from the probability distributions of randomly chosen quantum circuits, which we call Random Circuit Sampling (RCS). In this paper we study both the hardness and verification of RCS. While RCS was defined with experimental realization in mind, we show complexity theoretic evidence of hardness that is on par with the strongest theoretical proposals for supremacy. Specifically, we show that RCS satisfies an average-case hardness condition - computing output probabilities of typical quantum circuits is as hard as computing them in the worst-case, and therefore #P-hard. Our reduction exploits the polynomial structure in the output amplitudes of random quantum circuits, enabled by the Feynman path integral. In addition, it follows from known results that RCS satisfies an anti-concentration property, making it the first supremacy proposal with both average-case hardness and anti-concentration.
UR - https://arxiv.org/abs/1803.04402 ER - TY - JOUR T1 - Complexity of sampling as an order parameter Y1 - 2017 A1 - Abhinav Deshpande A1 - Bill Fefferman A1 - Michael Foss-Feig A1 - Alexey V. Gorshkov AB -We consider the classical complexity of approximately simulating time evolution under spatially local quadratic bosonic Hamiltonians for time
We study the complexity of classically sampling from the output distribution of an Ising spin model, which can be implemented naturally in a variety of atomic, molecular, and optical systems. In particular, we construct a specific example of an Ising Hamiltonian that, after time evolution starting from a trivial initial state, produces a particular output configuration with probability very nearly proportional to the square of the permanent of a matrix with arbitrary integer entries. In a similar spirit to boson sampling, the ability to sample classically from the probability distribution induced by time evolution under this Hamiltonian would imply unlikely complexity theoretic consequences, suggesting that the dynamics of such a spin model cannot be efficiently simulated with a classical computer. Physical Ising spin systems capable of achieving problem-size instances (i.e., qubit numbers) large enough so that classical sampling of the output distribution is classically difficult in practice may be achievable in the near future. Unlike boson sampling, our current results only imply hardness of exact classical sampling, leaving open the important question of whether a much stronger approximate-sampling hardness result holds in this context. The latter is most likely necessary to enable a convincing experimental demonstration of quantum supremacy. As referenced in a recent paper [A. Bouland, L. Mancinska, and X. Zhang, in Proceedings of the 31st Conference on Computational Complexity (CCC 2016), Leibniz International Proceedings in Informatics (Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, 2016)], our result completes the sampling hardness classification of two-qubit commuting Hamiltonians.
VL - 96 U4 - 032324 UR - https://arxiv.org/abs/1701.03167 CP - 3 U5 - 10.1103/PhysRevA.96.032324 ER - TY - JOUR T1 - A Complete Characterization of Unitary Quantum Space Y1 - 2016 A1 - Bill Fefferman A1 - Cedric Yen-Yu Lin AB - We give two complete characterizations of unitary quantum space-bounded classes. The first is based on the Matrix Inversion problem for well-conditioned matrices. We show that given the size-n efficient encoding of a 2O(k(n))×2O(k(n)) well-conditioned matrix H, approximating a particular entry of H−1 is complete for the class of problems solvable by a quantum algorithm that uses O(k(n)) space and performs all quantum measurements at the end of the computation. In particular, the problem of computing entries of H−1 for an explicit well-conditioned n×n matrix H is complete for unitary quantum logspace. We then show that the problem of approximating to high precision the least eigenvalue of a positive semidefinite matrix H, encoded as a circuit, gives a second characterization of unitary quantum space complexity. In the process we also establish an equivalence between unitary quantum space-bounded classes and certain QMA proof systems. As consequences, we establish that QMA with exponentially small completeness-soundness gap is equal to PSPACE, that determining whether a local Hamiltonian is frustration-free is PSPACE-complete, and give a provable setting in which the ability to prepare PEPS states gives less computational power than the ability to prepare the ground state of a generic local Hamiltonian. UR - http://arxiv.org/abs/1604.01384 ER - TY - CONF T1 - Computational Security of Quantum Encryption T2 - Computational Security of Quantum Encryption. In: Nascimento A., Barreto P. (eds) Information Theoretic Security. Y1 - 2016 A1 - Gorjan Alagic A1 - Anne Broadbent A1 - Bill Fefferman A1 - Tommaso Gagliardoni A1 - Christian Schaffner A1 - Michael St. Jules AB -Quantum-mechanical devices have the potential to transform cryptography. Most research in this area has focused either on the information-theoretic advantages of quantum protocols or on the security of classical cryptographic schemes against quantum attacks. In this work, we initiate the study of another relevant topic: the encryption of quantum data in the computational setting. In this direction, we establish quantum versions of several fundamental classical results. First, we develop natural definitions for private-key and public-key encryption schemes for quantum data. We then define notions of semantic security and indistinguishability, and, in analogy with the classical work of Goldwasser and Micali, show that these notions are equivalent. Finally, we construct secure quantum encryption schemes from basic primitives. In particular, we show that quantum-secure one-way functions imply IND-CCA1-secure symmetric-key quantum encryption, and that quantum-secure trapdoor one-way permutations imply semantically-secure public-key quantum encryption.
JA - Computational Security of Quantum Encryption. In: Nascimento A., Barreto P. (eds) Information Theoretic Security. UR - https://link.springer.com/chapter/10.1007%2F978-3-319-49175-2_3 ER - TY - JOUR T1 - Quantum Merlin Arthur with Exponentially Small Gap Y1 - 2016 A1 - Bill Fefferman A1 - Cedric Yen-Yu Lin AB - We study the complexity of QMA proof systems with inverse exponentially small promise gap. We show that this class can be exactly characterized by PSPACE, the class of problems solvable with a polynomial amount of memory. As applications we show that a "precise" version of the Local Hamiltonian problem is PSPACE-complete, and give a provable setting in which the ability to prepare PEPS states is not as powerful as the ability to prepare the ground state of general Local Hamiltonians. UR - http://arxiv.org/abs/1601.01975 ER - TY - JOUR T1 - On Quantum Obfuscation Y1 - 2016 A1 - Gorjan Alagic A1 - Bill Fefferman AB - Encryption of data is fundamental to secure communication in the modern world. Beyond encryption of data lies obfuscation, i.e., encryption of functionality. It is well-known that the most powerful means of obfuscating classical programs, so-called ``black-box obfuscation',' is provably impossible [Barak et al '12]. However, several recent results have yielded candidate schemes that satisfy a definition weaker than black-box, and yet still have numerous applications. In this work, we initialize the rigorous study of obfuscating programs via quantum-mechanical means. We define notions of quantum obfuscation which encompass several natural variants. The input to the obfuscator can describe classical or quantum functionality, and the output can be a circuit description or a quantum state. The obfuscator can also satisfy one of a number of obfuscation conditions: black-box, information-theoretic black-box, indistinguishability, and best possible; the last two conditions come in three variants: perfect, statistical, and computational. We discuss many applications, including CPA-secure quantum encryption, quantum fully-homomorphic encryption, and public-key quantum money. We then prove several impossibility results, extending a number of foundational papers on classical obfuscation to the quantum setting. We prove that quantum black-box obfuscation is impossible in a setting where adversaries can possess more than one output of the obfuscator. In particular, generic transformation of quantum circuits into black-box-obfuscated quantum circuits is impossible. We also show that statistical indistinguishability obfuscation is impossible, up to an unlikely complexity-theoretic collapse. Our proofs involve a new tool: chosen-ciphertext-secure encryption of quantum data, which was recently shown to be possible assuming quantum-secure one-way functions exist [Alagic et al '16]. UR - http://arxiv.org/abs/1602.01771 ER - TY - JOUR T1 - Space-Efficient Error Reduction for Unitary Quantum Computations JF - 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) Y1 - 2016 A1 - Bill Fefferman A1 - Hirotada Kobayashi A1 - Cedric Yen-Yu Lin A1 - Tomoyuki Morimae A1 - Harumichi Nishimura AB -This paper develops general space-efficient methods for error reduction for unitary quantum computation. Consider a polynomial-time quantum computation with completeness