TY - JOUR T1 - Page curves and typical entanglement in linear optics JF - Quantum Y1 - 2023 A1 - Joseph T. Iosue A1 - Adam Ehrenberg A1 - Dominik Hangleiter A1 - Abhinav Deshpande A1 - Alexey V. Gorshkov AB -

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.

VL - 7 U4 - 1017 UR - https://arxiv.org/abs/2209.06838 U5 - 10.22331/q-2023-05-23-1017 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 - Transition of Anticoncentration in Gaussian Boson Sampling Y1 - 2023 A1 - Adam Ehrenberg A1 - Joseph T. Iosue A1 - Abhinav Deshpande A1 - Dominik Hangleiter A1 - Alexey V. Gorshkov AB -

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.

UR - https://arxiv.org/abs/2312.08433 ER - TY - JOUR T1 - Implementing a Fast Unbounded Quantum Fanout Gate Using Power-Law Interactions JF - Phys. Rev. Research Y1 - 2022 A1 - Andrew Y. Guo A1 - Abhinav Deshpande A1 - Su-Kuan Chu A1 - Zachary Eldredge A1 - Przemyslaw Bienias A1 - Dhruv Devulapalli A1 - Yuan Su A1 - Andrew M. Childs A1 - Alexey V. Gorshkov AB -

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. 

VL - 4 UR - https://arxiv.org/abs/2007.00662 CP - L042016 U5 - https://doi.org/10.1103/PhysRevResearch.4.L042016 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.

VL - 3 UR - https://arxiv.org/abs/2007.11582 U5 - 10.1103/prxquantum.3.040327 ER - TY - JOUR T1 - Quantum computational advantage via high-dimensional Gaussian boson sampling JF - Science Advances Y1 - 2022 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 -

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 - Simulation Complexity of Many-Body Localized Systems Y1 - 2022 A1 - Adam Ehrenberg A1 - Abhinav Deshpande A1 - Christopher L. Baldwin A1 - Dmitry A. Abanin A1 - Alexey V. Gorshkov AB -

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. 

UR - https://arxiv.org/abs/2205.12967 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 - Entanglement Bounds on the Performance of Quantum Computing Architectures JF - Phys. Rev. Research Y1 - 2020 A1 - Zachary Eldredge A1 - Leo Zhou A1 - Aniruddha Bapat A1 - James R. Garrison A1 - Abhinav Deshpande A1 - Frederic T. Chong A1 - Alexey V. Gorshkov AB -

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.

VL - 2 UR - https://arxiv.org/abs/1908.04802 CP - 033316 U5 - https://doi.org/10.1103/PhysRevResearch.2.033316 ER - TY - JOUR T1 - Hierarchy of linear light cones with long-range interactions JF - Physical Review X Y1 - 2020 A1 - Minh C. Tran A1 - Chi-Fang Chen A1 - Adam Ehrenberg A1 - Andrew Y. Guo A1 - Abhinav Deshpande A1 - Yifan Hong A1 - Zhe-Xuan Gong A1 - Alexey V. Gorshkov A1 - Andrew Lucas AB -

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.

VL - 10 UR - https://arxiv.org/abs/2001.11509 CP - 031009 U5 - https://doi.org/10.1103/PhysRevX.10.031009 ER - TY - JOUR T1 - Limits on Classical Simulation of Free Fermions with Dissipation Y1 - 2020 A1 - Oles Shtanko A1 - Abhinav Deshpande A1 - Paul S. Julienne A1 - Alexey V. Gorshkov AB -

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.

UR - https://arxiv.org/abs/2005.10840 ER - TY - JOUR T1 - Optimal state transfer and entanglement generation in power-law interacting systems Y1 - 2020 A1 - Minh C. Tran A1 - Abhinav Deshpande A1 - Andrew Y. Guo A1 - Andrew Lucas A1 - Alexey V. Gorshkov AB -

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. 

UR - https://arxiv.org/abs/2010.02930 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 - Interference of Temporally Distinguishable Photons Using Frequency-Resolved Detection JF - Phys. Rev. Lett. Y1 - 2019 A1 - Venkata Vikram Orre A1 - Elizabeth A. Goldschmidt A1 - Abhinav Deshpande A1 - Alexey V. Gorshkov A1 - Vincenzo Tamma A1 - Mohammad Hafezi A1 - Sunil Mittal AB -

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.

VL - 123 UR - https://arxiv.org/abs/1904.03222 CP - 123603 U5 - https://doi.org/10.1103/PhysRevLett.123.123603 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 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.

VL - 121 U4 - 12 pages, 4 figures. v3: published version UR - https://arxiv.org/abs/1703.05332 CP - 030501 U5 - https://doi.org/10.1103/PhysRevLett.121.030501 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 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.

UR - https://arxiv.org/abs/1703.05332 ER - TY - JOUR T1 - Lattice Laughlin states on the torus from conformal field theory JF - Journal of Statistical Mechanics: Theory and Experiment Y1 - 2016 A1 - Abhinav Deshpande A1 - Anne E B Nielsen AB - 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. VL - 2016 U4 - 013102 UR - http://stacks.iop.org/1742-5468/2016/i=1/a=013102 ER - TY - JOUR T1 - Remote tomography and entanglement swapping via von Neumann–Arthurs–Kelly interaction JF - Physical Review A Y1 - 2014 A1 - S. M. Roy A1 - Abhinav Deshpande A1 - Nitica Sakharwade AB - 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. VL - 89 U4 - 052107 UR - http://journals.aps.org/pra/abstract/10.1103/PhysRevA.89.052107 CP - 5 U5 - http://dx.doi.org/10.1103/PhysRevA.89.052107 ER -