An optimal adiabatic quantum query algorithm

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

• Mathieu Brandeho (Université Libre de Bruxelles)
• Thursday 16 October 2014, 14:15-15:15
• MR3, Centre for Mathematical Sciences, Wilberforce Road, Cambridge.

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.

This talk is included in these lists:

• All CMS events
• CMS Events
• CQIF Seminar
• DAMTP info aggregator
• Hanchen DaDaDash
• Interested Talks
• MR3, Centre for Mathematical Sciences, Wilberforce Road, Cambridge
• bld31

Note that ex-directory lists are not shown.