Quantum
computing has gotten a ton of press, due to its enormous
theoretical promise--essentially, that you can parallelize your
computations across parallel
universes.

Unfortunately,
it's possible that like fusion power, which is theoretically
superior to all other forms of power generation but currently
seems intractible in practice, quantum computing is "the
technology of the future, and always will be". It's also
possible the laws of physics constraint quantum computers to
impractically small size--we don't know enough about the coherence
collapse process to say for sure.

Ordinary Computer | Quantum Computer | |

Goal |
Get 'er done! | Speedups up
to exponential: e.g., search n values in sqrt(n) time, factor integers in polynomial time. |

Data storage | 1's and 0's (bits) | Vector with axes 1 and 0
(qubits) Not just 1 or 0: both at once (Hadamard gate) |

Assignments? | Yes | No (quantum "cloning" violates laws of physics) |

Reversible? | No (e.g., assignments) |
Yes, except for "measurement"
operations, which cause wavefunction collapse. |

Swap? | Yes | Yes |

Logic gates | AND, OR, NOT | CNOT, Hadamard rotate 45 degrees |

ProgrammingModel |
Ordinary instructions | Reversible Quantum Gate
Operations, and Irreversible Collapse |

Clock
Limit |
Switching speed |
Coherence time |

When? | Now | ??? |

Hardware Limits |
Heat/power |
How many bits can you keep coherent? |

In some
fields, there's a simple and easy to visualize core operation,
concealed beneath layers of confusing and complicated
notation. I'm actually not sure if quantum mechanics is like
that, or if it's confusing and complicated all the way down!

You can get a decent feeling for the process of quantum gate
design using a simulator
like jQuantum, by Andreas de Vries (download the .jar, since
applets are now forbidden unless you're on HTTPS and have a
certificate). It makes very little sense unless you are
working through a good set
of example quantum circuits.

Many things, like photons or electrons, display several very odd mechanical properties with mystical sounding quantum names. The key point here is that everything is made of waves.

The wave equation for a particle is the Schrödinger equation .

*i*is the usual square root of -1, since the wave phase is represented using complex numbers.*ħ*("h bar") is just a constant, the reduced Plack constant.- Ψ ("psi") is the wave itself. The probability of observing an electron at any given location is the square magnitude of the wave's amplitude. The phase of the wave isn't observable.
- The interesting part is H, the Hamiltonian, which measures how much energy the particle has. If the Hamiltonian is positive, that part of the wave oscillates, changing faster with more energy. If the Hamiltonian is negative, that part of the wave dies away exponentially fast--this allows quantum tunneling.

Restating this equation in small words, "a particle's wave changes with time depending on the particle's energy."

I prepared some photographic examples of wave properties visible in laser light. Waves are very strange; see IBM's atomic force microscope images of electrons bouncing off atoms, compare to the Falstad ripple tank applet (again, download the .jar, because applets are dead) for an interactive version.

- Superposition:
an electron can be in several places at once, or several states
at once. The terminology here is that the electron's wave
function has spread over space. Needless to say,
classical particles such as billiard balls cannot do this: the 8
ball is in the corner pocket, or not; but an electron can be
around an atom AND not at the same time.

- Entanglement:
electrons can interact. Electrons in a superposition of
states can interact. Interactions between superpositioned
electrons always collapse to consistent values,
telling a consistent story of the electron's history. This
can create surprisingly complex interactions, since the
interaction of n binary unknowns represents 2
^{n}total interactions. Entanglement is the key feature that lets quantum machines scale exponentially faster than classical machines.

- Collapse: if something big (e.g., a human being, a microscope, or any macroscopic measuring device) stares at the electron, it appears in exactly one place. This is called "wavefunction collapse", because the spread-out wave function bunches up again; or "state reduction", since you start with many states and end up with one state. Worse yet, it's looking less like collapse is somehow tied to an "observer", which would be merely creepy (what counts as an observer?). Delayed quantum erasure experiments mean it's probably entangling your wavefunction with the electron's, which would be freaky: just looking at the plots splits your own wavefunction into several pieces! This would mean collapse is just an illusion; what is happening is the particle's superposition has been extended to you.

