An Introduction
to
Quantum Computation
and
Quantum Communication

Rob Pike
Bell Labs
Lucent Technologies
rob@plan9.bell-labs.com June 23, 2000




Introduction



An analogy:

Newtonian physics is an approximation to Einsteinian physics (general relativity).

Classical physics is an approximation to quantum mechanics.

Classical information is an approximation to quantum information.

In each case, the approximation excludes important details but serves well for many purposes.

In each case, removing the approximation requires deeper understanding and harder math, but results in a truer picture of Nature and may enable new technologies.

Yes, Nature: we're beginning to understand that information is a physical concept.

What approximation do we remove?



Relativity: we remove (among others) the approximation that we are traveling much slower than light.

Quantum mechanics: we remove (among others) the approximation that we are manipulating things much larger than atoms.

Quantum computation: we remove (among others) the approximation that the elements of information are independently manipulable.

Why would we care?



That approximation means that we can look at one bit in a register without affecting the other bits.

Why remove that approximation? Because it limits the power of the computer. (Keep in mind the analogies.)

Also, getting ahead of ourselves, that approximation turns out to be troublesome in representing information quantum mechanically.

Why would we do that?

We're running out of particles.



The insulators in CMOS transistors can't get much smaller or the insulating layers will stop insulating (at around 6 atoms thick). (Maybe before 2010.)

In optical fiber, we use ten thousand or so photons to represent a bit. There's a Moore's law for fiber, too, and we'll soon run out of photons. (Maybe before 2010.)

Quantum mechanical effects will become important in just a few years!

Currently, we work in the classical information regime. That won't last. We'd better come to understand quantum information.

Of course, this version of the story isn't how quantum computation came to be. (Keep in mind the analogies.) So let's back up and tell a more historical story, to introduce the ideas.

Feynman's Question



In a couple of papers in the 1980s, Feynman asked and began to answer the following question:
Is it feasible for a computer to simulate a physical system perfectly?


The answer appears to be, "No". A classical computer seems to need time exponential in n to predict precisely the behavior of a general quantum mechanical system of n particles. (Yet nature manages to do it in real time.)

Briefly, a quantum mechanical system of n particles is represented by a wave function in a Hilbert space of dimension exponential in n. We really do need that much dimensionality to represent all possible behaviors of the system.

Less briefly...

The Nature of Quantum Reality



The two-slit experiment.


1. Single photon still produces interference pattern!

2. Ask which slit photon passes - pattern disappears!

Interpretation



The photon can go through either slit, or both; its state embodies both possibilities.

If we ask which slit it went through, there must be an answer, and the system must decide:
Asking the question changes the state of the system from both possibilities to exactly one.


The Quantum Measurement Postulate
When you make a measurement, the system makes a random selection among the possible answers and chooses one. After the measurement, the system is in the state that always gives that answer; the possibility of other answers is gone.


Do the measurement again (sufficiently quickly) and you'll get the same answer.

Quantum mechanics in two slides (I)



The state of a QM system is described by its wave function, an oscillating complex-valued function defined over all of space. can interfere with itself.

Quantum mechanics is linear. We can create by linear combination, e.g.:


For well-defined states, e.g. up, we use the notation as in


The are complex coefficients that must normalize; if the |> states are orthogonal, the must satisfy:


These are called probability amplitudes and (note the square) is the probability that if we make a measurement of the system, we will find it in state

Quantum mechanics in two slides (II)



The quantum measurement postulate in math:

If we make a measurement on a system with wave function


and find it's in state i, the wave function is now


Math aside: the i are the eigenvalues corresponding to eigenvectors of the operator (e.g. energy) defining the measurement.

See for yourself



Light can be linearly polarized: its vibrations can lie in a plane, say horizontally or vertically. Represent these two possibilities as and We call these orthogonal states a basis of the system.

Plain light is a mixture of these polarizations and in fact a single photon can be a mixture. For example, light polarized at 45° is

Light can also be circularly polarized: circular polarization can be created from linear as follows:


This is another orthogonal basis of the polarization.

We can demonstrate that light obeys the quantum measurement postulate using three linear polarizing filters and an overhead projector....

A few points about wave functions



1. Quantum mechanics is a linear theory: we can create linear superpositions of wave functions, provided we keep the probability amplitudes normalized.

