The Territory Around BQP: Results and Open Problems

          @misc{ scivideos_PIRSA:10050096,
            doi = {10.48660/10050096},
            url = {https://pirsa.org/10050096},
            author = {Aaronson, Scott},
            keywords = {Quantum Foundations},
            language = {en},
            title = {The Territory Around BQP: Results and Open Problems},
            publisher = {Perimeter Institute for Theoretical Physics},
            year = {2011},
            month = {may},
            note = {PIRSA:10050096 see, \url{https://scivideos.org/pirsa/10050096}}
          }
          

Abstract

In this talk, I'll survey various "foils" of BQP (Bounded-Error Quantum Polynomial-Time) that have been proposed: that is, changes to the quantum model of computation that make it either more or less powerful. Possible topics include: postselected quantum computing, quantum computing with nonlinear Schrodinger equation, quantum computing with non-unitary linear transformations, quantum computing with hidden variables, linear-optical quantum computing, quantum computing with restricted gate sets, quantum computing with separable mixed states, quantum computing over finite fields, and more depending on audience interest.