Michele Mosca, Workshop on: QUANTUM INFORMATION PROCESSING FOR QUANTUM COMMUNICATIONS

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
>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.
Abstract
	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.