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 
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 “
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: ![\left[ \frac{1}{8} \sum_{x=0}^7 f(x) \right] |0\rangle+(\cdots)|1 \rangle+ \cdots](https://s0.wp.com/latex.php?latex=%5Cleft%5B+%5Cfrac%7B1%7D%7B8%7D+%5Csum_%7Bx%3D0%7D%5E7+f%28x%29+%5Cright%5D+%7C0%5Crangle%2B%28%5Ccdots%29%7C1+%5Crangle%2B+%5Ccdots&bg=ffffff&fg=000000&s=0 "\left[ \frac{1}{8} \sum_{x=0}^7 f(x) \right] |0\rangle+(\cdots)|1 \rangle+ \cdots")
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 (
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 
Notice that that summation in front of the 
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 
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.
Pingback: Linkblogging For 17/02/11 « Sci-Ence! Justice Leak!
Pingback: Tweets that mention Q: How does quantum computing work? | Ask a Mathematician / Ask a Physicist -- Topsy.com
Regarding the quantum oracle, how could we determine which numbers she liked without getting oracle stabbed?
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.
A single neutron under liquid nitrogen has unlimited rendering potential.
I don’t think that’s true. Do you have a reference?
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’.
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.
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.
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
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.
Can we run quantum algorithms on a normal current computer?
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.
Pingback: Futurist’s Cheat Sheet: Quantum Computing « notiziario internet
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?
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.
o
Pingback: Episode 13: Quantum Computing | The Wonder of Reality
Ok ? I am not a math wiz here : But I think all of you are looking at this the wrong way :
If you have one block that computes in one > way :
Then have a block that computes in the other < way :
Stack them in layers one on top of the other there is no limit to how many stacks you can have :
Each layer is able to compute it's own value and they all work together :
You could compute at a very high number if you stack chips one on top of the other ?
By using a multi task system where each chip works on the problem on a one approach way : you could X times billions of fractions in just a few seconds !
Computer X 100000000000000000000 to the 100 power !
Am I the only one who thinks this way ?
@Dr. Timothy W Price Thd.
You’re definitely not the only one thinking that way! What you’re describing is “parallel computing“. It is an extremely powerful tool and it’s used all the time.
“Quantum parallelism” is kinda similar. A single (quantum) computer can handle a huge number of simultaneous calculations in the same processor (an ordinary computer can only handle one), and quantum computers have the added advantage that those different calculations can interfere (in the wave sense) which opens up a lot of surprising new options.
I can see how the three qubits have all the possibilities but, what about the f(x) that makes the decision, is that processing all of these at once…? How does this tie in with the classical CNOT gate I have read about if at all. Also if you take this to the end point, is the output supposed to be three qubits that indicates a result? How does the interference work to create a result? The Dwave site seemed to give an example that looked very much like a backpropagated trained neural net…?? There are some big jumps in here from the old light slit stuff to suddenly whoooster an end point…
I guess this sort of works for me… the amplitude at step 3…
Experimental realization of Shors quantum factoring algorithm…
http://www.nature.com/articles/414883a.epdf?referrer_access_token=N0d_eMAs-M441VDqxciSkdRgN0jAjWel9jnR3ZoTv0PMrwtfUJ7oOhIqYcp4hAPEwl1B__UiseZhFSViGAnLGU1NAtUJIOJeS37ryWdOmVhcIZgD_osP1-S8u0JnL7iRN2jatD2jTj-a99Q0_ek2ICPc1vBBuDIXWHH7ma1TogyoSyWWjvh2qRUg330NO9RW2zvVAJ6y1e2itpXZbTYyG9PfffJz22aLGL9-JmBppoY%3D&tracking_referrer=physicsworld.com
I’ve been reading a lot about Quantum computers in order to get a better understanding of how they work, and I guess that what confuses me the most is similar to what others have asked here, which is how quantum computing differs mechanically from parallel computing?
I am going to have to do a lot of follow up reading on the material I’ve just read here, but the fuzzy understanding that I have is that in the example of the photon beam splitter, it appears that we have 2 qbits that produce 4 individual pieces of data: (1/2|0, 1/2|1, 1/2|2, 1/2|3). The big difference appears to be that in quantum computing, we produce probability amplitudes as opposed to binary states. Is the data simply a 1=yes, 0=no, 2=maybe? Or is the probability amplitude more of a calculation of chance in percentage of a given result?
As you addressed that it takes clever programming to decipher results, How do we use probability to come to usable conclusions?
How is the way that a quantum computer performing multiple calculations simultaneously different from a parallel system?
If the issue is the constraints of an assembly language that only uses True/False answers, how come we don’t re-write assembly to use 1,1=True, 0,0=False, 0,1=Superposition equivalent, 1,0 = Superposition equivalent to use similar equipment to what we presently have?
It’s an amazingly interesting field of study, and I’m trying to learn as much as I can, but this is the first site I’ve come upon that wants to explain the mechanics as opposed to just focusing on what the technology can do.
Pingback: Q: What are “delayed choice experiments”? Can “wave function collapse” be used to send information? | Ask a Mathematician / Ask a Physicist
Pingback: A CIO's guide to Quantum Computing | CIO WaterCooler | CIOs CTOs & Change Agents