[gjm11]

A quantum computer isn't really much like a super-powered classical computer. There are certain specific things it's amazingly good at (most notably, factorizing large integers), some other things it's quite good at (e.g., some kinds of search operation), and lots of things for which no one knows how to make quantum computers any faster than classical ones.

So, if you have a quantum computer, you're probably going to want to use it for breaking RSA or similar cryptography by factorizing large numbers.

There are (ordinary, non-quantum) algorithms for factorizing large-ish numbers. They work pretty well for numbers of modest size. But they don't scale well as the numbers get very large. Something like exp(log(n)^1/3 log(log(n))^2/3) to factorize a number near to n. Or, in terms of the number of bits, something like exp(b^1/3 log(b)^2/3).

So this works fine for numbers up to, let's say, 200 bits on a single machine or 1000 bits for a team with a substantial network. (Note: all numbers here are kinda made up but of the right order of magnitude.)

With a quantum computer, you can factorize a b-bit number with something like 2b qubits, b^3 quantum gates, and a runtime that scales more manageably with b.

So there's not much point in using a quantum computer until the number of qubits it has gets large enough to use for factorizing numbers bigger than you can do on your PC. Which means somewhere on the order of 100 qubits. As the number goes up, the advantage of the quantum computer over the classical computer increases. The transition from "slower than your PC" to "faster than any classical computer that will ever be built" takes place over a fairly small range of qubit-count.

Down with much smaller numbers of qubits, though, the quantum computer can maybe manage to find the factors of, say, 15. Which is, shall we say, quite a lot less than the computer on your desktop can do.

[ConceptJunkie]

I'm confused, you say you could factor a b-bit number with "something like 2b qubits", but then go on to say you'd only need 100 qubits to factor bigger numbers than a PC.

Factoring a 50-bit number is not that big a deal. I used my Python command-line calculator program (all the hard stuff is done by mpmath, pyprimes and other open-source code I didn't write) to factor a 50-bit number just now:

c:\>rpn -t 2 50 7 + factor

[ 37, 30429727211963 ]

29.569 seconds

I'm sure Mathematica is much faster.

It seems to me several hundred cubits would be necessary to outperform classical algorithms on commodity hardware.

[archgoon]

Why on earth would it take 30 seconds to factor a random 50 bit number? You just check all numbers between 2 and 2^25 (about 32 million). This should take less then a second, maybe two in python.

The parent poster likely was thinking 100 bit number (200 qubits), which, while technically tractable, is quite a bit of computing power (assuming that we don't end up with huge coefficients with quantum computers).

[gjm11]

As I said, all the concrete numbers in what I wrote are crude order-of-magnitude approximations. The original question was whether a quantum computer with just a few qubits would be comparable in power to a conventional desktop computer; the answer is a clear no whether the point at which quantum computers become genuinely useful is at (say) 100 or 1000 qubits.