ABSTRACT:
Computational complexity theory is a branch of computer science that aims to characterise how hard it is to perform a given computational task. Although this appears distant from the usual considerations of physics, it has in recent decades been seen to have a remarkable relevance, driving the emergence of a new area of research viz. quantum information science. The conceptual framework of complexity theory provides a new tool for illuminating essential foundational differences between classical and quantum physics, especially in issues of many-body physics. It is also a natural formalism for studying the power of quantum computation relative to classical computation. In this talk we will introduce the basic notions of complexity theory and outline their fundamental significance for quantum physics. Then we will discuss some recent developments on the characterisation of the power of quantum computation, a subject harbouring surprises and which is still little understood.
ADDITIONAL INFORMATION:
Richard Jozsa is the holder of the Leigh Trapnell Chair in Quantum Physics. His research area is quantum information science; a pioneer of this field, he is the co-author of the Deutsch-Jozsa quantum algorithm and one of the co-inventors of quantum teleportation. His work was recognised in 2004 by the London Mathematical Society with the award of the Naylor Prize for “his fundamental contributions to the new field of quantum information science”.
http://www.damtp.cam.ac.uk/people/r.jozsa/