Currently, the world's fastest supercomputer runs at 17.59 Petaflops, which consumes 9 megawatts of electricity. A qubit-based quantum computer has the potential to operate much more quickly for some operations than a classical computer would be able to (as noted in this question). In fact, classical computers face a major hurdle in computation speed due to the inherent capacitance of components. My question is: would a quantum computer able to compute things faster than a classical computer do so with less, about the same, or greater power draw for equivalent operations? Would that depend on its implementation?

-

If a quantum computer can be implemented at all, it will inherently be many orders of magnitude more power efficient for arriving at a given solution.

One way to explain why is that a quantum computer doesn't rely on entropy in the conventional sense at all. Instead, it sort of "settles down" to a solution that undermines standard (entropic) definitions of past and future. That is the "entanglement" part of quantum computing, the part that just cannot be modeled by any classical methods. As a very rough analogy, that part is a bit like moving towards a solution every so slightly, then going back in time a wee bit and starting the computation over again with that slightly improved result. Do that a gazillion times and even an intractable factoring problem becomes solvable.

Here's a physical comparison: Imagine trying to erase a small granite block by using only pencil erasers. Doesn't sound very easy, does it? Sure, you can rub a few molecules off of the block with a pencil eraser before the eraser gives out, but to do the entire job would take untold numbers of centuries, at an unbelievable cost in terms of erasers (the "entropic" cost).

But now imagine that every time you finish rubbing a few molecules off of the granite block, you get to go back in time and repeat the erasing process, this time using that slightly smaller granite block. You will still need to repeat the process an unimaginable number of times to finish erasing the granite block, but two things have changed dramatically: You no longer need centuries to do it (it's incredibly faster), and you no longer need a nearly infinite number of new pencil erasers to do it (it's incredibly less entropic, that is, the resources needed have become almost negligible).

If all of that sounds way too good to be true, you now are getting a small inkling of why in the decades since @PeterShor first proposed a quantum computing algorithm, the very possibility has riveted the minds and resource of many physics, security, and computational researchers around the world. Factoring a truly huge number actually by known methods turns out to be harder than erasing granite blocks using pencil erasers, not easier. In fact, it's pretty easy to come up with factoring problems that to complete using conventional computing would require time spans that are many times larger than the entire history of the universe.

I should mention that the second "spice" in quantum computing is its massive parallelism, which is a somewhat different aspect of quantum mechanics that is often presented as a full explanation. That part relies on the idea that instead of running just a single value through a computer (e.g., sending a "1" bit into an input port), quantum mechanics allows you to run multiple inputs through the same port at the same time (e.g, both "0" and "1" bits, a combination that is referred to as a qubit). Do that with enough inputs and you end up getting a huge and combinatorial increase in computational power, an increase that is nothing to be laughed at.

This is often thought to be the truly "quantum" part of quantum computing because the idea that one location can have multiple states at the same time is a very quantum idea. It is called quantum superpositioning of states, and it's sort of the defining feature of quantum physics, since you don't have any superpositioning of states, your system can be described by ordinary classical physics.

But you know what? If a qubit is used only that way, it's not nearly enough.

One way to understand why is to think of such multiple states running through a computer as providing parallelism in space. That is, instead of having to use two computers in parallel to process "0" and "1" inputs at the same time, you use just one computer with a the "0" and "1" bits superimposed on the same spot in space. Voila! You've saved all the space and power requirement of potentially many, many computers running in parallel, performing the same tasks on only one.

But think back to the example I gave earlier. The power for erasing the granite block came not from being parallel in space, but from being parallel in time. That is, each iteration of the eraser was "piled up" so that it took place during the same fragment of time, not just of space.

Time parallelism emerges only when you start considering the curious effect of entanglement, which plays havoc with ordinary concepts of time by providing effects that are "instantaneous" across distances in space. Relativity says very odd things about anything that works like that, since it makes space and time interchangeable.

So, the bottom line is this:

1. Any kind of quantum computer will be more efficient because it will use forms of parallelism that don't invoke the entropic costs of very large numbers of computers.

2. The most powerful designs for quantum computer are parallel in both space and time, a combination that allows pretty much unimaginable levels of computation to take place within quite tiny volumes of space-and-time.

PLEASE NOTE: Peter Shor most definitely participates in this group, and I rubbed his magic lamp earlier when I put an ampersand in front of his name.

So, if Professor Shor should show up (Poof!), I hereby abdicate any and all of what I just said to any and all of what Professor Shor may have to say. Scorn and ridicule are in fact fully welcome if appropriate, and if dished out will simply cause me to say "cool dude, thanks!"

-
I know close to nothing about quantum computing but after reading your explanation of why beating entropy/entropy generation is the best thing about quantum computing, I think: This is exactly why any quantum computer designed to beat/limit decoherence will have generate a ton more entropy in the universe (complement of the computer) and in doing so will result in excessive power consumption! – Sankaran Jan 25 '13 at 23:31
Even classically, a computation does not have to generate entropy. Look up reversible computation. Feynman wrote about it in his lectures on computation in the 80s. – user1631 Jan 26 '13 at 0:59
Sankaran, good point. The infrastructure to get a large quantum computer working could be non-trivial. Small ones (a few qubits) have been built, however, and they haven't been too bad on energy consumption. And user1631, yes, e.g. page 151 of Feynman Lectures on Computation, section 5.2, "Reversible Computation and the Thermodynamics of Computation." My recollection was that the classical form of reversible computing is very, very slow, e.g. p. 152 bottom quarter "...the energy loss [of computing] could be made as small as you want... as a rule, infinitesimally slowly." Fascinating stuff. – Terry Bollinger Jan 26 '13 at 3:57

What makes quantum computers powerful is not their speed, but that they are inherently massively parallel. If a machine has $n$ qubits of "working storage" then it can do up to $2^n$ parallel computations, analogous to a SIMD (single instruction multiple data) machine.

It's too soon to talk about power use because actual quantum computers haven't been able to go beyond a fairly small number of qubits.

-
A nicely succinct answer; I still have to go with the other one thanks to the rousing entropy discussion. Cheers! – B. Elliott Jan 26 '13 at 2:38
Researchers have known for a while that the way quantum computers work has very little to do with the concept of a massively parallel classical computer. The main reason why this intuition does not work is that when one measures a quantum computer (or any quantum system) one gets a random answer. Thus, to find the solution of a problem we may run $2^n$ "parallel" (in the sense of quantum superpositions) computations to test wether a huge number of inputs are solutions, and then try to pick a solution by measuring: due to the intrinsic randomness, we are most likely getting a useless outcome. – Juan Bermejo Vega Jan 26 '13 at 3:45
There are only a very limited number of problems, such as factoring, for which quantum computers gain an exponential advantage like this. A quadratic speedup (i.e. $n^2$ vs. $n$) is much more common. – Dan Stahlke Jan 26 '13 at 13:41
@Juan: I agree. I was just trying to keep the answer short for an unsophisticated OP. I've experimented with a simulation of Grover's algorithm. – Mike Dunlavey Jan 26 '13 at 14:37