 |
|
 |
| Quantum Computation: A Survey of Recent Theoretical Developments | ||
|---|---|---|
| Tuesday 30 May 2000 | 17:00 | Brian Spratt Room |
| Professor Richard Jozsa Department of Computer Science University of Bristol |
||
Quantum computation involves a synthesis of fundamental quantum physics with concepts from computer science. In theory it offers the possibility of exponentially enhanced computing power compared to any classical device. Peter Shor's discovery in 1994, of a fast (polynomial-time) quantum algorithm for integer factorisation, was a landmark result. Since then we have come to recognise and abstract the essential ingredients of this algorithm for possible wider applicability.
Quantum entanglement has emerged as a fundamental resource in the processes of quantum computation. In addition to its role in enhancing computing power, we may consider it in the context of the theory of communication complexity. This context more generally has led to a variety quantum applications including a provable exponential benefit of quantum over classical computation for certain communication tasks (with no prior assumptions of classical intractability).
Many intriguing questions remain unresolved. What is the origin of the power of quantum computation? What is its relation to classical complexity classes such as NP? In this talk we will introduce the basic necessary quantum principles and survey some of the main lines of development in quantum computation.
