Quantum Complexity and Computation

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

• Richard Jozsa, Leigh Trapnell Professor of Quantum Physics
• Wednesday 05 October 2011, 17:30-18:30
• Meeting Room 2 at the Centre for Mathematical Sciences.

If you have a question about this talk, please contact sm822.

Professor Richard Jozsa, DAMTP

Inaugural lecture as Leigh Trapnell Professor of Quantum Physics

The lecture will be introduced by Professor Sir Leszek Borysiewicz, Vice-Chancellor of the University of Cambridge.

Abstract: Theoretical physics and computer science are often regarded as disparate disciplines but surprisingly they share a deep fundamental connection – if we recognise that any computer is a physical device and information is always represented in physical degrees of freedom, then it follows that the possibilities and limitations of information processing and communication must depend on the laws of physics and not upon mathematics alone. Indeed our familiar computational paradigm is an expression of the computational possibilities of classical physics. Quantum physics is well known to give rise to a notoriously strange picture of the world and correspondingly it offers extraordinary novel possibilities for computation and communication. Two notable examples are the process of quantum teleportation, a new communication primitive, and computationally, a quantum method for factorising integers, that is exponentially more powerful than any known conventional (classical) algorithm for this important task.

In this talk we will give an intuitive discussion of the ingredients of quantum mechanics, emphasising their surprising significance for computational issues. We will introduce the basic notion of computational complexity of a given task and discuss in general terms, some novel possibilities and limitations of a quantum computer. Finally we will give an overview of some recent results on the intriguing relationship between the computing power of quantum physics and classical physics. Although still not well understood, this relationship appears to be remarkably rich, indicating a great fertility for ideas from computational complexity as a new tool for illuminating some of the most fundamental questions in physics.

This talk is part of the sm822's list series.

This talk is included in these lists:

• All CMS events
• All Talks (aka the CURE list)
• CMS Events
• DAMTP info aggregator
• Faculty of Mathematics Lectures
• Guy Emerson's list
• Interested Talks
• Meeting Room 2 at the Centre for Mathematical Sciences
• School of Physical Sciences
• bld31

Note that ex-directory lists are not shown.