Sampling complexity of interacting bosonic random walkers on a lattice

ORAL

Abstract

A central goal for modern quantum information science is to demonstrate computational speedup for experimentally feasible architectures in the noisy intermediate-scale regime. In a previous work, we studied this problem in the context of simulating boson sampling by noninteracting bosonic atoms on a one-dimensional lattice [1]. We extend these results to include Bose-Hubbard-type interactions. In the presence of weak interactions, we show that the output-sampling distribution is close to that of a free-boson sampler in the total variational distance. We calculate the scaling of the interaction-strength such that this total variational distance is bounded by a constant, demonstrating a regime where the sampling complexity is equivalent to that of the corresponding boson sampler. We close with some outlook for the possibility of applying worst-to-average-case reduction tools to extend these results beyond the perturbative regime.

[1] G. Muraleedharan et al. NJP, 21(5), 055003.

*
Google Quantum Algorithms Focused Award.

–

Presenters

  • Gopikrishnan Muraleedharan

    • University of New Mexico

Authors

  • Gopikrishnan Muraleedharan

    • University of New Mexico

  • Sayonee Ray

    • Physics and Astronomy, University of New Mexico, US
    • University of New Mexico
    • Physics, University of New Mexico

  • Adrian Chapman

    • Univ of Sydney
    • Physics, University of Sydney

  • Akimasa Miyake

    • University of New Mexico

  • Ivan Deutsch

    • University of New Mexico