2. The quantum measurement postulate can be described as the wave function `collapsing' to the basis state corresponding to the outcome of the experiment.

3. We cannot discover the full quantum state of a system, only the squared probability amplitudes The are the projections of the system onto the basis states and are complex-valued.

4: We cannot clone an unknown quantum state. There are no quantum wires. (Proof a little later.)

Bits and Qubits



A bit is in one of two states, 0 and 1, represented by e.g. the state of a switch or a voltage.

To map this to quantum mechanics, choose two orthogonal states (e.g. horizontal and vertical polarization) and label these and The state maps to a Boolean 0 or 1.

A qubit is a parcel of information represented by such a system. Because quantum mechanics is linear, unlike Boolean algebra, a qubit can be not just the value and but any complex linear superposition that satisfies the normalization condition.

For example, a qubit might be a horizontally polarized photon; or it might be a vertically polarized one, or it might be a right circularly polarized one, or any other linear combination with appropriate normalization.

The interpretation of Qubits



A bit represents one of two points, but a qubit represents any point on the unit circle in the complex plane.


To ask the state of the qubit is to ask whether it is or and by QMP it must decide. Therefore, when we measure a qubit, we can only ever get or corresponding to Boolean 0 or 1. But until we ask, it can be an arbitrary mixture of and

Multiple bits and qubits



N bits can represent integer values.

N qubits can represent any complex vector of unit length in dimensions, one dimension for each possible classical state. A spectacularly larger set of values!

3 bits can represent any one of 000, 001, 010, ..., 111.

3 qubits can represent any value of the form


as long as


For example, a 3-qubit register might have the value There is no classical analogue of this sort of state. The register represents two (or up to 2^N) different values simultaneously!

The register could be in the `pure' state or but the overwhelming majority of possible states are not pure.

Entanglement



Two classical bits can be 00 or 01 or 10 or 11. We can ask the value of the first bit without affecting the second bit.

Two qubits could be in the state


The first qubit is neither nor

It's not even a superposition of and because the state is not separable: the value of the first qubit is entangled with the value of the second.

We can't discover value of first qubit affecting the second. Say we measure it and get 0; by QMP that means the state of the system is now and therefore the second qubit is now But it wasn't before; it was entangled with the first qubit.

This is another very different feature of quantum information.

Two points about entanglement



1. An entanglement by definition involves multiple qubits; this is not an entangled state:


2. A superposition is not necessarily entangled. Consider


We can measure the first qubit without affecting the second.

Compare the two above with this truly entangled state:


Proof of the no cloning theorem




Proof by contradiction. Assume we have a box that will take an arbitrary qubit and create a copy. Given the result will be given the result will be Given the arbitrary state


we want as output two separable qubits like this:


But quantum mechanics is linear, so applying the box to our state will produce

Unless one of or is zero, this is not the desired state; it is entangled. Therefore the cloning box cannot exist.

Similarly, an unknown quantum state cannot be deleted without affecting the rest of the system.

Conservation of information.

This theorem means: no wires, no oscilloscope probes, no debugging print statements. Note: this theorem doesn't apply once we measure the qubits, since the result is a pure state.

Computation



Classically, we put n bits into a calculation and get m bits out:


A quantum computer can't create or destroy qubits during the calculation, so m must equal n:


The quantum computer is an operator that maps n input qubits to n output qubits. Recall that n qubits represent a unit vector pointing to the surface of a sphere in complex space of dimensions. Therefore the QC is a kind of rotation; it can be represented by a rotation matrix in complex space; such matrices are called unitary.

Quantum systems evolve by unitary operations, and all steps in a quantum calculation must be unitary.

The final measurement step does not need to be unitary, since we can throw data away at the end.

A quantum gate



A quantum gate is a unitary operator, so number of bits in equals number of bits out. No AND or OR, but instead e.g., a controlled-NOT, which inverts B if A is 1:


It's a rotation, so reversible: given the output, we can recover the input.

Other quantum gates include controlled-controlled-NOT, square root of NOT, and other exotica.

Reversibility has the side effect that, in principle, it means a quantum gate can use zero energy (but might take arbitrarily long).

Reversibility has the undesired side effect that we are forbidden from using latches, feedback, or rewritable memory.

The big picture



A quantum computer looks like this, taking n input qubits, the register V, and producing n output qubits, the register W:


