PIRSA:13110090

Quantum Adversary (Upper) Bound

Kimmel, S. (2013). Quantum Adversary (Upper) Bound. Perimeter Institute. https://pirsa.org/13110090

Kimmel, Shelby. Quantum Adversary (Upper) Bound. Perimeter Institute, Nov. 20, 2013, https://pirsa.org/13110090 

          @misc{ pirsa_PIRSA:13110090,
            doi = {10.48660/13110090},
            url = {https://pirsa.org/13110090},
            author = {Kimmel, Shelby},
            keywords = {Quantum Information},
            language = {en},
            title = {Quantum Adversary (Upper) Bound},
            publisher = {Perimeter Institute},
            year = {2013},
            month = {nov},
            note = {PIRSA:13110090 see, \url{https://pirsa.org}}
          }

Shelby Kimmel

Massachusetts Institute of Technology (MIT)

Talk number
PIRSA:13110090
Collection
Talk Type
Subject
Abstract
I discuss a technique - the quantum adversary upper bound - that uses the structure of quantum algorithms to gain insight into the quantum query complexity of Boolean functions. Using this bound, I show that there must exist an algorithm for a certain Boolean formula that uses a constant number of queries. Since the method is non-constructive, it does not give information about the form of the algorithm. After describing the technique and applying it to a class of functions, I will outline quantum algorithms that match the non-constructive bound.