Richard Jozsa
(Department of Applied Mathematics and Theoretical Physics, and King's College, Cambridge)
Quantum Complexity and the Foundations of Computing

Turing's original notion of computation was motivated from operational considerations, abstracting the intuitive notion of "a person calculating on sheets of paper". But we can entertain such considerations at a more fundamental level, recognising that any computer is a physical device and information is always represented in physical degrees of freedom. It then follows (as emphasised by D. Deutsch in 1985) that the possibilities of information processing must depend on the /laws of physics/ and cannot be determined from mathematics or abstract thought alone.

The notion of computation embodied in a Turing machine may be argued to correspond to the computational possibilities of classical physics. On the other hand, quantum physics, superseding classical theory, is well known to give rise to a notoriously strange picture of the world and correspondingly it offers extraordinary novel possibilities for information processing. In this talk we will give an introduction to the associated notion of a quantum computation. We will discuss some recent results on the relationship between classical and quantum computational complexity and speculate on a possible significance of computational complexity for fundamental physics.

It is known that Turing maintained a lifelong interest in quantum physics, but curiously he appears never to have made a connection with his fundamental work on computation. He would surely have been delighted by the development of quantum computation.