A Brief History of Quantum Computing

By Simon Bone and Matias Castro

Abstract

Strange as it sounds, the computer of tomorrow could be built around a cup of coffee. The caffeine molecule is just one of the possible building blocks of a 'quantum computer', a new type of computer that promises to provide mind boggling performance that can break secret codes in a matter of seconds.


Table of contents

    1. Introduction
        1.1 Quantum computer basics
        1.2 The pitfall of quantum computing - decoherence
        1.3 Getting a result
    2. Theory of universal computation
        2.1 Heating up over lost information
        2.2 The universal quantum computer
        2.3 Artificial intelligence
    3. Building a quantum computer
        3.1 Quantum dots
        3.2 Computing liquids
    4. Applications of quantum computers
        4.1 Shor's algorithm
            - Shor's algorithm - An example 
        4.2 Grover's algorithm
        4.3 Simulation of quantum mechanical systems
    5. Quantum communication
        5.1 How quantum communication works
        5.2 Quantum bit commitment
    6. Current progress & future prospects
    7. Conclusion
    8. Glossary of terms
    9. References
        9.1 Books
        9.1 People
        9.2 Magazine articles
        9.3 Web pages

1. Introduction

Every so often a new technology surfaces that enables the bounds of computer performance to be pushed further forwards. From the introduction of valve technology through to the continuing development of VLSI designs, the pace of technological advancement has remained relentless. Lately, the key to improving computer performance has been the reduction of size in the transistors used in modern processors [18]. This continual reduction however, cannot continue for much longer. If the transistors become much smaller, the strange effects of quantum mechanics will begin to hinder their performance. It would therefore seem that these effects present a fundamental limit to our computer technology, or do they?

In 1982, the Nobel prize-winning physicist Richard Feynman thought up the idea of a 'quantum computer', a computer that uses the effects of quantum mechanics to its advantage [23]. For some time, the notion of a quantum computer was primarily of theoretical interest only, but recent developments have bought the idea to everybody's attention. One such development was the invention of an algorithm to factor large numbers on a quantum computer, by Peter Shor (Bell Laboratories). By using this algorithm, a quantum computer would be able to crack codes much more quickly than any ordinary (or classical) computer could. In fact a quantum computer capable of performing Shor's algorithm would be able to break current cryptography techniques in a matter of seconds. With the motivation provided by this algorithm, the topic of quantum computing has gathered momentum and researchers around the world are racing to be the first to create a practical quantum computer.

1.1 Quantum computer basics

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 [9],[10],[23]. Not only can a 'quantum bit', usually referred to as a 'qubit', exist in the classical 0 and 1 states, it can also be in a coherent superposition of both. When a qubit is in this state it can be thought of as existing in two universes, as a 0 in one universe and as a 1 in the other. An operation on such a qubit effectively acts on both values at the same time. The significant point being that by performing the single operation on the qubit, we have performed the operation on two different values. Likewise, a two-qubit system would perform the operation on 4 values, and a three-qubit system on eight. Increasing the number of qubits therefore exponentially increases the 'quantum parallelism' we can obtain with the system. With the correct type of algorithm it is possible to use this parallelism to solve certain problems in a fraction of the time taken by a classical computer.

1.2 The pitfall of quantum computing - decoherence

The very thing that makes quantum computing so powerful, its reliance on the bizarre subatomic goings-on governed by the rules of quantum mechanics, also makes it very fragile and difficult to control. For example, consider a qubit that is in the coherent state. As soon as it measurable interacts with the environment it will decohere and fall into one of the two classical states. This is the problem of decoherence and is a stumbling block for quantum computers as the potential power of quantum computers depends on the quantum parallelism brought about by the coherent state [14]. This problem is compounded by the fact that even looking at a qubit can cause it to decohere, making the process of obtaining a solution from a quantum computer just as difficult as performing the calculation itself.

1.3 Getting a result

