Introduction to Quantum Effects

In Young's double slit experiment below (Figure 1) light coming from the light source produces interference patterns on the screen S. If we were to consider that light is a wave then the patterns can be explained by the interference of light travelling through slits X and Y.

_{Figure 1}

Since Young first performed his experiment in 1801 we have gained a far better control over our light sources. We also now know that light is made of particles called photons. We can arrange for a single photon to leave the emitter, pass through the slits and hit the screen. What we see is that the photons strike certain areas of the screen more often than other areas, and that that this is the reason for the light and dark fringes.

This raises some interesting questions. For instance, just why does a single photon hit the screen more in some areas than in others? If light is made up of particles then how can a single particle travelling through one of the slits X or Y produce an interference pattern? As only one particle has been emitted from the light source surely there is nothing for the particle to interfere with.

One theory is that the photon is more likely to strike certain areas of the screen because it has effectively travelled to the screen via every possible path, with some paths interfering with others. This interference may be constructive or destructive and accounts for why the photons never hit certain areas of the screen. The effects of quantum interference are even more apparent in the results of a second experiment, shown below.

Consider a beam of light being emitted from a laser and hitting a partially reflective mirror, as shown in Figure 2. The mirror has been designed to reflect or transmit light with equal probability, so 50% of the light will hit detector 1 and 50% will hit detector 2.

_{Figure 2}

Now consider an attempt to recombine the beam, as shown in Figure 3. The paths are set up to be exactly equal in length. What we find is that 100% of the light hits detector 1.

_{Figure 3}

Now consider the same experiment with one of the paths blocked, as in Figure 4. What we now find is that 50% of the light hits detector 1 and 50% hits detector 2. Again we can adjust the light source so that only 1 photon is emitted at a time and again we find that this single photon behaves exactly as it would if it was a wave. In Figure 4 we know which path the electron has travelled as one of the paths is blocked. Yet how does this single photon know that this blockage on a remote path exists and that, with such a blockage, it must act differently when it reaches the second partially mirrored surface?

_{Figure 4}

Again it seems that we must accept the result that at the quantum level particles do not travel single paths, instead they travel to their destination by every possible path. Although this seems counterintuitive this area of quantum physics predicts measurements that agree with our observations to an astounding degree. For a more comprehensive explanation of the basic theory of quantum mechanics read Richard Feynman's excellent book, QED: The strange theory of light and matter.

If a photon travels to a destination via every possible path then can we use this quantum behaviour to our advantage in computing? It is clear that the universe is performing far more work in calculating the destination of a photon than one would expect from a classical point of view. As our machines are based on classical ideas of mathematics can this extra work by the quantum universe be converted in to extra computational power for our machines? The answer would appear to be a yes.

It was Benioff [1980, 1982a, 1982b] who showed that a machine whose computations were performed according to the laws of quantum mechanics physics would be at least as powerful as a classical Turing machine. It was Richard Feynman [1982, 1986] who first postulated that a quantum mechanical system takes an exponential amount of time to simulate on a classical machine. This then implies the reverse - that some computations which take an exponential amount of time to run on a classical machine can be computed in polynomial time by a quantum mechanical system. It was David Deutsch [1985, 1989] who was the first person to seriously investigate this possibility and define a Quantum Turing Machine.

MANY WORLDS FORMULATION

In one formulation of quantum theory, the Many Worlds interpretation, there are actually many copies of the universe which have certain probabilities of existing. In each universe the photon travels to its destination along one path. The interference that we see on the screen is due to the universes constructively and destructively interfering with one another. The universes where the photon strikes a dark patch of the screen have little possibility of existing while the universes with light patches have a reasonable chance of existing.

The Many Worlds theory originated with Dr Hugh Everett, III, is supported by some of the leading investigators in the field of quantum computation. The following in an extract from the "Many Worlds" faq by Michael Clive Price, which is available online.

"Political scientist" L David Raub reports a poll of 72 of the "leading cosmologists and other quantum field theorists" about the "Many-Worlds Interpretation" and gives the following response breakdown.

"Yes, I think MWI is true"	58%
"No, I don't accept MWI"	18%
"Maybe it's true but I'm not yet convinced"	13%
"I have no opinion one way or the other"	11%

Amongst the "Yes, I think MWI is true" crowd listed are Stephen Hawking and Nobel Laureates Murray Gell-Mann and Richard Feynman. Gell-Mann and Hawking recorded reservations with the name "many-worlds", but not with the theory's content. Nobel Laureate Steven Weinberg is also mentioned as a many-worlder, although the suggestion is not when the poll was conducted, presumably before 1988 (when Feynman died). The only "No, I don't accept MWI" named is Penrose.

The Many Worlds theory allows us a view of the behaviour of quantum computation which some find easier to visualise. The theory does differ from other quantum theories in its predicted results in certain areas. This opens up the possibility of being able to disprove the theory one day. Deutsch [1985] describes one possible experiment using an artificial intelligence computer built using quantum circuits. This experiment is currently far beyond our technical expertise.

The theory implies that there are many copies of you in many different universes. We are not aware of other copies because there can be no communication between the universes. This is disconcerting to a number of people who do not like their individuality to be impeached upon.

