AFAIK cryptography is never "safe" it has many weaknesses.

1. the vault is only as secure as the key

in theory you never need to encrypt you private keys, just keep them in a place where others can not see it or access it.

2. all encryption can be broken with enough time AFAIK

3. to combat QC now, simply increase the encryption now to unrealistic heights. then you have time to reimplement the needed security once you understand the problem.

to find a private key from a public key would still probably take a while, my guess would be at best, a few days.

4. alternate chains will emerge and probably try to address these problems

and lets not forget the most important thing.

i have yet to see any real benchmark of QC doing real work, and i don't see that happening in the next 5 years.

thats not encryption, thats 2 factor verification, and it too is easily defeated

man in the middle attack
how do you handle it when you "lose" your security token?
phishing

With QC, far better things can be done than bitcoin.  In particular, it is possible to design quantum e-cash where transactions occur entirely offline and yet doublespending is prevented (i.e., no global blockchain that must be aware of all transactions).

http://dspace.mit.edu/handle/1721.1/52007

The spookiest thing about quantum (Einstien called it spooky) is that we do not know how it works. For all we know research may discover ways of accessing secure data via multidimensional exploits. It's no longer even out of the question to think that cause and effect is just a phenomena created by our feeble ability to perceive what's really going on.

I teach biology, and I often wonder if there is a quantum connection between wave colapse and the state we call "living". Right now I can't explain to my students the difference between a dead bird and a live bird.
You are going to hear a lot more about this in the future.

Heh... Richard Feynman, who was instrumental in developing quantum electrodynamics, once famously said that "if you think you understand quantum theory, you don't understand quantum theory".

I hope the same thing applies to quantum computing. 

You may be right. But even with our substantial knowledge of chemicals and electromagnetism we simply don't know how to get the "living state" going, or how it keeps going.
In physics a lot of discussion about unifying large and small scale theory is underway. But what about life? It seems to me that no theory of physics is complete without an explanation of the weirdest phenomena of all.

This was posted to slashdot about a von Neumann quantum computer:

http://www.technologyreview.com/computing/38495/?p1=A1

I would be more interested in what reversible computing may do for bitcoin.

Sorry to revive an old thread, but I feel I have to contribute, as I have studied Quantum computing, cryptography and Bitcoin all extensively.  I've been considering writing a series on the topic, but I never quite found time to do it.  The least I can do is respond to this thread.

First and foremost, QCs are useless for breaking a public-private keypair if they don't have the public key, and Bitcoin addresses are actually hashes of the public key. The attacker only sees the public key the first time the owner spends coins.  Therefore, if you use each address exactly once, by the time the attacker with the QC sees your public key, the coins have already been sent to another address with an unknown public key.   I don't know if this was an intentional security mechanism, but it adds a high degree of quantum resistance that may actually save the network.  (NOTE:  actually this isn't true for coinbase transactions which usually include the person's full public key, but there's no reason the miners can't switch to regular BTC addresses)

The QC would have to have a faster connection to your computer than your computer has with the rest of the network, then when you broadcast a tx, they have to crack your public key instantaneously and broadcast a replacement transaction to a significant number of nodes before the original transaction propagates.  This would be have to be a highly targeted attack -- still a stretch even if the person with the QC controls a significant number of your peer connections -- and still requires the QC to be fast enough to compute your private key nearly instantaneously.   This would only feasibly succeed if they control all your peer connections.  However, there's a variety of other attacks the person can execute if they control all of your peers...

The other angle is if the person with the QC also controls a significant portion of the global hashrate.  With a classical computer, they can only double spend against you (sometimes), but with a QC they can now also spend your coins.  If they can solve for your private key quickly after you broadcast a tx, there's a chance they can build a new branch of the chain fast enough that discards your transaction and includes one of their own.  However, if someone has enough computing power to do this, the network/community is going to have serious problems regardless of whether QCs are involved.

Secondly, hashing is effectively secure against QCs.  QCs wouldn't break the algorithm itself, but Grover's algorithm can be used on any pure-guessing problem to cut it's compute time down to sqrt of the original problem.  If you are trying to find someone's public key based on their bitcoin address (the hash of it), it will take a classical computer 2^256 guesses, but it will take the QC 2^128 guesses.  This is still wildly infeasible (for reference, the entire bitcoin network has produced about about 2^70 hashes total over the course of 2 years --- approximately 1 quadrillionth of the number of computations required to reverse your public key from your BTC address).

This would be most relevant for mining, but probably still safe for a while.  It takes your classical computer approximately 1^15 hashes on average to compute a new block (at current difficulty), so it would take about 100 million operations on a quantum computer -- but QCs are going to be dirt slow for a long time - it's possible that 100 million ops could take days or months on a QC.  My guess is, miners will have nothing to fear from QCs for a long time.

Thirdly The QCs can only break a public-private keypair if they have enough qubits.  However, number of qubits is going to be one of the bottlenecks of QC, the same way classical computers at one point maxed out at 4kB of RAM.  The QC needs more qubits if the encryption/signing key is longer.  This is likely to be a short term solution for internet cryptography -- use much longer keys.  For instance, switching from 256-bit ECDSA (like bitcoin uses) to 4096-bit ECDSA could add an extra decade to the security of the system (which would be more than enough time to work out alternatives).  Sure, it will take 1 minute to sign a message, but there's plenty of infrastructure that will continue to exist (both Bitcoin and otherwise). 

Fourthly there are asymmetric encryption algorithms that will continue to be secure even in the presence of QCs.  Granted, most asymmetric schemes are based on exactly the kinds of problems that QCs are good at solving (integer factorization, discrete-log), but not all of them.   There's a dozens of unused op-codes, which could be leveraged to switch the network to a quantum-resistant signature algorithm other than ECDSA.  Even the hashing algorithm can be switched.   Satoshi explicitly wanted this in the design, since there's no guarantee that today's encryption algorithms will be secure tomorrow.  He probably didn't have QCs in mind, specifically, but any algorithm could be broken by mathematicians any day.

In summary: The biggest saving grace for BTC is that it uses hashes of public keys instead of the keys themselves.  This, by itself, adds an extremely high degree of quantum-resistance to the BTC network.  Other places where QCs might cause disruption are only purely theoretical, and could take decades for the technology to develop to the level needed to actually execute the attacks.  So, if any of this is ever going to happen, we will see it coming, potentially decades in advance and can prepare accordingly.