PIRSA:14040077 Scientific Series Quantum Information

DOI10.48660/14040077

Series: Perimeter Institute Quantum Discussions

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}}
}

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.

Resources

Next talk

Related Talks