PIRSA:06020011

Quantum computation: where does the speedup come from?

Bub, J. (2006). Quantum computation: where does the speedup come from?. Perimeter Institute. https://pirsa.org/06020011

Bub, Jeffrey. Quantum computation: where does the speedup come from?. Perimeter Institute, Feb. 08, 2006, https://pirsa.org/06020011 

          @misc{ pirsa_PIRSA:06020011,
            doi = {10.48660/06020011},
            url = {https://pirsa.org/06020011},
            author = {Bub, Jeffrey},
            keywords = {Quantum Information, Quantum Foundations},
            language = {en},
            title = {Quantum computation: where does the speedup come from?},
            publisher = {Perimeter Institute},
            year = {2006},
            month = {feb},
            note = {PIRSA:06020011 see, \url{https://pirsa.org}}
          }

Jeffrey Bub University of Maryland, College Park

DOI 10.48660/06020011
Collection
Talk Type Scientific Series
Subject

Abstract

I look at the information-processing involved in a quantum computation, in terms of the difference between the Boolean logic underlying a classical computation and the non-Boolean logic represented by the projective geometry of Hilbert space, in which the subspace structure of Hilbert space replaces the set-theoretic structure of classical logic. I show that the original Deutsch XOR algorithm, Simon's algorithm, and Shor's algorithm all involve a similar geometric formulation. In terms of this picture, I consider the question of where the speedup relative to classical algorithms comes from.