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.