The Hitchhiker's Guide To Quantum Computing

By Simon BoneDon't Panic


Aim

The aim of this article is to provide a short introduction to the topics that we will cover over the next few weeks. It will gloss over most of the details and provide a general overview that will lead onto our following articles.


Contents

  1. Introduction
  2. So what is a 'Quantum Computer'?
  3. The advantages of Quantum Computing
  4. The disadvantages of Quantum Computing
  5. Related topics
    • Quantum communication
    • Quantum cryptography
    • Artificial Intelligence
  6. Conclusion
  7. References


Introduction

During the 1930's key figures such as Alan Turing developed the classical theories of computing. These theories describe the limitations of machine-executable algorithms and are still in use today. It is interesting to note that most of these theories predate the modern computer which only came into existence as we know it during the 1950's. The modern computer has developed rapidly since then, from valve technology through to VLSI integrated circuits. We have already reached the stage where the design features of modern processors are so small that they are being affected by the strange rules of quantum mechanics.

Whilst these effects represent a limit to the size reduction that has been one of the key methods of increasing processor performance, a school of thought has developed believing that maybe these effects can be used to our advantage in some kind of new computer, a quantum computer.

Richard Feynman led the way by producing an abstract model of how, in principle, a quantum system could be used to perform computations. Then, in 1985, David Deutsch published a ground breaking theoretical paper describing how any physical process could be modeled perfectly (in theory) using a quantum computing system. Such a computer, he argued, would be able to perform tasks like true random number generation that no classical computer can achieve. The most powerful feature of a quantum computer would be its ability to use the phenomenon of 'quantum parallelism' to perform certain types of calculations in a fraction of the time taken by a classical computer


So what is a 'Quantum Computer'?

In the classical model of a computer the most fundamental building block, the bit, can only exist in one of two distinct states, a '0' or a '1'. In a quantum computer the rules are changed. Not only can a 'quantum bit', usually referred to as a 'qubit', exist in the classical '0' and '1' states, but it can also be in a superposition of both! In this coherent state, the bit exists as a '0' and a '1' in a manner which may at first seem hard to accept. Let's consider a register of three classical bits: it would be possible to use this register to represent any one of the numbers from 0 to 7 at any one time. If we then consider a register of three qubits, we can see that if each bit is in the superposition or coherent state, the register can represent all the numbers from 0 to 7 simultaneously!

A processor that can use registers of qubits will in effect be able to perform calculations using all the possible values of the input registers simultaneously. This phenomenon is called quantum parallelism, and is the motivating force behind the research being carried out in quantum computing.


The advantages of Quantum Computing

It has been shown in theory that a quantum computer will be able to perform any task that a classical computer can. However, this does not necessarily mean that a quantum computer will outperform a classical computer for all types of task. If we use our classical algorithms on a quantum computer, it will simply perform the calculation in a similar manner to a classical computer. In order for a quantum computer to show its superiority it needs to use new algorithms which can exploit the phenomenon of quantum parallelism.

Such algorithms are not easy to formulate, but once discovered they yield spectacular results. An example of one such algorithm is the quantum factorisation algorithm created by Peter Shor of AT&T Bell laboratories. The algorithm tackles the problem of factorising large numbers into its prime factors. This task is classically very difficult to solve; in fact it is so difficult that it forms the basis of RSA encryption, probably the most popular method of encryption used today. Shor's algorithm cleverly uses the effects of quantum parallelism to give the results of the prime factorisation problem in a matter of seconds whereas a classical computer would take, in some cases, more than the age of the universe to produce a result!


The disadvantages of Quantum Computing

The technology needed to build a quantum computer is currently beyond our reach. This is due to the fact that the coherent state, fundamental to a quantum computers operation, is destroyed as soon as it is measurably affected by its environment. Attempts at combatting this problem have had little success, but the hunt for a practical solution continues.


Related Topics

The implications of the theories involved in quantum computation reach further than just making faster computers...

Quantum Communication

Many research groups are working on quantum communication systems. They allow a sender and receiver to agree on a code without ever meeting in person. The uncertainty principle, an inescapable property of the quantum world, ensures that if an eavesdropper tries to monitor the signal in transit it will be disturbed in such a way that the sender and receiver are alerted.

Quantum Cryptography

The expected capabilities of quantum computation promise great improvements in the world of cryptography. Ironically the same technology also poses current cryptography techniques a world of problems. The implications of Shor's factoring algorithm on the world of cryptography is staggering. The ability to break the RSA coding system will render almost all current channels of communication insecure.

Artificial Intelligence

The theories of quantum computation suggest that every physical object, even the universe, is in some sense a quantum computer. If this is the case, then according to Turing's work which says that all computers are functionally equivalent, computers should be able to model every physical process. Ultimately this suggests that computers will be capable of simulating conscious rational thought. These theories provoke a minefield of philosophical debate, but maybe the quantum computer will be the key to achieving true artificial intelligence.


Conclusion

Although the future of quantum computing looks promising, we have only just taken our first steps to actually realising a quantum computer. There are many hurdles which need to be overcome before we can begin to appreciate the benefits they may deliver. Researchers around the world are racing to be the first to achieve a practical system, a task which some scientists think is futile. David Deutsch - one of the ground breaking scientists in the world of quantum computing - said himself that perhaps 'their most profound effect may prove to be theoretical'.

In comparison the progress in quantum communications has been somewhat more fruitful. Companies like BT have actually achieved working systems that are able to use quantum effects to detect eavesdropping on a channel. Whether or not such systems will prove practical remains to be seen.

Can we really build a useful quantum computer?

Who knows; in a quantum world, anything is possible!


References :