How Does a Quantum Computer Work?

I've read Wikipedia, I've read How Stuff Works, I've read The Singularity is Near, but I still just don't get it. How does a Quantum Computer work? It sounds very intriguing, but I just can't wrap my mind around it. I would greatly appreciate it if someone could explain it to me as they would explain the basics of it to their 7 year old nephew (who apparently is probably about equal to me in their ability to understand this concept!)

Typically analogies work best when explaining concepts to the unenlightened, but this is quantum theory, so I'm not sure any analogy could exist that can explain such a bizarre concept ;)

• There is no quantum computer (yet) and certainly not any programmable quantum computer equivalent to classical computers. Are you perhaps asking for general quantum principles these computers want to exploit? Or do you want a description of some of the most popular quantum algorithms? The latter (and perhaps also former) would be better addressed at stackoverflow or cstheory sites. Commented Jul 19, 2011 at 15:54

A quantum computer is just a computer which uses quantum states instead of classical states. Quantum states are just combinations of classical states.

Say a computer takes a certain input $x_i$ to output $f(x_i)$. According to quantum mechanics, you can set up your computer such that its input is a combination of all of the classical inputs $x_i$, namely $\frac{1}{n} \sum_i^n x_i$. After operating, your computer would then take this combination of all inputs to the combination of all outputs $\frac{1}{n} \sum_i^n f(x_i)$.

If this is all there was to it, we could compute all of the outputs of a function as fast as we could compute one. The quantum caveat is that when you go to look at your answer, you don't see $\frac{1}{n} \sum_i^n f(x_i)$, you see $f(x_i)$, for some $i$, with probability $\frac{1}{n}$. So it looks like we've only computed the function once after all! However, if we're clever, we can still benefit from our quantum computer. Let's say, instead of wanting to know all the values, $f(x_i)$, we want to know some function $g(f)$, which depends on all of the answers $f(x_i)$. If we're clever enough, we can sometimes come up with an algorithm which takes $\frac{1}{n}\sum_i^n f(x_i)$ to $g(f)$. The classical computer might have needed to compute every $f(x_i)$ just to find $g$, but the quantum computer can just do it "once."

Please Note: this isn't exactly how it works in most cases, but most cases require quite a bit of math to describe accurately. But this is the "general idea" of why quantum computers can outperform classical ones.

• As I understand it, quantum computers don't exist yet... Is this true? If so, what are the obstacles in realizing them?
– Paul
Commented Sep 9, 2012 at 17:03
• @Paul entanglement. usnews.com/science/articles/2012/05/01/… Commented Dec 19, 2012 at 23:20
• Great answer, very helpful. However I'm certain this can be explained without math, with enough thought. It took me a few years to figure out how to do that for michaelson interferometers (for medical imaging) - it can be done! Commented Jun 10, 2016 at 15:24