Abstract

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.