%0 Journal Article %J Quantum %D 2023 %T Page curves and typical entanglement in linear optics %A Joseph T. Iosue %A Adam Ehrenberg %A Dominik Hangleiter %A Abhinav Deshpande %A Alexey V. Gorshkov %X

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.

%B Quantum %V 7 %P 1017 %8 5/18/2023 %G eng %U https://arxiv.org/abs/2209.06838 %R 10.22331/q-2023-05-23-1017 %0 Journal Article %D 2023 %T A sharp phase transition in linear cross-entropy benchmarking %A Brayden Ware %A Abhinav Deshpande %A Dominik Hangleiter %A Pradeep Niroula %A Bill Fefferman %A Alexey V. Gorshkov %A Michael J. Gullans %X

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.

%8 5/8/2023 %G eng %U https://arxiv.org/abs/2305.04954 %0 Journal Article %D 2023 %T Transition of Anticoncentration in Gaussian Boson Sampling %A Adam Ehrenberg %A Joseph T. Iosue %A Abhinav Deshpande %A Dominik Hangleiter %A Alexey V. Gorshkov %X

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.

%8 12/13/2023 %G eng %U https://arxiv.org/abs/2312.08433 %0 Journal Article %J Phys. Rev. Research %D 2022 %T Implementing a Fast Unbounded Quantum Fanout Gate Using Power-Law Interactions %A Andrew Y. Guo %A Abhinav Deshpande %A Su-Kuan Chu %A Zachary Eldredge %A Przemyslaw Bienias %A Dhruv Devulapalli %A Yuan Su %A Andrew M. Childs %A Alexey V. Gorshkov %X

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

%B Phys. Rev. Research %V 4 %8 10/27/2022 %G eng %U https://arxiv.org/abs/2007.00662 %N L042016 %R https://doi.org/10.1103/PhysRevResearch.4.L042016 %0 Journal Article %J PRX Quantum %D 2022 %T Importance of the Spectral gap in Estimating Ground-State Energies %A Abhinav Deshpande %A Alexey V. Gorshkov %A Bill Fefferman %X

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.

%B PRX Quantum %V 3 %8 12/9/2022 %G eng %U https://arxiv.org/abs/2007.11582 %R 10.1103/prxquantum.3.040327 %0 Journal Article %J Science Advances %D 2022 %T Quantum computational advantage via high-dimensional Gaussian boson sampling %A Abhinav Deshpande %A Arthur Mehta %A Trevor Vincent %A Nicolas Quesada %A Marcel Hinsche %A Marios Ioannou %A Lars Madsen %A Jonathan Lavoie %A Haoyu Qi %A Jens Eisert %A Dominik Hangleiter %A Bill Fefferman %A Ish Dhand %X

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.

%B Science Advances %V 8 %P eabi7894 %8 1/5/2022 %G eng %U https://www.science.org/doi/abs/10.1126/sciadv.abi7894 %R 10.1126/sciadv.abi7894 %0 Journal Article %D 2022 %T Simulation Complexity of Many-Body Localized Systems %A Adam Ehrenberg %A Abhinav Deshpande %A Christopher L. Baldwin %A Dmitry A. Abanin %A Alexey V. Gorshkov %X

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

%8 5/25/2022 %G eng %U https://arxiv.org/abs/2205.12967 %0 Journal Article %D 2021 %T Quantum Computational Supremacy via High-Dimensional Gaussian Boson Sampling %A Abhinav Deshpande %A Arthur Mehta %A Trevor Vincent %A Nicolas Quesada %A Marcel Hinsche %A Marios Ioannou %A Lars Madsen %A Jonathan Lavoie %A Haoyu Qi %A Jens Eisert %A Dominik Hangleiter %A Bill Fefferman %A Ish Dhand %X

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.

%8 2/24/2021 %G eng %U https://arxiv.org/abs/2102.12474 %0 Journal Article %D 2021 %T Tight bounds on the convergence of noisy random circuits to uniform %A Abhinav Deshpande %A Bill Fefferman %A Alexey V. Gorshkov %A Michael Gullans %A Pradeep Niroula %A Oles Shtanko %X

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. 

%8 12/1/2021 %G eng %U https://arxiv.org/abs/2112.00716 %0 Journal Article %J Phys. Rev. Research %D 2020 %T Entanglement Bounds on the Performance of Quantum Computing Architectures %A Zachary Eldredge %A Leo Zhou %A Aniruddha Bapat %A James R. Garrison %A Abhinav Deshpande %A Frederic T. Chong %A Alexey V. Gorshkov %X

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

%B Phys. Rev. Research %V 2 %8 9/22/2020 %G eng %U https://arxiv.org/abs/1908.04802 %N 033316 %R https://doi.org/10.1103/PhysRevResearch.2.033316 %0 Journal Article %J Physical Review X %D 2020 %T Hierarchy of linear light cones with long-range interactions %A Minh C. Tran %A Chi-Fang Chen %A Adam Ehrenberg %A Andrew Y. Guo %A Abhinav Deshpande %A Yifan Hong %A Zhe-Xuan Gong %A Alexey V. Gorshkov %A Andrew Lucas %X

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

%B Physical Review X %V 10 %8 5/29/2020 %G eng %U https://arxiv.org/abs/2001.11509 %N 031009 %R https://doi.org/10.1103/PhysRevX.10.031009 %0 Journal Article %D 2020 %T Limits on Classical Simulation of Free Fermions with Dissipation %A Oles Shtanko %A Abhinav Deshpande %A Paul S. Julienne %A Alexey V. Gorshkov %X

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

