Cats, Qubits, and Teleportation: The Spooky World of Quantum Computation (Part One)

By the time most of us reach adulthood, we know a few basic truths. Cats cannot be simultaneously alive and dead. Objects at opposite ends of the universe can’t affect each other. Computers operate on 0s and 1s, and that’s the most fundamental unit of information. The premise of quantum computation is that these truths are partially wrong. Don’t worry, the cat part is mostly right, at least for actual cats, and nothing can travel faster than light.

Twenty years ago, quantum computers were purely theoretical, and existed only on whiteboards and in academic papers. It was unclear whether one would ever be implemented. Ten years ago, the implementation of quantum computers was underway, but a genuinely useful quantum computer was still a distant prospect. Now, quantum computers are available for hire on the cloud. Businesses, academic institutions, and government labs are racing to be the first to announce a quantum computer which can solve problems too difficult for conventional computation.

But what is it which makes a quantum computer so powerful? What kind of problems is a quantum computer useful for? How do modern quantum computers actually work? Will all our computers be quantum computers in the future?

Introduction to quantum mechanics

Quantum mechanics was developed at the beginning of the twentieth century, as physicists began studying smaller and smaller particles. In order to explain what they were observing experimentally, they had to devise new models. In the nineteenth century, observation of refraction and interference had led to a general consensus in the scientific community that light was a wave (a bit like a wave in a swimming pool, or a sound wave in air). Increasingly sophisticated experiments had also revealed that atoms had a planet-like internal structure, with a dense core of protons and neutrons, surrounded by orbiting electrons.

Quantisation

The wave understanding of light was shaken up by the need to explain two experimental phenomena; the way very hot objects glow (thermal radiation), and the way that shining a light on metal releases electricity (the photoelectric effect). ‘Normal’ physics models did a lousy job of predicting how much high-frequency light would be emitted by a hot object. Max Planck discovered that if the radiant energy were treated as discrete lumps, theory could be made to match reality. When he published his work, his intention wasn’t to make a bold statement about the nature of reality. He assumed that that all he had discovered was a useful mathematical trick.

Einstein took things further in his explanation of the photoelectric effect. He demonstrated that the photoelectric effect could be neatly explained if light were considered to be a particle as well as a wave. That is, light travels around in discrete lumps of energy, but these lumps have many of the properties of a wave, such as a frequency and the ability to interfere with one another. If you find this confusing, you should! We’re all familiar with particles (like sand), and waves (like we see on a beach), but there’s no sensible analogy we can make to understand something which is simultaneously sand and a wave. 

The situation for matter isn’t much better. Although electrons do orbit a proton nucleus, these orbits aren’t like planetary orbits; instead, they’re like rungs on a ladder (“quantisation”). Electrons are only allowed to jump between the rungs, and can never occupy the space in between. “But how”, you may ask, “do they get from one rung to another without traversing the space in between?” Many distinguished physicists have asked the exact same question, and the general scientific consensus seems to be resigned acceptance that we may never find a satisfying interpretation of quantum jumps.

Wave-particle duality

 But there’s more - just as light is both a wave and a particle, even matter - solid, sensible, un-wavey matter - is actually both a wave and a particle. It’s been experimentally observed that electrons and molecules will diffract and interfere with one another. This is known as wave-particle duality, and it applies to both matter and light. It’s part of a broader theoretical framework which asserts  that matter and light - despite seeming entirely distinct - are broadly related. (Einstein’s famous equation, E = mc²  , is a continuation of this idea, and expresses how light and matter can be changed into one another.)    

Spin

As well as position and momentum, all quantum wave-particle-things have a third property, spin. Spin was first observed when particles deflected in a magnetic field, as if they themselves were magnets. In the classical world, this would happen when charged objects spun, so the original experimenters called what they observed spin. Although it’s sort of analogous to angular momentum, quantum spin has to be considered a metaphor. If quantum particles were actually spinning (and were actually particles), their surface would have to move faster than the speed of light to achieve the observed magnetic effects.

You probably won’t be surprised to hear that spin is quantised. (This makes it even less like angular momentum, if you’re keeping track.) There are only two possible values for an individual particle’s spin, up and down. The fact that it only has two values makes spin a pleasing property for storing quantum information, which we’ll come back to later. Spin is also convenient for quantum information because things sit still while their spin is changed. Changing momentum or position, on the other hand, would be much less tidy. It would require the internals of a computer to be constantly racing around while accelerating and decelerating.

Superposition

With only two values to choose from, quantum spin could be a boring property. Things get more lively, though, because of one of the strangest quantum phenomena - superposition. Although any measured spin will be either totally-up or totally-down, the measurement has a chance of being either up or down. That is, until the measurement is made, the spin is both up and down. How much up and how much down is in the mix determines the chances of an up measurement or a down measurement. The same is true for other observables, like position or momentum. This is known as superposition. When a measurement is made, the state converges on a single point. (The mechanism of this convergence is still a subject of scientific debate, known as the measurement problem.)