Once a calculation that makes use of quantum parallelism has been performed, there will be any number of different results in different universes. The fact that the results are not in this universe means that we can only obtain a solution to a computation by looking at the interference of the various results. It is important to note that looking at the result (or any intermediate state) of a quantum computer prevents any further interference between the different versions from taking place, i.e. prevents any useful quantum computations from continuing. Such interference is best illustrated with a simple example; In Young's two slit experiment, light is shone through two parallel slits onto a screen. The resulting pattern of light and dark fringes displayed on the screen is a result of constructive and destructive interference. In a similar way, the results from each universe's calculation will constructively and destructively interfere to give a measurable result. This result has a different significance for different algorithms, and can be used to deduce the solution to the problem in hand (For an example see Shor's algorithm - An example).

Figure 1 - Young's two slit experiment demonstrates interference of photons.


2. Theory of universal computation

One thing that all computers have in common, from Charles Babbage's analytical engine (1936) to Pentium(tm) based PC's, is the theory of classical computation as described by the work of Alan Turing [3]. In essence, Turing's work describes the idea of the universal turing machine, a very simple model of a computer that can be programmed to perform any operation that "would naturally be considered to be computable". All computers are essentially implementations of a universal turing machine. They are all functionally equivalent and although some may be quicker, larger or more expensive than others, they can all perform the same set of computational tasks.

2.1 Heating up over lost information

A great deal of time has been spent on investigating whether quantum theory places any fundamental limits on computing machines. As a result, it is now believed that physics does not place any absolute limits on the speed, reliability or memory capacity of computing machines. One consideration that needs to be made however, concerns the information that may be 'lost' in a computation [23]. In order for a computer to run arbitrarily fast, its operation must be reversible (i.e. it's inputs must be entirely deducible from its outputs). This is because irreversible computations involve a 'loss' of information which can be equated to a loss in heat, and thus the restricted ability of the system to dissipate heat will in turn limit the performance of the computer. An example of information being lost can be seen in an ordinary AND gate. An AND gate has two inputs and only one output, which means that in the process of moving from the input to the output of the gate, we loose one bit of information.

In 1976, Charles Bennett proved that it is possible to build a universal computer entirely from reversible gates, and that expressing a program in terms of primitive reversible operations does not significantly slow it down. A suitable universal and reversible gate with which we could build a computer is the Toffoli gate (see Figure x).


Figure 2 - The inputs of a Toffoli gate are entirely deducible from the outputs.

2.2 The universal quantum computer

The Church-Turing principle - "There exists or can be built a universal computer that can be programmed to perform any computational task that can be performed by any physical object".

A number of key advances have been made in the theory of quantum computation, the first being the discovery that a simple class of 'universal simulator' can mimic the behaviour of any finite physical object, by Richard Feynman in 1982. David Albert made the second discovery in 1984 when he described a 'self measuring quantum automaton' that could perform tasks that no classical computer can simulate. By instructing the automaton to measure itself, it can obtain 'subjective' information that is absolutely inaccessible by measurement from the outside. The final and perhaps most important discovery was made by David Deutsch in 1989, he proved that all the computational capabilities of any finite machine obeying the laws of quantum computation are contained in a single machine, a 'universal quantum computer'. Such a computer could be built from the quantum equivalent of the Toffoli gate and by adding a few extra operations that can bring about linear superpositions of 0 and 1 states, the universal quantum computer is complete. This discovery requires a slight alteration to the Church-Turing principle - "There exists or can be built a universal quantum computer that can be programmed to perform any computational task that can be performed by any physical object".

2.3 Artificial intelligence

The theories of quantum computation have some interesting implications in the world of artificial intelligence. The debate about whether a computer will ever be able to be truly artificially intelligent has been going on for years and has been largely based on philosophical arguments. Those against the notion suggest that the human mind does things that aren't, even in principle, possible to perform on a Turing machine.

The theory of quantum computation allows us to look at the question of consciousness from a slightly different perspective. The first thing to note is that every physical object, from a rock to the universe as a whole, can be regarded as a quantum computer and that any detectable physical process can be considered a computation. Under these criteria, the brain can be regarded as a computer and consciousness as a computation. The next stage of the argument is based in the Church-Turing principle and states that since every computer is functionally equivalent and that any given computer can simulate any other, therefore, it must be possible to simulate conscious rational thought using a quantum computer.

Some believe that quantum computing could well be the key to cracking the problem of artificial intelligence but others disagree. Roger Penrose of Oxford University believes that consciousness may require an even more exotic (and as yet unknown) physics.


3. Building a quantum computer

A quantum computer is nothing like a classical computer in design; you can't for instance build one from transistors and diodes. In order to build one, a new type of technology is needed, a technology that enables 'qubits' to exist as coherent superpositions of 0 and 1 states. The best method of achieving this goal is still unknown, but many methods are being experimented with and are proving to have varying degrees of success.

3.1 Quantum dots

An example of an implementation of the qubit is the 'quantum dot' which is basically a single electron trapped inside a cage of atoms [7]. When the dot is exposed to a pulse of laser light of precisely the right wavelength and duration, the electron is raised to an excited state: a second burst of laser light causes the electron to fall back to its ground state. The ground and excited states of the electron can be thought of as the 0 and 1 states of the qubit and the application of the laser light can be regarded as a controlled NOT function as it knocks the qubit from 0 to 1 or from ' to 0.

If the pulse of laser light is only half the duration of that required for the NOT function, the electron is placed in a superposition of both ground and excited states simultaneously, this being the equivalent of the coherent state of the qubit. More complex logic functions can be modelled using quantum dots arranged in pairs. It would therefore seem that quantum dots are a suitable candidate for building a quantum computer. Unfortunately there are a number of practical problems that are preventing this from happening:

3.2 Computing liquids

Quantum dots are not the only implementation of qubits that have been experimented with. Other techniques have attempted to use individual atoms or the polarisation of laser light as the information medium. The common problem with these techniques is decoherence. Attempts at shielding the experiments from their surroundings, by for instance cooling them to within a thousandth of a degree of absolute zero, have proven to have had limited success at reducing the effects of this problem.

The latest development in quantum computing takes a radical new approach [16]. It drops the assumption that the quantum medium has to be tiny and isolated from its surroundings and instead uses a sea of molecules to store the information. When held in a magnetic field, each nucleus within a molecule spins in a certain direction, which can be used to describe its state; spinning upwards can signify a 1 and spinning down, a 0. Nuclear Magnetic Resonance (NMR) techniques can be used to detect these spin states and bursts of specific radio waves can flip the nuclei from spinning up (1) to spinning down (0) and vice-versa.

The quantum computer in this technique is the molecule itself and its qubits are the nuclei within the molecule. This technique does not however use a single molecule to perform the computations; it instead uses a whole 'mug' of liquid molecules. The advantage of this is that even though the molecules of the liquid bump into one another, the spin states of the nuclei within each molecule remain unchanged. Decoherence is still a problem, but the time before the decoherence sets in is much longer than in any other technique so far. Researchers believe a few thousand primitive logic operations should be possible within time it takes the qubits to decohere.

Dr. Gershenfield from the Massachusetts Institute of Technology, is one of the pioneers of the computing liquid technique. His research team has already been able to add one and one together, a simple task which is way beyond any of the other techniques being investigated. The key to being able to perform more complex tasks is to have more qubits but this requires more complex molecules with a greater number of nuclei, the caffeine molecule being a possible candidate. Whatever the molecule, the advancement to 10 qubit systems is apparently straightforward. Such a system, Dr. Gershenfield hopes, will be possible by the end of this year, and should be capable of factoring the number 15.

Advancing beyond a 10-qubit system may prove to be more difficult. In a given sample of 'computing liquid' there will be a roughly even number of up and down spin states but a small excess of spin in one direction will exist. It is the signal from this small amount of extra spin, behaving as if it were a single molecule that can be detected and manipulated to perform calculations while the rest of the spins will effectively cancel each other out. This signal is extremely weak and grows weaker by a factor of roughly 2 for every qubit that is added. This imposes a limit on the number of qubits a system may have as the readable output will be harder to detect.


4. Applications of quantum computers

It is important to note that a quantum computer will not necessarily outperform a classical computer at all computational tasks. Multiplication for example, will not be performed any quicker on a quantum computer than it could be done on a similar classical computer. In order for a quantum computer to show its superiority it needs to use algorithms that exploit its power of quantum parallelism. Such algorithms are difficult to formulate, to date the most significant theorised being Shor's algorithm and Grover's algorithm. By using good these algorithms a quantum computer will be able to outperform classical computers by a significant margin. For example, Shor's algorithm allows extremely quick factoring of large numbers, a classical computer can be estimated at taking 10 million billion billion years to factor a 1000 digit number, where as a quantum computer would take around 20 minutes.

4.1 Shor's algorithm

This is an algorithm invented by Peter Shor in 1995 that can be used to quickly factorise large numbers. [7],[22]If it is ever implemented it will have a profound effect on cryptography, as it would compromise the security provided by public key encryption (such as RSA).

At Risk - Public Key Encryption

This is currently the most commonly used method for sending encrypted data [3]. 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. However, an eavesdropper who has acquired your public key can in principle calculate your private key as they are mathematically related. In order to do so it is necessary to factorise the public key, a task that is considered to be intractable.

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 a number grows rapidly with additional digits. It took 8 months and 1600 Internet users to crack RSA 129 (a number with 129 digits). Cryptographers thought that more digits could be added to the key to combat increasing performance in computers (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, the number of digits in the key has little effect on the difficulty of the problem. Cracking RSA 140 would take a matter of seconds.

Shor's algorithm - An example

The purpose of this section is to illustrate the basic steps involved in Shor's Algorithm. In order to keep the example relatively easy to follow we will consider the problem of finding the prime factors of the number 15. Since the Algorithm consists of three key steps, this explanation will be presented in 3 stages...

Stage 1

The first stage of the algorithm is to place a memory register into a coherent superposition of all its possible states. The letter 'Q' will be used denote a qubit that is in the coherent state.



Figure 3 - A three-qubit register can represent 8 classical states simultaneously.

When a qubit is in the coherent state, it can be thought of as existing in two different universes. In one universe it exists as a '1' and in the other it exists as a '0' (See Figure 1). Extending this idea to the 3 bit register we can imagine that the register exists in 8 different universes, one for each of the classical states it could represent (i.e. 000, 001, 010, 011, 100, 101, 110, 111). In order to hold the number 15, a four bit register is required (capable of representing the numbers 0 to 15 simultaneously in the coherent state).

A calculation performed on the register can be thought of as a whole group of calculations performed in parallel, one in each universe. In effect, a calculation performed on the register is a calculation performed on every possible value that register can represent.

Stage 2

The second stage of the algorithm performs a calculation using the register. The details of which are as follows:



Figure 4 - Operation performed in stage 2.

After this operation has been performed, register B contains the superposition of each universes results. This is best illustrated with an example, if we choose X to be 2, then the contents of register B, for every possible value in register A are as follows.

Register A

Register B

0

1

1

2

2

4

3

8

4

1

5

2

6

4

7

8

8

1

9

2

10

4

11

8

12

1

13

2

14

4

15

8

Table 1 - Contents of Register B, when N = 15 and X = 2.

Notice that the contents of register B follows a repeating sequence (1,2,4,8,1,2,4,8...), the frequency at which this repeats can be named f. In this case the repeating sequence (1, 2, 4, 8) has four values so f = 4.

Stage 3

The final stage is perhaps the most difficult to follow. The frequency of repetition, f, can be found using a quantum computer. This is done by performing a complex operation on register B and then looking at its contents which causes the results from every universe to interfere with each other. The resulting value for f is then used in the following equation to calculate a (possible) factor.



Figure 5 - Equation used to calculate factor.

The resulting number cannot be guaranteed to be a prime factor, but there is a good chance that it is one. The interference that produces the value for f tends to favour the correct answer as incorrect answers cancel each other out.

In our example the value f = 4 does give a correct answer of 3.

The fact that the answer cannot be guaranteed to be correct is of little consequence as it can be easily checked with multiplication. If the answer is incorrect, there is a very strong chance that repeating the calculation a few times with different values of X will produce the right answer.


4.2 Grover's algorithm

Lov Grover has written an algorithm that uses quantum computers to search an unsorted database faster than a conventional computer [20],[21]. Normally it would take N/2 number of searches to find a specific entry in a database with N entries. Grover's algorithm makes it possible to perform the same search in root N searches. With the increasing size and integration of databases, this saving in time becomes significant. The speed up that this algorithm provides is a result of quantum parallelism. The database is effectively distributed over a multitude of universes, allowing a single search to locate the required entry. A further number of operations (proportional to root N) are required in order to produce a readable result.

Grover's algorithm has a useful application in the field of cryptography. It is theoretically possibly to use this algorithm to crack the Data Encryption Standard (DES), a standard which is used to protect, amongst other things, financial transactions between banks. The standard relies on a 56-bit number that both participants must know in advance, the number is used as a key to encrypt/decrypt data.

If an encrypted document and its source can be obtained, it is possible to attempt to find the 56-bit key. 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 key after only 185 searches. 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 key, which would increase the number of searches needed exponentially. However, the effect that this would have on the speed of the quantum algorithm is negligible.

4.3 Simulation of quantum mechanical systems

In 1982, Feynman conjectured that quantum computers would be able to simulate quantum mechanical systems with a much greater degree of accuracy than is possible with classical computers [17]. It is speculated that a quantum computer with a few tens of quantum bits could perform simulations that would take an unfeasible amount of time on a classical computer. This is due to the use of computer time and memory growing as an exponential function of the size of the quantum system in question.

On classical computers, the dynamics of a quantum system can be simulated using approximations. A quantum computer however, can be "programmed" to simulate the behaviour of a system by inducing interactions between its variables. These imitate the characteristics of the system in question. A quantum computer would, for example, allow the "Hubbard Model" (which describes the movement of electrons within a crystal) to be simulated, a task that is beyond the scope of current conventional computers.


5. Quantum communication

The research carried out on quantum computing has created the spin-off field of quantum communication. This area of research aims to provide secure communication mechanisms by using the properties of quantum mechanical effects

5.1 How quantum communication works

Quantum communications makes use of the fact that information can be encoded as the polarisation of photons (i.e. the orientation of a photon's oscillation) [25],[43]. An oscillation in one direction can be thought of as 0 and in another as a 1. Two sets of polarisations are commonly used, rectilinear and diagonal (see figure 6).



Figure 6 - The polarisation of photons can be used to encode data. In order to receive the data, the polarisation of the filter must match that of the photons.

The property that quantum communication exploits is that in order to receive the correct information, photons have to be measured using the correct filter polarisation e.g. the same polarisation that the information was transmitted with. If a receiver is in rectilinear polarisation, and a diagonally polarised photon is sent, then a completely random result will appear at the receiver. Using this, property information can be sent in such a way as to make it impossible for an eavesdropper to listen undetected. The mechanism by which this works is as follows:

  1. The sender transmits information to the receiver using random polarisations.
  2. The receiver detects this information (also at random polarisations) and records it.
  3. The sender then informs the receiver of the polarisations that he used over a public channel.
  4. The receiver and sender compare a random selection of the information that was received at the correct polarisation.
  5. If an eavesdropper has intercepted and forwarded the information, the receiver and sender will be alerted as a higher percentage of errors will be present than expected.
  6. If an eavesdropper has been detected, then the whole process has to be repeated.

For example, say there is a sender named Alice who wishes to transmit information to Bob without an eavesdropper Eve listening. They would follow the steps as described above. If Eve tries to eavesdrop, she will have to measure the bits coming from Alice and then forward them to Bob (she can't simply look at the information as doing so will alter it's content). She must use random polarisations to do this, as she does not know which ones Alice used. The chances are that Eve will correctly receive 50% of the information, the other 50% will consist of random values. The fact that approximately half of the random values will be correct means that Eve can at best forward 75% of the correct information to Bob.

Assuming that there is negligible noise on the communication line, Bob will be able to detect that Eve has eavesdropped, as the information he received at the correct polarisation will contain more than 25% errors. He checks for errors by comparing a random selection with Alice on a public channel.

Another way that Eve could attempt to subvert communication between Bob and Alice is to intercept the information and send her own instead. Eve will be thwarted by the fact that Alice and Bob discuss a randomly selected group of values, giving away the fact that Eve changed the information. It does not matter how subtly Eve intercepts the signal, Alice and Bob will always be able to discover that she has been listening to the line. This system can only work if the noise on the communication line is negligible, if the line had 25% noise for example it would be impossible to distinguish an eavesdropper from the noise itself. British Telecom has managed to implement a line with only 9% error over a distance of 10km, giving quantum communications a promising future.

5.2 Quantum bit commitment

A different method of quantum communication is quantum bit commitment. Using this method, people can compare or combine information while keeping each individual contribution secret. A possible use for this would be in contract bidding (making firms bid their best possible offer instead of simply higher than the highest opposition).

The basic operation of this method is as follows:

  1. Alice sends a string of photons to Bob, all of which are at the same polarisation.
  2. Bob receives the photons, randomly changing his polarisation and recording the results.
  3. Alice can prove to Bob that she sent the information by telling him the pattern of 1's and 0's he saw when his polarisation was the same as hers.

The weakness in this system is that Alice can cheat by creating pairs of photons and sending only one to Bob [13]. These matched photons have the strange quantum property, which no matter how far apart, an observation of one will effect how the other appears at the receiver. Alice can now change Bob's photons by manipulating the copy she kept. Researchers knew of this problem for some time, and Mayor has recently proven that this is a general weakness of all quantum bit commitment systems.


6. Current progress & future prospects

The recent work on the 'computing liquid' technique pioneered by Dr. Gershenfield and Dr. Chuang (Los Alamos National Laboratory, New Mexico) has given quantum computing a promising future. In fact, Dr. Gershenfield believes that a quantum co-processor could be a reality within 10 years if the current pace of advancement continues. Other techniques, such as quantum dots, may also yield similar results as our technology advances. The optimist will point out that the problems being experienced by researchers appear to be technical rather than fundamental.

On the other side of the argument, is the topic of decoherence. This problem has not been resolved and many people, including Rolf Landauer of IBM's Thomas Watson Research Centre, believe that the quantum computer is unlikely to progress beyond the 10-qubit system (described above), as decoherence makes them too fragile to be practical.

Researchers in quantum communication have enjoyed a greater level of success. The partial quantum computers involved have enabled secure communication over distances as far as 10km. Depending on how costly these lines are to develop and the demand that exists for them, there could be a strong future for quantum communications.


7. Conclusion

With classical computers gradually approaching their limit, the quantum computer promises to deliver a new level of computational power. With them comes a whole new theory of computation that incorporates the strange effects of quantum mechanics and considers every physical object to be some kind of quantum computer. A quantum computer thus has the theoretical capability of simulating any finite physical system and may even hold the key to creating an artificially intelligent computer.

The quantum computers power to perform calculations across a multitude of parallel universes gives it the ability to quickly perform tasks that classical computers will never be able to practically achieve. This power can only be unleashed with the correct type of algorithm, a type of algorithm that is extremely difficult to formulate. Some algorithms have already been invented; they are proving to have huge implications on the world of cryptography. This is because they enable the most commonly used cryptography techniques to be broken in a matter of seconds. Ironically, a spin off of quantum computing, quantum communication allows information to be sent without eavesdroppers listening undetected.

For now at least, the world of cryptography is safe because the quantum computer is proving to be vary difficult to implement. The very thing that makes them powerful, their reliance on quantum mechanics, also makes them extremely fragile. The most successful experiments only being able to add one and one together. Nobody can tell if the problems being experienced by researchers can be overcome, some like Dr. Gershenfield are hopeful that they can whilst others believe that the quantum computer will always be to fragile to be practical.


8. Glossary of terms

Coherent
Term used to describe the stable superposition of states
Computing liquid
A possible quantum computer whose molecules can be used as qubits
Decoherence
When a quantum bit stabilises into only one of its states
DES
Data Encryption Standard
Diagonal
Polarisation at 45 and 135
Grover's Algorithm
An algorithm to search databases, that can also be used to crack DES
NMR
Nuclear Magnetic Resonance
Polarisation
The orientation of a photon's vibrations
Public Key Encryption
A method of encryption which uses the difficulty to factorise large numbers as its safeguard against cracking
Quantum bit commitment
A flawed method of verifying the source of a message
Qubit
A quantum bit, capable of being in both 0 and 1 states simultaneously
Quantum parallelism
By performing operations on qubits, many values can be processed with one calculation
Quantum communication
Using quantum effects to send information without eavesdroppers listening undetected
Quantum computer
A computer that is capable of utilising the effects of quantum parallelism
Quantum dot
A possible implementation of a qubit
Rectilinear
The vertical and horizontal polarisations
Shor's Algorithm
Algorithm to factorise large numbers
Toffoli Gate
A universal reversible gate.
VLSI
Very Large Scale Integration.


9. References

9.1 Books

1.
The Fabric of Reality. David Deutsch
One of the few books currently covering the subject of quantum computing/cryptography. Chapters two and nine are useful to this subject the others not so useful.
Readability:
Usefullness:
2.
Physics - A Textbook for Advanced Level Students. Tom Duncan
A brief introduction to elementry quantum physics
Readability:
Usefullness:
3.
Algorithmics - The Spirit of Computing. David Harel
Includes the history of computing theory and details of encryption techniques
Readability:
Usefullness:

9.1 People

4.
Iain Stewart
Many thanks to Iain for all his time and advice
5.
Naranker Dulay
Many thanks to Naranker for his guidance and time

9.2 Magazine articles

6.
The coffee cup super computer. Tom Standage, Telegraph Connected 3/6/97
A very concise introduction to the subject of quantum computing
Readability:
Usefullness:
7.
A quantum revolution for computing. Julian Brown, New Scientist 24/9/94
Includes a fairly detailed history of quantum computation and a relatively simple explanation of Shor's algorithm
Readability:
Usefullness:
8.
The best computer in all possible worlds. Tim Folger, Discover 1/10/95
A very long and comprehensive acount on the progress of quantum computing as of november 1995
Readability:
Usefullness:
9.
Two-bit heroes - Computing with quanta. The Economist Volume 338 Issue 7948
A shallow introduction to quantum computation
Readability:
Usefullness:
10.
Cue the qubits: Quantum computing - How to make a quantum computer. The Economist Volume 342 Issue 8005
A very good introduction to quantum computing
Readability:
Usefullness:
11.
Wake up to Quantum Coffee. Howard Baker, New Scientist 15/3/97
A comprehensive discussion on the relatively successful computing liquid technique of quantum computing
Readability:
Usefullness:
12.
Demonstrate logic gates for quantum computing. Bertram Schwarzchild, Physics Today 1/3/96
A report on quantum logic gates, directed towards a physicist
Readability:
Usefullness:
13.
Quantum cheats will always win. Robert Pool, New Scientist 17/5/97
A short article detailing a fundamental floor in quantum bit commitment communication schemes
Readability:
Usefullness:
14.
Future of quantum computing proves to be debatable. Christopher Monroe, Physics Today 1/11/96
Takes a realistic look at the feasability of quantum computing
Readability:
Usefullness:
15.
Quantum computation. David P. DiVincenzo, Science 13/10/95
A very comprehensive report on quantum computing, unfortunately heavily drowned in physics notation
Readability:
Usefullness:
16.
Brewing a quantum computer in a coffee cup. D. Vergano, Science News 18/1/97
Very short introduction on the computing liquid technique of quantum computation
Readability:
Usefullness:
18.
Universal Quantum Simulators. Seth Lloyd, Science 23/8/96
An in depth look at the use of quantum computers in simulation
Readability:
Usefullness:
18.
When silicon hits its limits. Tom Thompson, Byte 1/4/96
This article includes a section that introduces the notion of the quantum computer and its possible advantages
Readability:
Usefullness:
19.
Quantum computation. Artur Ekert, American Institute of Physics 1993
A comprehensive but very technical paper
Readability:
Usefullness:
20.
Searching a quantum phone book. Gilles Brassard, Science Volume 275 31/1/97
Good explanation of Grover's algorithm, although a little shallow
Readability:
Usefullness:
21.
Quantum-quick Queries. Ivars Peterson, Science News Volume 150 31/8/96
A good, quick introduction to Grover's algortihm
Readability:
Usefullness:
22.
Quantum code breaking. The Economist, Volume 331 30/4/94
Code breaking explained in laymans terms
Readability:
Usefullness:
23.
Quantum computation. David Deutsch, Physics World, 1/6/92
A comprehensive and inspiring guide to quantum computing
Readability:
Usefullness:
24.
Experimental quantum cryptography. C.H.Bennet, F.Bessette, G.Brassard, L.Salvail, J.Smolin 1/11/91
Indepth analysis of quantum cryptography with examples
Readability:
Usefullness:
25.
Quantum keys for keeping secrets. Artur Ekert, New Scientist Volume 137 16/1/93
Very usefull analysis of quantum communications
Readability:
Usefullness:

Other articles:

 26. Quantum Computation, Physics World, 1992, David Deutsch
 27. A quantum leap in secret communications. William Bown, New Scientist 30/1/93
 28. Tight Bounds on Quantum Searching, M. Boyer, G. Brassard, P. Hoyer, A. Tapp
 29. Quantum Cryptoanalysis introduction, Artur Ekert
 30. Weirdest Computer of All, The Economist, 28 Sept. 1996
 31. Is the universe a computer?. Julian Brown, New Scientist 14/6/1990
 32. It takes two to tangle - in the quantum world. Ben Stein, New Scientist, 28/9/96
 33. Quantum communication thwarts eavesdroppers. David Deutsch, New Scientist, 9/12/89
 34. Quantum leap in code cracking computers. Mark Ward, New Scientist, 23/12/95
 35. Quantum Code-breaking, The Economist, 30 Apr. 1994
 36. Physical Revue Letters. (Vol. 78 p3414).

9.3 Web pages

37.
The Kitchen Sink: Quantum computing.
Links to the field of quantum computering.
http://sps1.phys.vt.edu/~alandahl/quantum_computing.html
Readability:
Usefullness:
38.
Caltech Quantum Optics
A group which is attempting to combat the problem of decoherence
http://www.cco.caltech.edu/~qoptics/
Readability:
Usefullness:
39.
Quantum Cryptoanalysis - Introduction
Good introduction to factorising using Shor's algorithm
http://eve.physics.ox.ac.uk/QCresearch/cryptoanalysis/qc.html
Readability:
Usefullness:
40.
Particle Beam Physics Laboratory
Links to quantum computing information
http://vesta.physics.ucla.edu/~smolin/index.html
Readability:
Usefullness:
41.
Bulk Spin Resonance Quantum Computation
Articles on coffee cup quantum computers
http://feynman.stanford.edu/qcomp/NMRQC/home.html
Readability:
Usefullness:
42.
Iain Stewarts Home Page
More links to quantum computing sites
http://www.doc.ic.ac.uk/~ids/quantum_computing.html
Readability:
Usefullness:
43.
Quantum Encoding
Quantum communication being attempted by the Innsbruck group
http://www.sigmaxi.org/Amsci/issues/Sciobs96/Sciobs96-11Encoding.html
Readability:
Usefullness:
44.
Technical papers on quantum computation
Various papers on quantum computers, most needing an indepth knowledge to understand.
http://feynman.stanford.edu/qcomp/artlist.html
Readability:
Usefullness: