Individual project proposal: Quantum Computing

Proposer: Iain Stewart, room 220a Huxley, e-mail ids@doc.ic.ac.uk

Quantum computing is a radical new approach to the whole discipline of computing science. It's about thinking through the implications of quantum mechanics - our current best theory of the physical world - for computers and computing.

In theoretical terms, it's about exploring issues like: given quantum mechanics, what sort of machines will do useful computation? Or: just how much computation can be squeezed out of any particular sort of physical system?

In practical terms, it's about exploiting the quantum aspects of the world to improve the performance of future generations of computers. The most exciting really new feature of quantum computing is quantum parallelism: parallel processing on a serial machine. Different parts of the computation can be farmed out to copies of the machine in different parallel universes, and quantum interference can then merge these sub-computations into a final result.

Today only a handful of primitive quantum computers exist, and they perform "toy calculations" (like 1+1) or are "hard-coded" for one specialized task (like quantum cryptography). We don't have a quantum computer at IC, so this obviously pushes any IC quantum computing project in the theoretical direction! That still leaves an immense number of interesting avenues to explore. For example:

• Design issues: what sort of systems will work well as quantum computers, and how can they be made programmable?
• Quantum programming languages. If a programmable quantum computer is ever built, what will a quantum programming language look like?
• Re-working the classical "standard computer models" (the Turing machine, the cellular automaton, etc.) into quantum form.
• Quantum algorithmic issues. What problems are quantum-computable, and how long (polynomial time, exponential time, etc.) will quantum algorithms take to run?
• Reliability and scalability. Quantum computers will need qualitatively new forms of error detection and correction to deal with problems unique to them (such as decoherence). How reliable and scalable are proposed quantum architectures likely to be?
• Simulation of a quantum computer on a conventional classical machine. This will likely be very slow and inefficient, but it could be useful as a development tool or to try out different kinds of would-be quantum computer designs. Another possibility would be to take an existing simulator and build a library of basic or well-known quantum algorithms for it.
• Applications: even today's primitive quantum computers are being tentatively applied in fields like quantum cryptography, quantum communication and quantum teleportation. What can we look forward to if robust, powerful, programmable quantum computers become a reality? One exciting application could be fast simulation of a general quantum system on a quantum computer. Meanwhile, we can study the theoretical scope and limits of quantum computing applications, present and future.

You can find lots of stuff about quantum computing on the web. I've collected some interesting links (or links to links...) on this page: "http://www.doc.ic.ac.uk/~ids/quantum_computing.html". Here are some books about quantum computing which you may find useful:

• Quantum Computing by Jozef Gruska (McGraw-Hill, 1999). A comprehensive technical book, accompanied by updates on the web.
• Quantum Computation and Quantum Information by Michael A. Nielsen and Isaac L. Chuang (Cambridge University Press, 2000). Another comprehensive technical book on the subject.
• Introduction to Quantum Computation and Information, edited by Hoi-Kwong Lo, Tim Spiller and Sandu Popescu (World Scientific, 1998). Assumes some prior knowledge of quantum mechanics. (As stated in a review anyway - I haven't seen it myself yet!)
• The Fabric of Reality by David Deutsch (Allen Lane, The Penguin Press, 1997). A non-technical book containing a chapter on quantum computing and further chapters arguing for its place as one important strand in our deepest theories of the structure of the world.

A final remark: I certainly wouldn't claim to be an expert on any of this myself, I simply find it very interesting. So if you do this project you'll be in some sense "on your own" (though obviously I'll try to keep up!). In short: this project is "for the brave". If you're still interested, do come and see me about any aspect of the project and all the various forms it could take!

This corner of the web maintained by Iain Stewart <ids@doc.ic.ac.uk>, Department of Computing, Imperial College, London, UK

- add your own comments to this web page or any other for all to see! (Only supported by some browsers, sometimes via an extension or the like.)

(If you're reading this from within IC DoC you can try Crit, an earlier way to annotate the web. )