01506nas a2200157 4500008004100000245005800041210005700099260001400156520104400170100002001214700001801234700002101252700002001273700001801293856003701311 2023 eng d00aEffect of non-unital noise on random circuit sampling0 aEffect of nonunital noise on random circuit sampling c6/28/20233 a
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.
1 aFefferman, Bill1 aGhosh, Soumik1 aGullans, Michael1 aKuroiwa, Kohdai1 aSharma, Kunal uhttps://arxiv.org/abs/2306.1665901745nas a2200181 4500008004100000245006600041210006300107260001300170520118700183100001801370700002301388700002401411700002101435700002001456700002501476700002501501856003701526 2023 eng d00aA sharp phase transition in linear cross-entropy benchmarking0 asharp phase transition in linear crossentropy benchmarking c5/8/20233 aDemonstrations 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, J. uhttps://arxiv.org/abs/2305.0495402357nas a2200145 4500008004100000245007100041210006900112260001400181490000600195520190500201100002302106700002502129700002002154856003702174 2022 eng d00aImportance of the Spectral gap in Estimating Ground-State Energies0 aImportance of the Spectral gap in Estimating GroundState Energie c12/9/20220 v33 aThe 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.
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.abi789402003nas a2200253 4500008004100000245008100041210006900122260001400191520125700205100002301462700001801485700002001503700002101523700002001544700002001564700001701584700002101601700001401622700001701636700002401653700002001677700001501697856003701712 2021 eng d00aQuantum Computational Supremacy via High-Dimensional Gaussian Boson Sampling0 aQuantum Computational Supremacy via HighDimensional Gaussian Bos c2/24/20213 aPhotonics 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.1247401465nas a2200169 4500008004100000245007200041210006900113260001400182520093400196100002301130700002001153700002501173700002101198700002101219700001801240856003701258 2021 eng d00aTight bounds on the convergence of noisy random circuits to uniform0 aTight bounds on the convergence of noisy random circuits to unif c12/1/20213 aWe 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.
1 aDeshpande, Abhinav1 aFefferman, Bill1 aGorshkov, Alexey, V.1 aGullans, Michael1 aNiroula, Pradeep1 aShtanko, Oles uhttps://arxiv.org/abs/2112.0071601697nas a2200169 4500008004100000245008100041210006900122260001500191520115700206100002001363700002301383700001901406700002001425700002001445700002501465856003701490 2019 eng d00aComplexity phase diagram for interacting and long-range bosonic Hamiltonians0 aComplexity phase diagram for interacting and longrange bosonic H c06/10/20193 aRecent 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.
1 aMaskara, Nishad1 aDeshpande, Abhinav1 aTran, Minh, C.1 aEhrenberg, Adam1 aFefferman, Bill1 aGorshkov, Alexey, V. uhttps://arxiv.org/abs/1906.0417801947nas a2200397 4500008004100000245005400041210005400095260001500149520085000164100001801014700001601032700002301048700002301071700002201094700002401116700001901140700001801159700001801177700002001195700002501215700001801240700001801258700001901276700001901295700001601314700002301330700001901353700001701372700002401389700001901413700002201432700001901454700001901473700002001492856003701512 2019 eng d00aQuantum Computer Systems for Scientific Discovery0 aQuantum Computer Systems for Scientific Discovery c12/16/20193 aThe 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.
1 aAlexeev, Yuri1 aBacon, Dave1 aBrown, Kenneth, R.1 aCalderbank, Robert1 aCarr, Lincoln, D.1 aChong, Frederic, T.1 aDeMarco, Brian1 aEnglund, Dirk1 aFarhi, Edward1 aFefferman, Bill1 aGorshkov, Alexey, V.1 aHouck, Andrew1 aKim, Jungsang1 aKimmel, Shelby1 aLange, Michael1 aLloyd, Seth1 aLukin, Mikhail, D.1 aMaslov, Dmitri1 aMaunz, Peter1 aMonroe, Christopher1 aPreskill, John1 aRoetteler, Martin1 aSavage, Martin1 aThompson, Jeff1 aVazirani, Umesh uhttps://arxiv.org/abs/1912.0757712409nas a2200169 45000080041000002450055000412100055000963000047001514900008001985201188600206100002312092700002012115700001912135700002312154700002512177856003712202 2018 eng d00aDynamical phase transitions in sampling complexity0 aDynamical phase transitions in sampling complexity a12 pages, 4 figures. v3: published version0 v1213 aWe 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.
1 aBouland, Adam1 aFefferman, Bill1 aNirkhe, Chinmay1 aVazirani, Umesh uhttps://arxiv.org/abs/1803.0440205805nas a2200145 4500008004100000245004900041210004900090260001500139520537700154100002305531700002005554700002305574700002505597856003705622 2017 eng d00aComplexity of sampling as an order parameter0 aComplexity of sampling as an order parameter c2017/03/153 aWe 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.
1 aFefferman, Bill1 aFoss-Feig, Michael1 aGorshkov, Alexey, V. uhttps://arxiv.org/abs/1701.0316701705nas a2200121 4500008004100000245005700041210005500098260001500153520133500168100002001503700002401523856003601547 2016 eng d00aA Complete Characterization of Unitary Quantum Space0 aComplete Characterization of Unitary Quantum Space c2016/04/053 aWe 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.1 aFefferman, Bill1 aLin, Cedric, Yen-Yu uhttp://arxiv.org/abs/1604.0138401599nas a2200169 4500008004100000245004900041210004900090260001500139520107400154100001901228700002001247700002001267700002501287700002501312700002401337856006801361 2016 eng d00aComputational Security of Quantum Encryption0 aComputational Security of Quantum Encryption c2016/11/103 aQuantum-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.
1 aAlagic, Gorjan1 aBroadbent, Anne1 aFefferman, Bill1 aGagliardoni, Tommaso1 aSchaffner, Christian1 aJules, Michael, St. uhttps://link.springer.com/chapter/10.1007%2F978-3-319-49175-2_300861nas a2200121 4500008004100000245005500041210005500096260001500151520049300166100002000659700002400679856003600703 2016 eng d00aQuantum Merlin Arthur with Exponentially Small Gap0 aQuantum Merlin Arthur with Exponentially Small Gap c2016/01/083 aWe 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.1 aFefferman, Bill1 aLin, Cedric, Yen-Yu uhttp://arxiv.org/abs/1601.0197502209nas a2200121 4500008004100000245002700041210002400068260001500092520190500107100001902012700002002031856003602051 2016 eng d00aOn Quantum Obfuscation0 aQuantum Obfuscation c2016/02/043 aEncryption 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].1 aAlagic, Gorjan1 aFefferman, Bill uhttp://arxiv.org/abs/1602.0177121161nas a2200205 45000080041000000200022000410220014000632450069000772100068001462600015002143000016002294900007002455202053400252100002020786700002420806700002420830700002220854700002520876856005420901 2016 eng d a978-3-95977-013-2 a1868-896900aSpace-Efficient Error Reduction for Unitary Quantum Computations0 aSpaceEfficient Error Reduction for Unitary Quantum Computations c2016/04/27 a14:1--14:140 v553 aThis paper develops general space-efficient methods for error reduction for unitary quantum computation. Consider a polynomial-time quantum computation with completeness