02008nas 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.0683801745nas 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.0495401909nas a2200157 4500008004100000245006300041210006300104260001500167520141800182100002001600700002201620700002301642700002401665700002501689856003701714 2023 eng d00aTransition of Anticoncentration in Gaussian Boson Sampling0 aTransition of Anticoncentration in Gaussian Boson Sampling c12/13/20233 aGaussian 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.0843301951nas a2200217 4500008004100000245008300041210006900124260001500193490000600208520129200214100002001506700002301526700001701549700002201566700002401588700002301612700001301635700002301648700002501671856003701696 2022 eng d00aImplementing a Fast Unbounded Quantum Fanout Gate Using Power-Law Interactions0 aImplementing a Fast Unbounded Quantum Fanout Gate Using PowerLaw c10/27/20220 v43 aThe standard circuit model for quantum computation presumes the ability to directly perform gates between arbitrary pairs of qubits, which is unlikely to be practical for large-scale experiments. Power-law interactions with strength decaying as 1/rα in the distance r provide an experimentally realizable resource for information processing, whilst still retaining long-range connectivity. We leverage the power of these interactions to implement a fast quantum fanout gate with an arbitrary number of targets. Our implementation allows the quantum Fourier transform (QFT) and Shor's algorithm to be performed on a D-dimensional lattice in time logarithmic in the number of qubits for interactions with α≤D. As a corollary, we show that power-law systems with α≤D are difficult to simulate classically even for short times, under a standard assumption that factoring is classically intractable. Complementarily, we develop a new technique to give a general lower bound, linear in the size of the system, on the time required to implement the QFT and the fanout gate in systems that are constrained by a linear light cone. This allows us to prove an asymptotically tighter lower bound for long-range systems than is possible with previously available techniques.
1 aGuo, Andrew, Y.1 aDeshpande, Abhinav1 aChu, Su-Kuan1 aEldredge, Zachary1 aBienias, Przemyslaw1 aDevulapalli, Dhruv1 aSu, Yuan1 aChilds, Andrew, M.1 aGorshkov, Alexey, V. uhttps://arxiv.org/abs/2007.0066202357nas 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.abi789401610nas a2200157 4500008004100000245005700041210005600098260001400154520112700168100002001295700002301315700002901338700002301367700002501390856003701415 2022 eng d00aSimulation Complexity of Many-Body Localized Systems0 aSimulation Complexity of ManyBody Localized Systems c5/25/20223 aWe use complexity theory to rigorously investigate the difficulty of classically simulating evolution under many-body localized (MBL) Hamiltonians. Using the defining feature that MBL systems have a complete set of quasilocal integrals of motion (LIOMs), we demonstrate a transition in the classical complexity of simulating such systems as a function of evolution time. On one side, we construct a quasipolynomial-time tensor-network-inspired algorithm for strong simulation of 1D MBL systems (i.e., calculating the expectation value of arbitrary products of local observables) evolved for any time polynomial in the system size. On the other side, we prove that even weak simulation, i.e. sampling, becomes formally hard after an exponentially long evolution time, assuming widely believed conjectures in complexity theory. Finally, using the consequences of our classical simulation results, we also show that the quantum circuit complexity for MBL systems is sublinear in evolution time. This result is a counterpart to a recent proof that the complexity of random quantum circuits grows linearly in time.
1 aEhrenberg, Adam1 aDeshpande, Abhinav1 aBaldwin, Christopher, L.1 aAbanin, Dmitry, A.1 aGorshkov, Alexey, V. uhttps://arxiv.org/abs/2205.1296702003nas 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.0071601493nas a2200193 4500008004100000245007800041210006900119260001400188490000600202520090100208100002201109700001401131700002101145700002401166700002301190700002401213700002501237856003701262 2020 eng d00aEntanglement Bounds on the Performance of Quantum Computing Architectures0 aEntanglement Bounds on the Performance of Quantum Computing Arch c9/22/20200 v23 aThere are many possible architectures for future quantum computers that designers will need to choose between. However, the process of evaluating a particular connectivity graph's performance as a quantum architecture can be difficult. In this paper, we establish a connection between a quantity known as the isoperimetric number and a lower bound on the time required to create highly entangled states. The metric we propose counts resources based on the use of two-qubit unitary operations, while allowing for arbitrarily fast measurements and classical feedback. We describe how these results can be applied to the evaluation of the hierarchical architecture proposed in Phys. Rev. A 98, 062328 (2018). We also show that the time-complexity bound we place on the creation of highly-entangled states can be saturated up to a multiplicative factor logarithmic in the number of qubits.
1 aEldredge, Zachary1 aZhou, Leo1 aBapat, Aniruddha1 aGarrison, James, R.1 aDeshpande, Abhinav1 aChong, Frederic, T.1 aGorshkov, Alexey, V. uhttps://arxiv.org/abs/1908.0480202312nas a2200217 4500008004100000245006500041210006400106260001400170490000700184520168700191100001901878700001901897700002001916700002001936700002301956700001601979700001901995700002502014700001802039856003702057 2020 eng d00aHierarchy of linear light cones with long-range interactions0 aHierarchy of linear light cones with longrange interactions c5/29/20200 v103 aIn quantum many-body systems with local interactions, quantum information and entanglement cannot spread outside of a "linear light cone," which expands at an emergent velocity analogous to the speed of light. Yet most non-relativistic physical systems realized in nature have long-range interactions: two degrees of freedom separated by a distance r interact with potential energy V(r)∝1/rα. In systems with long-range interactions, we rigorously establish a hierarchy of linear light cones: at the same α, some quantum information processing tasks are constrained by a linear light cone while others are not. In one spatial dimension, commutators of local operators 〈ψ|[Ox(t),Oy]|ψ〉 are negligible in every state |ψ〉 when |x−y|≳vt, where v is finite when α>3 (Lieb-Robinson light cone); in a typical state |ψ〉 drawn from the infinite temperature ensemble, v is finite when α>52 (Frobenius light cone); in non-interacting systems, v is finite in every state when α>2 (free light cone). These bounds apply to time-dependent systems and are optimal up to subalgebraic improvements. Our theorems regarding the Lieb-Robinson and free light cones, and their tightness, also generalize to arbitrary dimensions. We discuss the implications of our bounds on the growth of connected correlators and of topological order, the clustering of correlations in gapped systems, and the digital simulation of systems with long-range interactions. In addition, we show that quantum state transfer and many-body quantum chaos are bounded by the Frobenius light cone, and therefore are poorly constrained by all Lieb-Robinson bounds.
1 aTran, Minh, C.1 aChen, Chi-Fang1 aEhrenberg, Adam1 aGuo, Andrew, Y.1 aDeshpande, Abhinav1 aHong, Yifan1 aGong, Zhe-Xuan1 aGorshkov, Alexey, V.1 aLucas, Andrew uhttps://arxiv.org/abs/2001.1150901547nas a2200145 4500008004100000245006900041210006900110260001400179520108200193100001801275700002301293700002301316700002501339856003701364 2020 eng d00aLimits on Classical Simulation of Free Fermions with Dissipation0 aLimits on Classical Simulation of Free Fermions with Dissipation c5/21/20203 aFree-fermionic systems are a valuable, but limited, class of many-body problems efficiently simulable on a classical computer. We examine how classical simulability of noninteracting fermions is modified in the presence of Markovian dissipation described by quadratic Lindblad operators, including, for example, incoherent transitions or pair losses. On the one hand, we establish three broad classes of Markovian dynamics that are efficiently simulable classically, by devising efficient algorithms. On the other hand, we demonstrate that, in the worst case, simulating Markovian dynamics with quadratic Lindblad operators is at least as hard as simulating universal quantum circuits. This result is applicable to an experimentally relevant setting in cold atomic systems, where magnetic Feshbach resonances can be used to engineer the desired dissipation. For such systems, our hardness result provides a direct scheme for dissipation-assisted quantum computing with a potential significant advantage in the speed of two-qubit gates and, therefore, in error tolerance.
1 aShtanko, Oles1 aDeshpande, Abhinav1 aJulienne, Paul, S.1 aGorshkov, Alexey, V. uhttps://arxiv.org/abs/2005.1084001333nas a2200157 4500008004100000245008800041210006900129260001400198520082100212100001901033700002301052700002001075700001801095700002501113856003701138 2020 eng d00aOptimal state transfer and entanglement generation in power-law interacting systems0 aOptimal state transfer and entanglement generation in powerlaw i c10/6/20203 aWe present an optimal protocol for encoding an unknown qubit state into a multiqubit Greenberger-Horne-Zeilinger-like state and, consequently, transferring quantum information in large systems exhibiting power-law (1/rα) interactions. For all power-law exponents α between d and 2d+1, where d is the dimension of the system, the protocol yields a polynomial speedup for α>2d and a superpolynomial speedup for α≤2d, compared to the state of the art. For all α>d, the protocol saturates the Lieb-Robinson bounds (up to subpolynomial corrections), thereby establishing the optimality of the protocol and the tightness of the bounds in this regime. The protocol has a wide range of applications, including in quantum sensing, quantum computing, and preparation of topologically ordered states.
1 aTran, Minh, C.1 aDeshpande, Abhinav1 aGuo, Andrew, Y.1 aLucas, Andrew1 aGorshkov, Alexey, V. uhttps://arxiv.org/abs/2010.0293001697nas 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.0417801480nas a2200193 4500008004100000245009000041210006900131260001400200490000800214520086300222100002601085700003101111700002301142700002501165700002001190700002101210700001801231856003701249 2019 eng d00aInterference of Temporally Distinguishable Photons Using Frequency-Resolved Detection0 aInterference of Temporally Distinguishable Photons Using Frequen c9/24/20190 v1233 aWe demonstrate quantum interference of three photons that are distinguishable in time, by resolving them in the conjugate parameter, frequency. We show that the multiphoton interference pattern in our setup can be manipulated by tuning the relative delays between the photons, without the need for reconfiguring the optical network. Furthermore, we observe that the symmetries of our optical network and the spectral amplitude of the input photons are manifested in the interference pattern. Moreover, we demonstrate time-reversed HOM-like interference in the spectral correlations using time-bin entangled photon pairs. By adding a time-varying dispersion using a phase modulator, our setup can be used to realize dynamically reconfigurable and scalable boson sampling in the time domain as well as frequency-resolved multiboson correlation sampling.
1 aOrre, Venkata, Vikram1 aGoldschmidt, Elizabeth, A.1 aDeshpande, Abhinav1 aGorshkov, Alexey, V.1 aTamma, Vincenzo1 aHafezi, Mohammad1 aMittal, Sunil uhttps://arxiv.org/abs/1904.0322212409nas 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
We consider the classical complexity of approximately simulating time evolution under spatially local quadratic bosonic Hamiltonians for time