Facebook Twitter Instagram YouTube

Quantum computational supremacy in the sampling of bosonic random walkers on a one-dimensional lattice

Event Details

Event Dates: 

Friday, June 22, 2018 - 3:00pm

Seminar Location: 

  • JILA X317

Speaker Name(s): 

Ivan Deutsch

Speaker Affiliation(s): 

University of New Mexico
Seminar Type/Subject

Scientific Seminar Type: 

  • JILA Public Seminar

Event Details & Abstract: 

What level of quantum complexity cannot be efficiently simulated on a classical computer? While it is widely believed that a universal fault-tolerant quantum computer achieves such complexity, implementation of such a device is still a distant prospect. Nonetheless, more modest devices designed for a limited task could supersede the power of a classical computer and achieve so-called “quantum supremacy”. In particular, a quantum device can yield random outcomes sampled from a probability distribution such that no classical computer could efficiently simulate its statistics. Aaronson and Arkhipov showed that quantum supremacy could arise from “sampling complexity” in the most unlikely of places:

the counting of photons outputted from a linear optical network.  In our work we extend this “Boson Sampling” paradigm to the case of a noninteracting bosonic random walkers on a 1D lattice. Our motivation is two-fold. Firstly, we seek to understand the minimal complexity necessary to achieve quantum supremacy. Secondly, this paradigm can be realized in physical platforms that might lead to more scalable implementations, e.g., ultracold bosonic atoms in an optical lattice.  We illustrate an experimental realization in a spinor optical lattice. We further discuss the general relationship between sampling complexity and the complexity of quantum simulation of many-body systems.