For the remainder of this text the Many Worlds theory shall be the only one used in explaining the behaviour of quantum circuits.

SUPERPOSITIONED PARTICLES

Imagine a hydrogen atom in its ground state. If we supply an amount of energy at the correct frequency for a certain period of time the atom will become excited. If we supply the energy for only half of this period then the atom will be in a superpositioned state - that is in some universes the atom will still be in a ground state and in other universes it will be in an excited state. Note that the particle is not in some intermediate state - it is definitely in one state or the other and measuring it will tell you which state the particle occupies in your universe. An otherwise identical copy of you in a different universe will have performed exactly the same measurement and will have seen the opposite result.

Again consider a particle in its ground state in universe X. Again we supply the correct amount of energy so that the particle enters a superpositioned state. The universe X will then split in to two universes: in universe U1 the particle is excited and in universe U2 the particle is still in its ground state. In all other aspects these two universes are absolutely identical. We can see this in Figure 5 where time increases along the x-axis.

_{Figure 5}

Each of these universes will have an amplitude attached to it. The amplitude is a complex number that corresponds to the likelihood of that universe existing. What we would term as being the probability of the universe existing is the magnitude squared of this complex number, which obviously must lie on or between 0 and 1.

Now if we consider the above example again, what would happen if there was another route for the universe U1 to be created, as in Figure 6. Here universe Y can also split in to two universes, one of which is identical to U1. It is obvious that the probability of U1 occurring must now be affected as there are two paths leading to this universe. This is not to say that the probability of U1 increases. The amplitude of U1 is determined by the a mathematical combination of the amplitudes of X and Y and of the amplitudes of X leading to U1 and Y leading U1. As amplitudes attached to these universes and actions are complex and may well involve negative numbers the probability of U1 existing may well be less in this example than it was in the previous example. Hence the universe may well destructively interfere as well as constructively so, and this is why we see dark fringes in Young's double slit experiment.

_{Figure 6}

It is important to note that the universes must be absolutely identical for interference to occur. Again consider a particle in a universe X which is then transferred in to a superpositioned state in universes U1 and U2. Now we measure the particle. In universe U1 you would see that the particle is excited and you and the particle would enter universe U3, and in U2 you would see that it is in the ground state and enter universe U4. By this process of measuring the state of billions of particles in your brain have been affected. The difference between U3 and U4 would not be one particle, as with the differences of U1 and U2, but billions of particles. U3 and U4 would be so far apart that there would never be any hope of the two universes becoming identical at some point in the future. Thus they will never interfere again. We call this process decoherence, and it can be seen in Figure 7 with the y-axis representing a qualitative measure of the distance between universes (that is to say how different they are).

_{Figure 7}

QUBITS

We define a quantum bit (Qubit) as being a particle in the superposition of two values, which we will denote |0> and |1>. Here we use the ket notation |> to remind us that we are dealing with quantum systems and not classical ones. For instance, we could denote the excited state of a superpositioned particle as being |1> and the ground state as being |0>.

Let's place a particle in to the superposition of two values, |0> and |1>. Again we get two universes, each with an assigned amplitude. If we were to then to place another particle in a superposition of two values we'd then get four universes, as shown in Figure 8. If we were to repeat this process then we would get eight universes, and so on.

_{Figure 8}

In fact for n superpositioned particles in two possible states we get 2ⁿ different universes with every possible combination of the n particles values being observed. As with classical machines we can call a collection of bits a register. However, the difference is that a classical register can only hold one value. A quantum register of length n bits can hold up to 2ⁿ values simultaneously with each value observed in an otherwise identical universe. This quantum register could be used as the input to some circuit. The circuit will then act simultaneously on these 2ⁿ different inputs, perform 2ⁿ different calculations and output 2ⁿ superpositioned results. This is the source of the exponential speed-up of quantum computers, and has also been dubbed parallel processing on a serial machine. In essence, for the cost of building only one circuit we can have the circuit perform an exponential number of calculations simultaneously.

The trick is to get all of these universes to interfere with each other in such a way as to produce an output that is of some use to us. Consider the situation where we have the functions in the 2ⁿ universes outputting a different value with equal probability. If we were to perform a measurement on the output value the systems would decohere and the value read would be a random value from the 2ⁿ outputs, which wouldn't really tell us very much. What's required is to arrange for the universes to interfere with each other with each other in such a way so that the output value(s) of interest have a much higher probability of being observed and, conversely, those values which are not of interest having a much smaller probability of being observed.

This leads to an interesting question. If we require that the output from a quantum circuit interferes in such a way as to make certain outputs being made more probable than others, then does this lead to a restriction on the type of class of problems which quantum circuits could perform more efficiently than their classical counterparts? Would it lead to a more efficient algorithm but with a less than exponential speed up? This question is analogous to the question of whether parallel processing machines can effectively speed up all problems or whether there are some inherently sequential problems that refuse to yield to parallel techniques. The answer to this question on quantum computation would appear to be yes, there is a limit to what quantum computation can speed up. The section Potential and Problems later gives an overview of some of the early results in the field of quantum complexity analysis.