PIRSA:15020109

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

APA

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

MLA

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

BibTex

          @misc{ scivideos_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 for Theoretical Physics},
            year = {2015},
            month = {feb},
            note = {PIRSA:15020109 see, \url{https://scivideos.org/index.php/pirsa/15020109}}
          }
          

Cedric Lin Massachusetts Institute of Technology (MIT)

Talk numberPIRSA:15020109
Source RepositoryPIRSA

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.