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