Southwest Quantum Information and Technology

Boson sampling of many-body quantum random walkers on a lattice

Presenting Author: Gopikrishnan Muraleedharan, Center for Quantum Information and Control (CQuIC), University of New Mexico
Contributing Author(s): Akimasa Miyake and Ivan H. Deustch

The Boson sampling problem introduced by Aaronson and Arkhipov showed quantum supremacy in terms of sampling complexity for the output distribution of photons scattering from a linear optical network. We study here an analogous problem in the case of multiple boson continuous-time quantum random walkers on a lattice, e.g., Bosonic atoms in an optical lattice. Results are presented for the special case of a 1D lattice with nearest neighbor and uniform hopping amplitude. We show that the permanent of the unitary time evolution operator can be approximated in \( O \left({{2T}\choose{T}}^3 \log N \right)\) time, using an algorithm developed by M. Shwartz [1]. Thus the sampling problem is easy as long as the time of evolution (T) is constant or at least logarithmic in N. When the time of evolution passes the logarithmic scale, the algorithm takes exponential time. It is not clear if the sampling problem is hard in this regime. Periodic and hard wall boundary conditions lead to the same result when number of lattice sites are substantially larger than the number of particles. When extended to arbitrary hopping amplitudes and on-site interactions, this corresponds to sampling complexity for a general Bose-Hubbard model. 1: Moshe Schwartz, "Efficiently computing the permanent and Hafnian of some banded Toeplitz matrices" , Linear Algebra and its Applications, Volume 430, Issue 4, 2009, Pages 1364-1374, ISSN 0024-3795, http://dx.doi.org/10.1016/j.laa.2008.10.029.

(Session 5 : Thursday from 5:00pm - 7:00pm)