Since a superposed state can’t be directly observed, why would we think particles are in a superposed state? Superposition follows, at a mathematical level, from wave-particle duality. The first evidence for it is that some measurements give apparently random results. Randomness on its own isn’t evidence that states were superposed immediately before the measurement was done, but there are stronger experiments. Quantum spin was first observed by passing a stream of hot atoms through a magnetic box, and seeing that the atoms deflected into two neat streams (spin up and spin down). If only one of the streams (say, spin up) is passed through a second box, with the field oriented in the same direction, the stream won’t split again. This isn’t surprising; we filtered for spin up, and then we measured the spin again, and it stays spin up. If the second box is rotated, so that the magnetic field is ninety degrees to the first one, the spin is being measured on a different axis, and since we didn’t filter on that axis, the stream will again split into two. What happens if a third box is added, with the field oriented in the original direction? The particle stream has already been filtered to only include those with spin up, but the stream will split. Having its spin measured on a different axis undoes the filtering. Another way of saying that is that the middle box, with the rotated field, put the atoms back into a superposed state. (As well as showing superposition, this experiment shows Heisenberg’s uncertainty principle; if we know the spin in one direction, we erase our knowledge of the spin in the other direction.)

Quantum theories are counter-intuitive, because we all know that's not how the world works. The theories were even unsettling to the scientists who developed them, who struggled with their strange implications. Einstein hated the idea that the world was fundamentally non-deterministic, which led to his famous pronouncement that ‘God does not play dice.’  Schrödinger hoped his later theoretical work would eliminate what he called ‘the quantum jump nonsense’ and expressed regret at ever having contributed to quantum theory..

In order to show how absurd superposition was, Schrödinger devised a thought experiment, in which a cat was isolated from the outside world in a box. Also in the box was a radioactive rock, a bottle of cyanide, and a geiger counter wired to a hammer, which would smash the bottle if any radioactivity was detected. The emission of particles from a radioactive source (radioactivity) is a probabilistic event, which cannot be predicted ahead of time. If a particle was emitted, the poison would be released, killing the occupants of the box. Quantum theory says that until a measurement was made, the decaying particle would be in both a decayed and non-decayed state. This means the famous cat would be simultaneously alive and dead until someone looked in the box to see if the cat had survived ("the measurement"). While everyone agreed with Schrödinger that cats clearly should not be both alive and dead, no one could deny that superposition was the theory which best fit the experimental evidence. This created an interesting challenge - how could a theory be both accurate, and totally absurd?

Schrödinger's cat stayed a thought experiment for two reasons. The first is that it seemed impossible to actually conduct the experiment; no experimenter could know what state the cat was in except by observing it, and the measurement of the cat's health was the very action that would trigger a quantum collapse. The second reason is that it's unethical for physicists to shut cats in boxes and probabilistically poison them.

Entanglement

The final piece of quantum weirdness comes when pairs (or groups) of quantum things have some shared properties. For example, if a pair of photons is generated by splitting a photon, the total spin of the pair has to be the same as the spin of the donor photon. So far, so good, except that if superpositions are involved, the measured state is only determined at the point of measurement. Once the state of one photon is known, we know exactly what the state of the other photon has to be. That means, when one half of the pair is measured, its state collapses, and the state of the other photon also collapses at the exact same moment.  

Einstein had famously stated that information could not travel faster than light, and so he was understandably offended by what he described as 'spooky action at a distance'. Things, he felt, should not be able to affect each other's state instantaneously over great distances. In order to resolve this problem, physicists came up with a ‘hidden variable’ theory - their hypothesis was that even though the states seemed random, some unmeasurable extra property was set at the point of creation, which meant that measurement outcomes were always predetermined, and there was no distressing faster-than-light effect. It seems like a hidden variable theory should be difficult to disprove (by definition; the variable is hidden). However, thirty years after hidden variables were first proposed, John Bell did some clever maths which demonstrated that if measurements were done along different axes, a world with hidden variables would be statistically distinguishable from one without them. Later experiments on entangled pairs have consistently supported the ‘no hidden variables’ outcome.

What kind of distances does entanglement ‘work’ for? Particles can be entangled even when they’re far apart, which makes the correlations and apparent action at a distance even more startling. Chinese researchers have managed to send entangled photons from space to earth, a distance of 1,200 km. What about physical particles? Entanglement has been achieved between electrons located 1.3 km away from each other. What’s extra-impressive with the electron experiment is that the entanglement was ‘transmitted’ to the electrons by entangling them with photons and then sending the photons to get entangled with one another. After this was done, the states of the electrons were random, but perfectly correlated. Spookiness is apparently a transmissable condition. 

