## Abstracts

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

Presenting Author: Gopikrishnan Muraleedharan, University of New Mexico CQuIC
Contributing Author(s): Christopher Jackson, Akimasa Miyake, Ivan H Deutsch

A quantum device that performa a computational task more efficiently than a current state-of-the-art classical computer is said to demonstrate quantum computational supremacy QCS. One path to achieving QCS 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, and dubbed boson sampling the context of identical photons scattering from a linear optical network. We generalize this to noninteracting bosonic quantum random walkers on a 1D lattice, and study the complexity of the resulting probability distribution obtained in static and time dependent lattices. We consider physical realizations based on controlled transport of ultra-cold atoms in a spinor optical lattice as well as a quantum gas microscope using optical tweezers. We quantify analytically and numerically how a sequence of random Hamiltonian evolution approaches Haar random SU ($$d$$) unitary. This, together with identical particle interference can yield QCS. We also study how much pseudorandomness is necessary to demonstrate QCS in terms of closeness to a t-design.

(Session 9a : Monday from 4:15pm - 4:45pm)

SQuInT Chief Organizer
Akimasa Miyake, Associate Professor
amiyake@unm.edu

SQuInT Local Organizers
Rafael Alexander, Postdoctoral Fellow
Chris Jackson, Postdoctoral Fellow