University of Cambridge > Talks.cam > CQIF Seminar > An optimal adiabatic quantum query algorithm

An optimal adiabatic quantum query algorithm

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact William Matthews.

Quantum query complexity is known to be characterized by the so-called quantum adversary bound. While this result has been proved in the standard discrete time model of quantum computation, it also holds for continuous-time (or Hamiltonian based) quantum computation, due to a known equivalence between these two query complexity models. In this work, we revisit this result by providing a direct proof in the continuous-time model. One originality of our proof is that it draws new connections between the adversary bound, a modern theoretical computer science technique, and early theorems of quantum mechanics. Indeed, the proof of the lower bound is based on Ehrenfest’s theorem, while the upper bound relies on the Adiabatic theorem, as it goes by constructing an optimal adiabatic quantum query algorithm.

This talk is part of the CQIF Seminar series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2017 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity