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. – Marek Jul 19 '11 at 15:54

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."