The input register can be prepared as a superposition of states, e.g. an equal superposition of all integers from 0 to


The computer then calculates in parallel the function applied to all integers simultaneously.

From QMP, when we measure W, it will choose a Boolean for each bit of the output register according to the resulting entangled wave function of the output qubits.

Design F so that it maximizes the probability that the output we measure is the answer we want.

The big picture continued



Measuring the output collapses the wave function: get Boolean values for all the qubits in W. The result is one of the possible outputs.

Imagine that F is (integer) square root Prepare V as the superposition of all integers from 0 to run the computer, then measure W. Result will square root of some number between 0 and The square root of any such number, with equal probability.

F calculates the square roots of all the integers in parallel, but QMP says we can only find out about one.

For real problems, arrange F so the probability amplitudes of the output state strongly favor the desired output from F.

Recall the double-slit experiment. Quantum computers are like huge multidimensional arrays of slits that generate interference patterns in the wave functions. Design the array right, and the pattern solves your problem.

A quantum computer is probabilistic: we may need to run it multiple times before we get the answer we want.

Shor's algorithm, simplified (I)



Peter Shor showed how to design a quantum computer to calculate the factors of an integer in polynomial time, theoretically breaking RSA.

We want to factor N, that is, find A and B such that AB = N.

Trick: find distinct x and y such that


Then


so one must contain a factor, which we can find by e.g. gcd(x-y, N).

Next, take y to be 1, so if and r is even then


Then r is the period of the function in a.

Shor's algorithm, simplified (II)



Looking for pair x, r such that

Greatly simplifying, algorithm builds a superposition of all integers x < N, then calculates for all a in parallel.

Discover the periods using a (quantum) FFT on the resulting entanglement. The final state is (sort of) an entanglement of all valid x, r pairs.

Finally, measure the output register. QMP says it must choose one x, r pair, and we can factor.

With small probability the output may be zero; if so, we run it again.

Not much like a regular computer program!

What else can we do?



Shor's algorithm
factors in polynomial time.


(We expect to get a non-zero result in a small number of runs.) It's dramatically faster than any known classical algorithm;

Entanglement gives us exponential parallelism.

A few other quantum algorithms go faster than classical. Most are obscure but one is important:

Lov Grover's algorithm searches an unordered database of N elements to finds an element satisfying a given condition in square root of N time. In other words,
it searches a linear list in square root time.


Not as dramatic as the exponential speedup in Shor's algorithm, but remarkable and possibly even practical.

Decoherence



Factoring a 200-digit number using Shor requires 3500 perfectly well-behaved qubits. (Current state of the art is four entangled qubits.) But that's not the hard part.

The challenge is decoherence: the `leakage' of quantum state into the environment. Actually, it is entanglement with the environment. (Believed to be the explanation for why the macroscopic world behaves classically).

QC must be run in a sealed box without any interaction with the outside world. Otherwise the qubits will be contaminated. (This is another reason debugging could be hard.)

The required isolation is extreme; today's entangled atomic states in the lab last for about 10ns, and decoherence proceeds exponentially fast in the number of particles.

Error correction



Decoherence would be the death knell for QC, except that Shor and others discovered quantum error correction. Like classical error correction, but QEC can correct an arbitrary error in a qubit, even if we don't know its state! (Much more astonishing than repairing a bit flip in a classical message.)

Many such codes exist, e.g. 7 qubits can fully repair damage to any one qubit in the message.

QEC could compensate for decoherence and other losses if they're at a low enough rate. (Current theory ranges from .000001 to .01.) Error correcting a t-step computation involves overhead polynomial in log t.

Using Shor to factor 200 digits requires 3500 perfect qubits, 100,000 if error correction is involved.

Quantum communication



Computation may be extremely hard because it involves many qubits. But communication can work one qubit at a time. Error-correcting such states might be practical. Experiments have reliably transmitted kiloqubits per second over many kilometers of fiber, and in one case a mile of open air!

Is this a solution to the running out of photons problem? An open question. Several ways to communicate:
C: Send classical bits.
Q: Send qubits.
Send qubits but also use two-way classical communication to assist.
Send qubits but first prepare them by prior entanglement between sender and receiver.


Channel capacities:


Entanglement is again the source of power.

EPR pairs



Einstein, Podolsky and Rosen proposed a thought experiment to show that quantum mechanics was crazy. Today we can do the EPR experiment and Einstein would have hated the result: QM is crazy.

Based on EPR, we can do stuff like teleportation, unbreakable key exchange, and high-efficiency communication.

Electron-positron annihilation produces two photons:


The two must have entangled states: the polarization of one must correlate with the polarization of the other.

What if Alice measures using plane polarization? Then if Bob measures using plane polarization, he must get same answer. Ditto for circular. But.... what if Alice doesn't tell until after Bob measures?

A classical channel can be used to report how the measurement was done, and Alice and Bob can compare notes.

Using EPR pairs



Quantum key exchange: Exchange a bunch of EPR pairs. Alice reports the basis she used for her measurements; Bob checks against his, and the photons measured in the same basis get the same answer.

Cannot be tapped because tapping will destroy the entanglement. Alice can add extra `check' bits; Bob can check them to see if key has been tampered with.

