De Ivan Deutsch
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.
De Florian Marquardt
De Gary Steele
De Hendrik Bluhm
De Jean-Michel Raimond
De Alain Sarlette
De Sylvain Schwartz
De Sophia Economou
De Klaus Mølmer
De Howard M. Wiseman
De Michel Devoret
De Akira Furusawa
De Yanhong Xiao
De Alex Retzker
De Nicolas Didier
De Ivan Deutsch
De Mankei Tsang
De Aashish Clerk
De Valentina Parigi
De Rebing Wu
De Michael Biercuk
De Thomas Ayral
De Nana Liu
De Nana Liu
