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

Understand

We study the sampling complexity of a probability distribution associated with an ensemble ofidentical noninteracting bosons undergoing a quantum random walk on a one-dimensional lattice.With uniform nearest-neighbor hopping we show that one can efficiently sample the distribution fortimes logarithmic in the size of the system, while for longer times there is no known efficient samplingalgorithm.

• With time-dependent hopping and optimal control, we design the time evolution toapproximate an arbitrary Haar-random unitary map analogous to that designed for photons in alinear optical network.
• This approach highlights a route to generating quantum complexity byoptimal control only of a single-body unitary matrix.
• We study this in the context of two potentialexperimental realizations: a spinor optical lattice of ultracold atoms and a quantum gas microscope.