Appears in collection : PRACQSYS 2018: Principles and Applications of Control in Quantum Systems

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.