PIRSA:15020109

Upper Bounds on Query Complexity Inspired by the Elitzur-Vaidman Bomb Tester

Lin, C. (2015). Upper Bounds on Query Complexity Inspired by the Elitzur-Vaidman Bomb Tester. Perimeter Institute. https://pirsa.org/15020109

Lin, Cedric. Upper Bounds on Query Complexity Inspired by the Elitzur-Vaidman Bomb Tester. Perimeter Institute, Feb. 04, 2015, https://pirsa.org/15020109 

          @misc{ pirsa_PIRSA:15020109,
            doi = {10.48660/15020109},
            url = {https://pirsa.org/15020109},
            author = {Lin, Cedric},
            keywords = {Quantum Foundations, Quantum Information},
            language = {en},
            title = {Upper Bounds on Query Complexity Inspired by the Elitzur-Vaidman Bomb Tester},
            publisher = {Perimeter Institute},
            year = {2015},
            month = {feb},
            note = {PIRSA:15020109 see, \url{https://pirsa.org}}
          }

Cedric Lin

Massachusetts Institute of Technology (MIT)

Talk number
PIRSA:15020109
Collection
Talk Type
Subject
Abstract

The Elitzur-Vaidman bomb tester allows the detection of a photon-triggered bomb with a photon, without setting the bomb off. This seemingly impossible task can be tackled using the quantum Zeno effect. Inspired by the EV bomb tester, we define the notion of "bomb query complexity". This model modifies the standard quantum query model by measuring each query immediately after its application, and ends the algorithm if a 1 is measured.

We show that the bomb query complexity is asymptotically the square of the quantum query complexity. Moreover, we will show how this characterization inspires a general theorem relating classical and quantum query complexity, and derive new algorithms from this theorem.