Consciousness, multiple universes, and decoherence

Once it was agreed that quantum physics explained things very well, scientists turned their attention to a different question; if the world was quantum, why did it seem so classical? What was it about measurement that destroyed superpositions? One theory is that observation by a conscious being is the key feature of a measurement (that is, the cat is both alive and dead until the box is opened and an experimenter peeks in).

Another theory is that a superposition never actually collapses - instead, each ‘alternative’ carries on in its own world. That is, measurement isn’t a collapse; it’s a branching. This branching process is continuous, and leads to a multiplicity of worlds. These theories have also been combined, with the idea being that when a measurement happens, two universes are created; in each universe, the conscious mind of the experimenter sees a new, internally consistent, reality. Instead of many-worlds, there are many-minds. The (somewhat tautological) reasoning is that since we never perceive something as being in two different states, consciousness is incapable of perceiving something as being in multiple states, and so a given observer has many distinct experiences as they interact with a superposed state.

These theories are intriguing, and include some appealingly familiar themes from science fiction. Sadly, they are of limited scientific value, because they’re impossible to either prove or disprove. The measurement problem is still controversial, but there is a growing scientific consensus that a phenomenon known as decoherence is a significant part of the reason why superpositions collapse. More precisely, there is no ‘collapse’, only a very rapid decoherence as superposed quantum states interact with their environment. The larger the system, the more rapid the decoherence. For example, even in a hard vacuum, interaction with sunlight would cause a dust mote to decohere in 10 microseconds, and a superposed kitten in 10 nanoseconds. (Why a kitten? Schrödinger’s kitten is smaller than Schrödinger’s cat!) It doesn’t make much sense, even as a thought experiment, to ask whether a kitten in a vacuum is alive or dead, since kittens need to breathe. With a breathable atmosphere present, kitten-decoherence would be effectively instantaneous, taking only 10 ^-26seconds.

The more macroscopic a system is, the more environment there is, and so the greater the effect of decoherence. Even apparently isolated systems decohere, because perfect isolation is impossible; the environment will always cause some noise. Decoherence interaction can be mathematically modelled, although the calculations are complex. Probably because of this complexity, decoherence theory was only proposed in 1991, long after the other foundations of quantum mechanics.

Quantum information theory

Quantum information theory deals with how information behaves in a quantum system. Just as the smallest unit of classical information theory is a bit, which can be 0 or 1, the smallest unit of quantum information theory is a qubit, which can also be 0 or 1. A spin is a physically convenient representation of a qubit, so up spin is 0, and down spin is 1. Light polarization can also be used, using horizontal for 0 and vertical for 1. We sometimes represent qubits as arrows, so 0 is down and 1 is up.

Unlike a classical bit, a qubit can also be a combination of the states 0 and 1. This superposition is represented as a point on a sphere. The reason it's a point on a sphere, rather than just a probability between 0 and 1, is that the superposed state has two dimensions, and is represented as a two-dimensional matrix. When measured, a qubit will collapse down to a classical '0' or '1' state, but all operations before that measurement - including multi-qubit-gates - are performed on the more complex quantum state.

A classical single-bit logic gate flips the state of the bit (a NOT operation). A quantum NOT gate represents a 180 degree rotation, but many other operations on a sphere are possible. For example, a 90 degree rotation on a '0' puts the qubit into a state where it's a superposition of '0' and '1' (with an additional twizzle around the axis, this is called a ‘Hadamard gate’). Other operations change the angular position (twisting the sphere around).

One thing the qubit model doesn't really capture, at least not visually, is the notion of entanglement. Multi-qubit gates are able to create entanglement between qubits, and also to disentangle them. A controlled-NOT operation (analogous to an exclusive-OR) is usually used for this purpose - or, perhaps more accurately, entanglement is a side-effect of a quantum controlled-NOT gate. Entanglement has big implications for the computation capability of the system.

It’s generally agreed that entanglement is key to the speedup of a quantum computer. Because entanglement involves correlations between states, an entangled state cannot just be written as the product of two independent states. Thinking in terms of matrices, an entangled state’s matrix cannot be factored into two smaller matrices. That irreduce-ability means entangled states cannot be efficiently simulated on a classical computer. It was, in fact, the computational complexity of simulating large quantum systems on a classical computer which led to the realisation that quantum computers might have superior computational capability.

In part 2 of this series, we’ll look more at computational complexity, and explain how and why some quantum algorithms have much lower computational complexity than their classical equivalents.

About the Author

Holly Cummins is a full-stack developer, and cloud computing technical lead. She is also a frequent speaker, Java Champion, and author of Enterprise OSGi in Action. Holly holds a DPhil (PhD) in Quantum Computation from the University of Oxford.