Boson sampling of multiple quantum random walkers on a lattice

A quantum device capable of performing an information-processing task more efficiently than current state of the art classical computers is said to demonstrate “quantum supremacy”. One path to achieving this in the short term is via “sampling complexity;” random samples are drawn from a probability distribution by measuring a complex quantum state in a defined basis. Surprisingly, a gas of identical noninteracting bosons can yield sampling complexity due solely to quantum statistics, as shown by Aaronson and Arkhipov, dubbed “boson sampling,” in the context of identical photons scattering from a linear optical network. We generalize this to noninteracting bosonic quantum random walkers on a 1D lattice. We study the quantum complexity of the probability distribution obtained through a discrete-time quantum random walk. Here the goal is to approximate a Haar-random unitary map on a single boson, and quantum statistics yields the many-body complexity. We consider a physical realization based on controlled transport of ultra-cold atoms in a spinor optical lattice. We quantify the degree of randomness (and thus complexity) of the unitarity map using different techniques from random matrix theory, unitary t-designs, and Renyi entropy.