Workshop on QUANTUM INFORMATION PROCESSING AND QUANTUM COMMUNICATIONS
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|
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 information is stored and processed in a physical medium,
any meaningful theory of information processing must be cast in a realistic
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.