Taking as given that a fully functional quantum computer is invented, this article will explain some of the uses found so far for it. For certain problem solving, the quantum computer will never surpass traditional computers. An example of this would be function evaluations such as multiplication. However, there are many other areas of computation that they would be well suited towards such as:

• Problem solving, i.e. factorising.
• Proving that an input is true (though not necessarily providing the proof) e.g. proving that a number is composite.
• Providing true randomisation as opposed to present day computers which only provide pseudo random numbers.
• Undergoing an evolution that mimics a specified physical system e.g. simulating the behaviour of a hurricane.
• Possibly producing intelligent machines that can pass the turing test.

This is an algorithm invented by Peter Shor in 1995. It is the so called 'killer application' of quantum computers, due to its usefulness. It uses a quantum computer to crack public keys, a very popular method of encrypting data. To understand how it works first I will explain the basic workings of public key encryption.

Public Key Encryption

This is the main method for sending encrypted data. It works by using two keys one public and one private. The public key is used to encrypt the data, while the private key is used to decrypt the data. The public key can be easily derived from the private key but not visa versa. This system relies on the extreme difficulty of factorising large numbers. An eavesdropper who knows your public key can in principle calculate your private key as they are mathematically related but the difficulty of computing the private key is the problem of factorising large integers. For example, multiplying 1234 by 3433 is easy to work out, but calculating the factors of 4236322 is not so easy. The difficulty of factorising grows rapidly with the size. It took 8 months and 1600 Internet users to crack RSA 129. Encrypters thought that more digits could be added as conventional computers increased in speed, i.e. it would take longer than the age of the universe to calculate RSA 140. However, using a quantum computer, which is running Shor's algorithm, a key can be cracked in seconds. This is due to the algorithm being able to parallel process on an unprecedented scale .

How Shor's Algorithm Works

There are three main stages to Shor's Algorithm

1) Take a memory register and place it into a quantum superposition of states (i.e. if you had a two bit register, it would be in the states 00, 01, 10, 11 at the same time.)

2) A calculation is made on the register (and hence on each different value in the register). First of all a random number x is chosen (between 0 and n). Raise this number to the power in the register. Divide this number by n, and place the remainder in a second register. The numbers in the second register will start to repeat at a certain frequency(f).

3) Plug into the formula (x.f/ 2) - 1. An example of this would be trying to factorise 15 using x = 3. This would give powers of 3, 9, 27, 81, 243, 729 etc. These have a repeating pattern of 3, 9, 12, 6, 3, 9 etc., giving the frequency as four. Putting it in the formula gives (3 x 4) / 2 - 1 = 5 which is a factor of 15.

Shor worked out that incorrect answers had a tendency to cancel themselves out while correct ones reinforced each other. Thus an answer for the factors could be found. This technique does not get the correct answer all the time, however it is so quick to implement, it can be run over and over again.

Lov Grover has written an algorithm using quantum computers to search an unsorted database faster than a conventional computer could. Normally a database with N entries would take N/2 number of searches to find the data needed, but using a quantum computer it takes root N. For example, with a database holding 1 million entries instead of taking on average 500,000 searches it will only take 1000 searches (in this universe). With databases getting larger and being integrated together more, this would mean a significant saving in time.

Grover's algorithm has another very useful application, in the field of cracking encrypted data. We are interested in the situation where a virtual database is so large that it would not fit in the memories of all the worlds computers. This allows a quantum computer to crack another widely used system to protect data. This is the Data Encryption Standard. DES relies on a 56 bit number which both participants must know before hand. If an eavesdropper intercepts clear and ciphered text then his goal is to find the key so that any future text can be decoded. An exhaustive search by conventional means would make it necessary to search 2 to the power 55 keys before hitting the correct one. This would take more than a year even if one billion keys were tried every second. By comparison Grover's algorithm could find the DES enciphering key after only 185 searches before hitting the correct one. For conventional DES, a method to stop modern computers from cracking the code (i.e. if they got faster) would be simply to add extra digits to the code which would increase the number of searches needed exponentially. This does not happen similarly in a quantum computer crack.

Grover also stated that quantum computers would be talented statisticians, excelling in finding single numbers which depend collectively on lots of data e.g. median age of a population.

Many of the special properties of quantum computers are similar to properties that the mind has, e.g. correlating large amounts of different data very rapidly to useful conclusions, without necessarily producing proof for this (intuition). This would seem to suggest that there is a link between quantum computers and how the brain works, possibly leading to an artificially intelligent computer.

From the above it can be seen that the most useful aspect of quantum computers (found so far) is to crack previously unbreakable codes, but other uses have been envisioned, such as AI and simulation. Once this computer is invented (this is by no means a certainty, indeed many say that it is impossible), many more algorithms may be invented to use its special capabilities. To give an example of just how close this technology is, the Innsbruck group hope to produce a 3 bit quantum computer in a year. If this is successful they hope to have a computer up and running, in 5 years, which will factorise 15. Other groups may be closer still (Hitachi is known to be secretly working on a quantum computer). Limited working quantum computers have been made which implement quantum communications links (see references for further information on this).