PIRSA:14040077

Quantum Computing with Noninteracting Particles

Arkhipov, A. (2014). Quantum Computing with Noninteracting Particles. Perimeter Institute. https://pirsa.org/14040077

Arkhipov, Alex. Quantum Computing with Noninteracting Particles. Perimeter Institute, Apr. 02, 2014, https://pirsa.org/14040077 

          @misc{ pirsa_PIRSA:14040077,
            doi = {10.48660/14040077},
            url = {https://pirsa.org/14040077},
            author = {Arkhipov, Alex},
            keywords = {Quantum Information},
            language = {en},
            title = {Quantum Computing with Noninteracting Particles},
            publisher = {Perimeter Institute},
            year = {2014},
            month = {apr},
            note = {PIRSA:14040077 see, \url{https://pirsa.org}}
          }

Alex Arkhipov Massachusetts Institute of Technology (MIT)

Talk numberPIRSA:14040077
DOI10.48660/14040077
Collection
Talk Type Scientific Series
Subject

Abstract

We introduce an abstract model of computation corresponding to an experiment in which identical, non-interacting bosons are sent through a non-adaptive linear circuit before being measured. We show that despite the very limited nature of the model, an exact classical simulation would imply a collapse of the polynomial hierarchy. Moreover, under plausible conjectures, a "noisy" approximate simulation would do the same. This gives evidence that quantum computers can sample a distribution that classical computers cannot even approximate, even when restricted to use no entanglement except that arising from particles being identical. We briefly discuss experimental prospects for realizing this model. This talk is based on The Computational Complexity of Linear Optics [STOC '11], which is joint work with Scott Aaronson.