RSS icon
Twitter icon
Facebook icon
Vimeo icon
YouTube icon

Complexity of sampling as an order parameter

April 28, 2017 - 12:10pm
Abhinav Deshpande
We consider the classical complexity of approximately simulating time evolution under spatially local quadratic bosonic Hamiltonians for time t. We obtain upper bounds on the scaling of t with the number of bosons, n, for which simulation is classically efficient. We also obtain a lower bound on the scaling of t with n for which this problem reduces to a general instance of the boson sampling problem and is hence hard, assuming the conjectures of Aaronson and Arkhipov [Proc. 43rd Annu. ACM Symp. Theory Comput. STOC '11]. 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.

Preprint: arXiv:1703.05332

PSC 2136

Subscribe to A Quantum Bit 

Quantum physics began with revolutionary discoveries in the early twentieth century and continues to be central in today’s physics research. Learn about quantum physics, bit by bit. From definitions to the latest research, this is your portal. Subscribe to receive regular emails from the quantum world. Previous Issues...

Sign Up Now

Sign up to receive A Quantum Bit in your email!

 Have an idea for A Quantum Bit? Submit your suggestions to