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 2^N 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 “|x\rangle” 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:

\frac{1}{\sqrt{8}} \sum_{x=0}^7 | x \rangle = \frac{1}{\sqrt{8}} | 0 \rangle + \frac{1}{\sqrt{8}}|1 \rangle +\frac{1}{\sqrt{8}}| 2 \rangle +\frac{1}{\sqrt{8}}| 3 \rangle +\frac{1}{\sqrt{8}}| 4 \rangle +\frac{1}{\sqrt{8}}| 5 \rangle +\frac{1}{\sqrt{8}}| 6 \rangle +\frac{1}{\sqrt{8}}| 7 \rangle

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: \left[ \frac{1}{8} \sum_{x=0}^7 f(x) \right] |0\rangle+(\cdots)|1 \rangle+ \cdots.  There are other weird summations for each of the other states (|1 \rangle, |2\rangle, \cdots) 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 (|0 \rangle) 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 |0 \rangle (since 1^2 = (-1)^2=1), and if she half-n-halfs you’ll definitely see some other state, and not see a |0 \rangle (since 0^2=0).

Notice that that summation in front of the |0\rangle 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 2^{20} 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.

This entry was posted in -- By the Physicist, Computer Science, Engineering, Entropy/Information, Math, Physics, Quantum Theory. Bookmark the permalink.

15 Responses to Q: How does quantum computing work?

  1. Pingback: Linkblogging For 17/02/11 « Sci-Ence! Justice Leak!

  2. Pingback: Tweets that mention Q: How does quantum computing work? | Ask a Mathematician / Ask a Physicist -- Topsy.com

  3. Chris says:

    Regarding the quantum oracle, how could we determine which numbers she liked without getting oracle stabbed?

  4. The Physicist The Physicist says:

    Assuming that the Oracle sticks with “yes/no” answers, then no. You’ll get stabbed.
    Quantum mechanics and nigh magical processing aside, the algorithm is still giving you one bit of information: either the Oracle (1) always has the same opinion, or (2) she likes half/hates half.
    There are 70 different ways that she could like 4 and hate 4 of the numbers 0-7, and it will always require an average of 6 or 7 yes/no questions to figure out exactly which like/hate pattern she’s got.
    (log base 2 of 70 is 6.129…, which is pretty close to 6 bits)
    It doesn’t matter how you come by those yes/no answers, you’ll still be bound by that lower limit.

  5. Bo Brymer says:

    A single neutron under liquid nitrogen has unlimited rendering potential.

  6. The Physicist The Physicist says:

    I don’t think that’s true. Do you have a reference?

  7. Will Huang says:

    Excuse me… I’m not sure I quite understand the Quantum Fourier transformation concept. Could you explain it in a way that is somewhat understandable to a high school student? I’m writting an ‘extended essay’ on quantum computation and its related topics and I want to make sure I comprehend all of its methodologies and ‘philosophies’.

  8. The Physicist The Physicist says:

    There’s a (fairly technical post) here that talks about the Quantum Fourier Transform a lot (particularly in “step 4″). It was written by the handsomest person I know.
    The exact name should be “Quantum Discrete Fourier Transform”. The Discrete Fourier Transform (DFT) takes a list of numbers and tries to express those numbers as a sum of sines and cosines. For example, if the signal, f(t), could be expressed as f(t) = A cos(Bx), then the Fourier transform would be a spike at “B” (the frequency) that’s “A high” (the amount of that frequency). A more complex signal will have more spikes, and in fact as often as not the Fourier transform has just as many numbers as the original function, f(t). The “Fourier Transform part” of the QFT is probably the more difficult to understand.
    The “Quantum part” of the QFT is a little nuanced. In this case the list of numbers is the “probability amplitude” of that index being measured (actual probability is the square of the probability amplitude, because the universe prefers it for some damn resaon). By index I mean, the “0th term, the 1st term, the 2nd term, etc”.
    So, for example \frac{1}{2},\frac{1}{2},0,0,\frac{1}{\sqrt{6}},\frac{1}{\sqrt{6}},\frac{1}{\sqrt{6}} means that if you were to measure (look at) the number there’s a 1-in-4 chance of getting a 0 or 1 (the first term is the “0th term”), there’s no chance of getting a 2 or 3, and there’s a 1-in-6 chance of getting a 4, 5, or 6.
    Keep in mind this is all in one register. All on the same pocket-calculator screen, so to speak. The QFT takes these different probability amplitudes as its string of numbers, and spits out how much Sin(x) and how much Cos(5x) and how much… you’d need to create that particular string of numbers. The results, however, also take the form of a single register in many states, just like the original register. However, if there’s just one or two frequencies that show up a lot (i.e., it mostly takes Sin(7x) to make the original string of numbers), then it will be likely that when you measure the results of the QFT you’ll see that frequency. Not 100%, but more likely.
    Anyway, read the “Shor algorithm post“. It’s better than a comment.

  9. Q guy says:

    Can we run quantum algorithms on a normal current computer?

  10. The Physicist The Physicist says:

    Nope!
    You need something that can do the processing on many states simultaneously. While normal computers are screaming fast, they still do everything one step and one state at a time.

  11. Pingback: Futurist’s Cheat Sheet: Quantum Computing « notiziario internet

  12. Jcacustodio says:

    Well, and can we run quantum algorithms on a powerfull network of normals computers running on real parallelism? Or we’ll got the same problem when facing the output?

  13. The Physicist The Physicist says:

    Running computres in parallel does increase the overall processing power, but you still have a single computer state overall. Classical parallelism (bunches of computers) doesn’t produce more states, just a bigger computer with one state. A quantum computer on the other hand is litterally in multiple states simultaneously.

  14. Ask a Philosopher says:

    o

  15. Pingback: Episode 13: Quantum Computing | The Wonder of Reality

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>