%8 5/21/2020 %G eng %U https://arxiv.org/abs/2005.10840 %0 Journal Article %D 2020 %T Optimal state transfer and entanglement generation in power-law interacting systems %A Minh C. Tran %A Abhinav Deshpande %A Andrew Y. Guo %A Andrew Lucas %A Alexey V. Gorshkov %X

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

%8 10/6/2020 %G eng %U https://arxiv.org/abs/2010.02930 %0 Journal Article %D 2019 %T Complexity phase diagram for interacting and long-range bosonic Hamiltonians %A Nishad Maskara %A Abhinav Deshpande %A Minh C. Tran %A Adam Ehrenberg %A Bill Fefferman %A Alexey V. Gorshkov %X

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. 

%8 06/10/2019 %G eng %U https://arxiv.org/abs/1906.04178 %0 Journal Article %J Phys. Rev. Lett. %D 2019 %T Interference of Temporally Distinguishable Photons Using Frequency-Resolved Detection %A Venkata Vikram Orre %A Elizabeth A. Goldschmidt %A Abhinav Deshpande %A Alexey V. Gorshkov %A Vincenzo Tamma %A Mohammad Hafezi %A Sunil Mittal %X

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

%B Phys. Rev. Lett. %V 123 %8 9/24/2019 %G eng %U https://arxiv.org/abs/1904.03222 %N 123603 %R https://doi.org/10.1103/PhysRevLett.123.123603 %0 Journal Article %J Phys. Rev. Lett. %D 2018 %T Dynamical phase transitions in sampling complexity %A Abhinav Deshpande %A Bill Fefferman %A Minh C. Tran %A Michael Foss-Feig %A Alexey V. Gorshkov %X

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 t due to evolution generated by spatially local quadratic bosonic Hamiltonians. We obtain an upper bound on the scaling of t with the number of bosons n for which approximate sampling is classically efficient. We also obtain a lower bound on the scaling of t with n for which any instance of the boson sampling problem reduces to this problem and hence implies that the problem is hard, assuming the conjectures of Aaronson and Arkhipov [Proc. 43rd Annu. ACM Symp. Theory Comput. STOC '11]. This establishes a dynamical phase transition in sampling complexity. Further, we show that systems in the Anderson-localized phase are always easy to sample from at arbitrarily long times. We view these results in the light of classifying phases of physical systems based on parameters in the Hamiltonian. In doing so, we combine ideas from mathematical physics and computational complexity to gain insight into the behavior of condensed matter, atomic, molecular and optical systems.

%B Phys. Rev. Lett. %V 121 %P 12 pages, 4 figures. v3: published version %G eng %U https://arxiv.org/abs/1703.05332 %N 030501 %R https://doi.org/10.1103/PhysRevLett.121.030501 %0 Journal Article %D 2017 %T Complexity of sampling as an order parameter %A Abhinav Deshpande %A Bill Fefferman %A Michael Foss-Feig %A Alexey V. Gorshkov %X

We consider the classical complexity of approximately simulating time evolution under spatially local quadratic bosonic Hamiltonians for time t. We obtain upper and lower bounds on the scaling of twith the number of bosons, n, for which simulation, cast as a sampling problem, is classically efficient and provably hard, respectively. We view these results in the light of classifying phases of physical systems based on parameters in the Hamiltonian and conjecture a link to dynamical phase transitions. In doing so, we combine ideas from mathematical physics and computational complexity to gain insight into the behavior of condensed matter systems.

%8 2017/03/15 %G eng %U https://arxiv.org/abs/1703.05332 %0 Journal Article %J Journal of Statistical Mechanics: Theory and Experiment %D 2016 %T Lattice Laughlin states on the torus from conformal field theory %A Abhinav Deshpande %A Anne E B Nielsen %X Conformal field theory has turned out to be a powerful tool to derive two-dimensional lattice models displaying fractional quantum Hall physics. So far most of the work has been for lattices with open boundary conditions in at least one of the two directions, but it is desirable to also be able to handle the case of periodic boundary conditions. Here, we take steps in this direction by deriving analytical expressions for a family of conformal field theory states on the torus that is closely related to the family of bosonic and fermionic Laughlin states. We compute how the states transform when a particle is moved around the torus and when the states are translated or rotated, and we provide numerical evidence in particular cases that the states become orthonormal up to a common factor for large lattices. We use these results to find the S -matrix of the states, which turns out to be the same as for the continuum Laughlin states. Finally, we show that when the states are defined on a square lattice with suitable lattice spacing they practically coincide with the Laughlin states restricted to a lattice. %B Journal of Statistical Mechanics: Theory and Experiment %V 2016 %P 013102 %8 2016/01/28 %G eng %U http://stacks.iop.org/1742-5468/2016/i=1/a=013102 %0 Journal Article %J Physical Review A %D 2014 %T Remote tomography and entanglement swapping via von Neumann–Arthurs–Kelly interaction %A S. M. Roy %A Abhinav Deshpande %A Nitica Sakharwade %X We propose an interaction-based method for remote tomography and entanglement swapping. Alice arranges a von Neumann-Arthurs-Kelly interaction between a system particle P and two apparatus particles A1,A2, and then transports the latter to Bob. Bob can reconstruct the unknown initial state of particle P not received by him by quadrature measurements on A1,A2. Further, if another particle P′ in Alice's hands is EPR entangled with P, it will be EPR entangled with the distant pair A1,A2. This method will be contrasted with the usual teleportation protocols. %B Physical Review A %V 89 %P 052107 %8 2014/05/09 %G eng %U http://journals.aps.org/pra/abstract/10.1103/PhysRevA.89.052107 %N 5 %R http://dx.doi.org/10.1103/PhysRevA.89.052107