Q: How does quantum computing work?

The original question was: Could you give a description of the principles behind quantum computing? And how is it that some problems have a better time-complexity when they’re run on a quantum-computer?

Physicist: Particles and sets of particles are frequently seen to be in multiple states simultaneously.  The internal mechanisms of a quantum computer are, similarly, in many states at the same time.  An ordinary computer can take a single input, do a single calculation, and output a single result.  A quantum computer can take many inputs, do many calculations, and produce many results at the same time.

The number of parallel computations increases exponentially with the number of qbits (quantum bits) involved.  So, while a normal computer can take exactly one input with N bits, a quantum computer can take inputs, simultaneously, with N qbits.

Like a Turing machine, the exact construction of a quantum computer (and there are a lot of extremely different constructions) isn’t particularly important for the philosophy behind its functioning.  Some example architectures include: ion traps, anyon world line manipulation, and diamond spintronics.

In the picture below (and in general) the notation “” is read as the “x state”.  Nothing special, just notation.  The number in front of a state is that state’s “probability amplitude”.

One method for generating qbits is to fire a photon at a beam splitter. The photon both passes through (0) and is refelected (1). Unlike an ordinary bit, a qbit is in both states at the same time. If you set this up several times you can get several qbits, and you can talk about larger numbers. With two qbits you can have the numbers/states 0, 1, 2, and 3 (00, 01, 10, and 11 in binary) all at the same time.

But, a quantum computer is more than just a lot of normal computers running in parallel.  Those different internal states interfere with each other, adding and subtracting from each other the same way waves can undergo constructive and destructive interference.  Quantum interference is the means by which a quantum computer does its computations (the quantum part anyway).  Most proposed quantum computers can also do classical computations.

Therein lies the problem with quantum computers.  A quantum computer can do all of those calculations simultaneously, but the answer it spits out is a jumbled mess of every possible answer.  The trick to a good quantum algorithm is to find a way to express that jumbled mess as something useful.

An excellent (free) reference can be found here.  They are the lecture notes for a quantum computation class in the 90’s, by John Preskill.  Were I so equipped, I would have Preskill’s babies.  Awesome notes.  Reads like a good book.

To understand quantum computers it helps to see an example of a quantum algorithm.  So, for the not-faint-of-heart and the girded-of-loin, what follows is answer gravy:

Deutsch’s problem: One of the classic examples of quantum computation is “Deutsch’s problem”.

Say you’ve got an impatient (quantum) Oracle, that has surprisingly strong opinions about all the numbers from 0 to 7, and hates (hates) answering questions.  So, after answering more than a couple of questions it start stabbing.

If you give the Oracle a number it either says “Good number!” (signified by 1) or “Bad number!” (signified by -1).  Somehow you find out that either the oracle always says the same thing, or it says it likes exactly half of the numbers and hates half of the numbers.  So, for all the numbers 0 to 7 it could hate all of them, like all of them, or like 4 / hate 4.

The Quantum Oracle after three or more questions.

It’s worth noting here that Deutsch’s problem doesn’t really solve anything, it’s just an interesting example.

So, if you ask “0?” and the Oracle says “Good number!” you now know that either she likes all numbers, or likes half / hates half.  To know for certain you’d have to ask as many as 5 questions (it might like 0-3, and hate 4-7), and by then you’d be Oracle stabbed.

If only there were some way to ask it about every number at the same time…

Here it is: Prepare 3 qbits.  With these you can represent a super-position of every number between 0 (000) and 7 (111), using binary.  The Oracle (being a quantum Oracle) can respond to each number at the same time, when you give her a superposition of every possible number, but she’ll give you a superposition of every possible response.

The input is a quantum state that looks like this:

This is just an even combination of every number from 0 to 7 where (since probability is the square of the probability amplitude) the probability of each term being seen is 1/8.

If the Oracle’s answer to the number x is f(x), then as a result (never mind how), you can construct a new state: .  There are other weird summations for each of the other states () but for this problem the zero state is the only important one.

So if the Oracle hates all the numbers you have 8 -1’s (totaling -8), if the Oracle likes all the numbers you have 8 1’s (totaling 8), and if the Oracle likes half and hates half you have 4 1’s and 4 -1’s (totaling zero).  So, if the Oracle likes all the numbers the probability amplitude of the zero state () is 1, if she hates them all the amplitude is -1, and if she half-n-halfs the amplitude is 0.

Since probability is equal to the square of the amplitude, if she either hates or likes all the numbers then you will definitely measure a (since ), and if she half-n-halfs you’ll definitely see some other state, and not see a (since ).

Notice that that summation in front of the is over every number from 0 to 7.  Normally, you can’t ask about more than one number at a time, but because of “quantum parallelism” you can input multiple, over-lapping, numbers/states at the same time, and even process them simultaneously.  In an ordinary computer the number could be just zero, or just three, or whatever, but never all of them at the same time.  Notice also that when the Oracle “half-n-halfs” that summation becomes “+4-4=0”.  That’s destructive interference!  (the other possibilities involve constructive interference)

So, by asking a single “quantum question” you can discover instantly whether the Oracle always has the same opinion about the numbers 0-7, or has differing opinions.  Normally, you’d be stuck asking as many as 5 ordinary questions.  The same technique continues to work even for very large numbers.  For example, it’s still just one quantum question when you’re considering the Oracle’s opinion on the numbers 0 to 1,048,575 (which is numbers).

But, the drawback is always that the answer comes back as a combination of every input, requiring the writer of the quantum algorithm to be crazy-clever.