PIRSA:11070063

Super-polynomial Speed-up for a Quantum Computer on Boolean Trees

Kimmel, S. (2011). Super-polynomial Speed-up for a Quantum Computer on Boolean Trees. Perimeter Institute. https://pirsa.org/11070063

Kimmel, Shelby. Super-polynomial Speed-up for a Quantum Computer on Boolean Trees. Perimeter Institute, Jul. 20, 2011, https://pirsa.org/11070063 

          @misc{ pirsa_PIRSA:11070063,
            doi = {10.48660/11070063},
            url = {https://pirsa.org/11070063},
            author = {Kimmel, Shelby},
            keywords = {},
            language = {en},
            title = {Super-polynomial Speed-up for a Quantum Computer on Boolean Trees},
            publisher = {Perimeter Institute},
            year = {2011},
            month = {jul},
            note = {PIRSA:11070063 see, \url{https://pirsa.org}}
          }

Shelby Kimmel Massachusetts Institute of Technology (MIT)

DOI 10.48660/11070063
Collection
Talk Type Conference

Abstract

We can prove that for certain problems, quantum computers do better than classical computers. I will introduce the query complexity framework, which lets us compare classical and quantum computers, and then describe a problem where quantum computers do better than classical. The problem I will discuss is evaluating boolean trees with a promise on the input.