[quantum-info] PIQuDos seminar Wed Feb 4: Cedric Lin

[Gus Gutoski]

Please join us on Wednesday, February 4 at 4pm in the Time room for a quantum
information seminar by Cedric Lin.

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

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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.uwaterloo.ca/pipermail/quantum-info/attachments/20150131/c4a8ea5f/attachment.html>