A quantum computer is based on "qubits", which you can think of as a dot in 2D space: the X axis means a "0", the Y axis means a "1". Normal bits must lie on one axis or another, but qubits can live between the axes. For example,

- (X,Y) coordinates (0.7,0.7) means "might be a 0, or might be a 1". Said more mystically, this is the "quantum superposition of 0 and 1". If you measure the qubit, it will randomly "collapse" to either 0 or 1.
- (0.0,1.0) means "definitely a 1". If you measure the qubit, you'll always get a 1. (0.0,-1.0) actually means the same thing.
- (0.3,0.95) means "it's probably a 1, but might still be 0". If you measure the qubit, you'll get a 0 10% of the time (10% = 0.3*0.3), and a 1 90% of the time (90%=0.95*0.95).

Since coordinates (0,0) means "not a 0, and not a 1", and we don't know what that means, we usually require the qubit to live on a unit sphere--it's either going to be a zero or going to be a one, so the probabilities (equal to the square of the amplitude) must add up to one.

There are many
ways to implement qubits, such as via photon polarization, where
"0" means horizontally polarized, "1" means vertically polarized,
and a superposition is unpolarized. You could also implement
the qubits as possible positions of an electron, where "0" means
in the left box, "1" in the right box, and superposition means
it's sitting in both boxes at once. D-Wave
represents qubits as magnetic fields generated by a current
loop in a superconductor; "0" means pointing north, "1" means
pointing south, and superposition means both at once.

Tons of
research groups have built single-bit quantum computers, but the
real trick is entangling lots of bits together without premature
"collapse", which seems to be a lot harder to actually pull off,
typically requiring the system to be electrically isolated,
mechanically isolated from vibrations, and kept near absolute zero
(e.g., D-Wave runs at 20 milliKelvin = 0.02 K). Collapse is
the single biggest limiting factor in building useful quantum
computers.

Just like a
classical computer uses logic gates to manipulate bits, the basic
instructions in a quantum computer will use quantum logic
gates to manipulate individual wavefunctions.
Because you don't want to destroy any aspect of the data (this
causes decoherence), you can represent any quantum logic gate with
a rotation matrix (a unitary matrix).

I think of a qubit like a little vector. One qubit is
2-float vector representing the amplitudes for zero and one:

a=0 |

a=1 |

A "Pauli-X" gate is represented by this 2x2 rotation matrix:

0 | 1 |

1 | 0 |

Plugging in the input and output probabilities, we have:

a=0 | a=1 | |

output a=0 | 0 | 1 |

output a=1 | 1 | 0 |

The amplitude for a=1 on the input becomes the amplitude for a=0
on the output, and vice versa--this is just a NOT gate!

A controlled
NOT takes two bits as input. Two qubits makes a 2^{2}=4
float vector with these components:

a=0 && b=0 |

a=0 && b=1 |

a=1 && b=0 |

a=1 && b=1 |

The CNOT gate's matrix is basically a 2x2 identity, and a 2x2 NOT
gate:

1 | 0 | 0 | 0 |

0 | 1 | 0 | 0 |

0 | 0 | 0 | 1 |

0 | 0 | 1 | 0 |

Again, putting in the input and output vectors, we can see what's
going on:

a=0 | a=1 | |||

b=0 | b=1 | b=0 | b=1 | |

a=0 && b=0 | 1 | 0 | 0 | 0 |

a=0 && b=1 | 0 | 1 | 0 | 0 |

a=1 && b=0 | 0 | 0 | 0 | 1 |

a=1 && b=1 | 0 | 0 | 1 | 0 |

If a=0, nothing happens--b's probabilities are exactly like
before. If a=1, then b gets inverted, just like a NOT gate.
If a is in a superposition of states, b is in a
superposition of being inverted and not being inverted.