After sharing an EPR pair, two classical bits can send an arbitrary quantum state from Alice to Bob. Alice combines her half of the pair with the state (say an atom), does a measurement, and sends the result to Bob. Bob uses the bits to entangle his half of the pair and the destination atom. Result is to transfer the unknown state to the atom: Teleportation!
More about EPR pairs



In a similar experiment, after prior sharing an EPR pair, Alice can send Bob two classical bits in one qubit. This is called superdense coding. Time is important: Alice and Bob can share and separate months before Alice decides which bits to send.


EPR pairs are a new kind of data communication. There's nothing like them in classical information theory.

Quantum computation can reduce the time complexity of some calculations.

Quantum communication can reduce the communication complexity of some calculations.

Physical Realizations



Far from an exhaustive list.

Photons: 23 km. of fiber under lake Geneva, reflecting with polarization change at the end back to sender. (Gisin, U. Geneva).

Electrons: Floating on liquid helium with electrodes underneath; too early to tell (Platzman & Dykman, Bell Labs).

Atoms: Ion traps, controlling quantum state by external laser pulses (Cirac & Zoller, Austria; Kimble, Caltech). Passing qubit from atom to photon is work in progress.

Molecules: NMR on an ensemble of molecules (e.g. chloroform, trichlorethylene) (Gershenfeld, MIT).

All these have limitations. Current status: a few qubits.

Solid state: In the future. Quantum dots, ultrasmall Josephson junctions, semiconductor microcavities, ...

Conclusions



As computational elements get smaller and smaller, quantum mechanical effects will become important. Somewhat to our surprise, this may turn out to be a good thing.

Information is a physical variable, and we can use the properties of its physical manifestation to our advantage. Quantum mechanical information has deeper structure and greater power than classical information.

Studying information as a physical notion helps us understand. For example, to understand what can and cannot travel faster than light, say this: information cannot travel faster than light.

A final thought: Sixty years ago classical computers seemed as remote as quantum computers do today.

Summary



Table adapted from Bennett & DiVincenzo:

Quantum speedups:

Factoring: exponential; Search: quadratic; Iteration, parity: no speed-up; Simulation of quantum systems: up to exponential.

References



Richard. P. Feynman, "Simulating Physics with Computers", International Journal of Theoretical Physics, 1982, Vol. 21, No. 6/7, pp. 467-488.

R. P. Feynman, "Quantum Mechanical Computers", Foundations of Physics, 1986, Vol. 16, No. 6, pp. 507-531.

C. H. Bennett and G. Brassard and A. K. Ekert, "Quantum Cryptography", Scientific American, October 1992, pp. 50-57.

P. W. Shor, "Quantum Computing", Documenta Mathematica, Extra Volume ICM 1998 I, pp. 467-480.

Three good overviews:

Charles H. Bennett & David P. DiVincenzo, ``Quantum information and computation'', Nature, Vol. 404, 16 Mar 2000, pp. 247-255.

A. Steane, "Quantum Computing", Reports on Progress in Physics, 1998, Vol. 61, pp. 117-173, https://xxx.lanl.gov/abs/quant-ph/9708022.

E. G. Rieffel and W. Polak, "An Introduction to Quantum Computing for Non-Physicists", 1998, https://xxx.lanl.gov/abs/quant-ph/9809016.

Copyright © 2000 Lucent Technologies Inc. All rights reserved.