Now, before the quantum discussion goes out of hand.
Here's what I know about quantum computing. Someone please correct me if I'm mistaken.
Whereas in classical computing you start from the ground up and essentially try to add more bit processors to compute information faster, in quantum computing you're essentially starting with the sum of all information and trying to devise a method to find the specific information you're looking for. In other words, classical computing is like starting with questions and trying to find the answers; quantum computing is like starting with ALL answers and trying to find the right question or set of questions which will give you the specific answer you're looking for.
A quantum computer is like starting with a library containing all books that have ever been written and will ever be written. A single qubit can contain an infinite amount of information. This in and of itself doesn't make for a useful library. How do you know where to find the book you're looking for? Moreover, when you begin to look (thus, you are trying to make calculated observations to find the book you want), the calculation you make on one piece of observed information changes the configuration of all the other information due to entanglement. In a way, I think of it as almost like a giant, entangled rubix cube. I would presume that adding more and more cubits allows you to process these calculated observations faster and allow you to retrieve the information you're looking for more quickly.
So, my guess is that a quantum computer with a single qubit could theoretically crack every key in the blockchain, but it would just take longer than if you had multiple qubits, and the more qubits you have, the faster it could be done.
I guess I'll give it a try. It's really not quite possible to explain quantum mechanics with classical analogies though, so just accept that reality is... different with QM. For example, working on a superposition of all return values of a function, what you call "ALL answers", is not the same as working on all return values of a classical function. You don't actually get all of them, they're just... partially there, for the lack of a better expression.
The information contained in a qubit is infinite because its state space is, for all we know, infinitely large. However, you cannot extract more than one bit of information when you read a qubit to get an actual answer! Also,
reading a qubit destroys its state! So the trick lies in
transformations done on the information in the system's quantum mechanical state space,
before you read out the answer.
In fact, it is very complicated and counter-intuitive to write algorithms for quantum computation devices. For all I know, we know about three useful algorithms. Granted, two of them are real breakthroughs: you can search an item in an unsorted list in sqrt(N) complexity (
yes, this should sound absolutely impossible if you think about it) and decompose numbers into their prime factors in polynomial complexity! The latter is called Shor's Algorithm.
With one qubit alone, you can do almost nothing. If you have one unitary transform on it, you get a great random bit generator, which can come in handy, but is absolutely useless to break Bitcoin. To actually break Bitcoin, you need Shor's Algorithm, and that means you need to operate on qubit-strings large enough to perform calculations with Bitcoin's keys! I don't know the exact requirements, but it's really really
really far off from where we stand. Remember people managed something like 4 qubits and factoring 15 or something.
Here's how a group did that:
http://arxiv.org/abs/0705.1398Note that this is nowhere near what a normal person imagines as a computer. We're talking enormous absurd setups creating interference patterns in cold vacuum chambers. To factor the number 15. Yes, it's 3*5, duh, and this implementation scales horribly.
It's really interesting to think about quantum computation, but don't panic too much about it. If someone shouts "heureka" and cracks Bitcoin-size keys, it might as well be a mathematician or whoever found something everyone else overlooked. If anything, be afraid of C++, which is a sloppy language in terms of security yet used for the main Bitcoin client. A simple bug in a compiler might turn out as fatal as one in the Bitcoin source, and I hope you remember how often Bitcoin already had dangerous problems of the kind. Billions of Bitcoins, baby! Been there, done that.
TL;DR:
DON'T PANIC!