The basic programming model with a quantum computer is:

- Initialize your quantum registers with a superposition of 0 and 1: these hence contain every possible answer.
- Run a series of instructions to selectively amplify the answer you're looking for, or attenuate the answers you're not looking for. For example, you can arrange "wrong answers" so they cancel each other out. Each instruction must be a reversible operation, but in theory can be arbitrarily complex and there's no theoretical limit on the number of instructions. However, in practice, the machine only works if you can keep the whole register entangled in a coherent superposition: accidental collapse or "decoherence" is currently the limiting factor in building big quantum computers.
- Finally, look at the register. The act of looking will "collapse" to a particular set of 1's and 0's, hopefully representing the right answer. If there are several right answers, physics will pick one randomly.

People started to get really interested in Quantum Computers when in 1994 Peter Shor showed a quantum computer could factor large numbers in polynomial time. The stupid algorithm for factoring is exponential (just try all the factors!), and though there are smarter subexponential algorithms known, there aren't any non-quantum polynomial time algorithms known (yet). RSA encryption, which your web browser uses to exchange keys in "https", relies on the difficulty of factoring large numbers, so cryptographers are very interested in quantum computers. In 1996, Lov Grover showed an even weirder result, that a quantum search over n entries can be done in sqrt(n) time.

At the moment,
nobody has built a popular, easy to use quantum computer, but
there are lots of interesting experimental ones. The biggest
number a quantum computer has factored is 21 (=3*7, after piles
of science; see readable poster
description of process). But *if* the hardware
can be scaled up, a quantum computer could solve problems that are
intractable on classical computers. Or perhaps there
is some physical limitation on the scale of wavelike effects--the
"wavefunction collapse"--and hence quantum computers will always
be limited to a too-small number of bits or too-simple circuitry.
The big research area at the moment is "quantum error
correction", a weird combination of physics-derived math,
experimental work on optics benches, and theoretical computer
science. At the moment, nobody knows if this scaling of
hardware and algorithms will combine to enable useful computations
anytime soon.

There's a different "Adiabatic Quantum Computer" design used by
British Columbia based quantum
computer startup D-Wave that they hope will scale to
solve some large problems. The adiabatic part of the name
refers to the adiabatic
theorem, proved in 1928, that says a system in quantum
ground state, moved slowly (adiabatically) to a new state, is
still in ground state. In practice, this allows the quantum
solution of reasonably large problems, up to 512 bits on their
current hardware, but only those that fit this model and the
company's choice of wiring. This is not a general-purpose quantum
computer, but it has shown speedups on real-world optimization
problems. They published some results in Nature (described
here), and have some fairly big contracts from Amazon,
Lockheed Martin, Google, etc. D-Wave raised
another $29 million at the end of 2014, so somebody thinks
they're on to something useful.

Basically every big tech company has some people working on quantum computing, from Microsoft to Google.

How do we deal with the cryptographic
threat from quantum computers?

- Hope nobody can ever build a quantum computer.
- Patch up a cryptosystem that has a known quantum attack, like
RSA or elliptic
curves, by just using more bits--for example, since Shor's
algorithm takes n
^{3}time, use n=1 billion bits. It's OK, I'll wait. - Sadly, *every* cryptosystem seems vulnerable to a Grover-type
quantum brute force attack, assuming the cipher can be
implemented quantum gates (that is, workarounds for no-cloning
can be figured out). This means the existence of quantum
computers will at a minimum require twice as many bits to resist
brute force, for example using 256 bits by default instead of
128 bits.

- Ideally, we would use a cryptosystem that cannot be implemented efficiently on a quantum computer. For example, the no-cloning theorem makes it difficult to implement algorithms that repeatedly re-use inputs, like many hashes or secret key ciphers.
- Use quantum key distribution, not encryption, to distribute cryptographic keys. Send the real data using a quantum distributed one-time pad. (If you can't beat 'em, join 'em!)