PIRSA:10010009

The Computational Complexity of Linear Optics

Aaronson, S. (2010). The Computational Complexity of Linear Optics. Perimeter Institute. https://pirsa.org/10010009

Aaronson, Scott. The Computational Complexity of Linear Optics. Perimeter Institute, Jan. 25, 2010, https://pirsa.org/10010009 

          @misc{ pirsa_PIRSA:10010009,
            doi = {10.48660/10010009},
            url = {https://pirsa.org/10010009},
            author = {Aaronson, Scott},
            keywords = {Quantum Information},
            language = {en},
            title = {The Computational Complexity of Linear Optics},
            publisher = {Perimeter Institute},
            year = {2010},
            month = {jan},
            note = {PIRSA:10010009 see, \url{https://pirsa.org}}
          }

Scott Aaronson The University of Texas at Austin

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

Abstract

I'll discuss some work-in-progress about the computational complexity of simulating the extremely "simple" quantum systems that arise in linear optics experiments. I'll show that *either* one can describe an experiment, vastly easier than building a universal quantum computer, that would test whether Nature is performing nontrivial quantum computation, or else one can give surprising new algorithms for approximating the permanent. Audience feedback as to which of these possibilities is the right one is sought. Joint work with Alex Arkhipov.