Quantum Information Processing and Quantum Communications

Quantum Lower Bounds

aula dottorato - venerdì 23 aprile ore 11
  MICHELE MOSCA, University of Waterloo & St. Jerome's University

>VITAE: Michele Mosca is the Canada Research Chair in Quantum Computation (since January 2002) at the University of Waterloo, Canada (Combinatorics & Optimization) and St. Jerome's University. He is co-founder and the Deputy Director of Waterloo's Institute for Quantum Computing, and a founding member of the Perimeter Institute for Theoretical Physics. He obtained a doctorate in quantum computer algorithms in 1999 at the University of Oxford, holds a Premier's Research Excellence Award, and
since autumn 2003 has been a member of the Canadian Institute for Advanced Research program on Quantum Information.

Michele Mosca
  Since information is stored and processed in a physical medium, any meaningful theory of information processing must be cast in a realistic physical framework.
The "computational complexity" of a task is a quantification of the amount of resources (usually time and/or space) necessary to perform that task.
In this talk I will discuss the "polynomial method" for finding lower bounds on the computational complexity of various computational problems in a quantum mechanical framework.
I will also describe why the polynomial method was unsuccessful in proving an exponential lower bound for the running time of certain "adiabatic" algorithms for solving NP-hard problems.