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 - 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
UR - https://arxiv.org/abs/1703.05332
CP - 030501
U5 - https://doi.org/10.1103/PhysRevLett.121.030501
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 -