Bitcoin Forum

http://www.scientificamerican.com/article.cfm?id=d-waves-quantum-computer-courts-controversy

These new quantum computers change the game in the IT world, and certainly might effect some of the assumptions behind Bitcoin's security.  The question that needs to be asked: how quickly can blocks be 'mined' with such a computer?


Butterfly Labs better take notice.

earlier threads on Bitcoin and quantum computing:

https://bitcointalk.org/index.php?topic=133425.0

https://bitcointalk.org/index.php?topic=78693.0

https://news.ycombinator.com/item?id=2602570

http://cr.yp.to/hash/collisioncost-20090823.pdf

The last thing somebody is going to do with a quantum computer is mess with bitcoin. I can think of almost infinite things they should be doing first like bioinformatics and physics calculations for new trillion dollar alternative power methods.

Bruce Schneier has written about QC numerous times on how useless it is for practical cryptography, just look up quantum computing on his blog, go through all the posts, deflate the hype

These quantum computers do not actually do what you think they do. they aren't conventional function computers but probability solvers for formations of solutions. they are very epotomy of asics but not for definitive maths.

they do not do standard mathematics and cannot be switched over. they short cut high difficulty pattern and lowest energy state problems in a noisy quantum way. they are not good at high grade parallel math. they effectively act like little distillery pots for patterns or lowest energy configurations of a problem, like folding or crystal lattice problems.

http://www.scientificamerican.com/article.cfm?id=d-waves-quantum-computer-courts-controversy&page=5

I feel like we talk about this every few months.

initially though, consider that the 'experts' claimed that Quantum Computing had no effect on hashing algorithms.

EVERYBODY PANIC

There have been loads of threads on this subject.

Bottom line is that there is no need to worry about a QC threat to Bitcoin in this decade or the next (or longer :-)

a) The capabilities of any QC that can be built today with one that can brute force a private key is like comparing Red Baron's bi-plane with a stealth fighter.

b) All fiat transactions in financial systems done over the internet, indeed, internet security itself would also be at risk, not just Bitcoin.

c) Different hashing algorithms can be used to replace SHA-256 that are much more resistant to QC problem solving.

Interesting paper.

According to it, preimage searches can be faster on quantum computers than on classic computers.  BTC mining can be expressed as preimage search, so the extended Grovers algorithm could be applied.  The paper sais it is not clear what search complexity is required to reach the tip-over point at which a quantum computer is more efficient.  Therefore it isnt clear on which side BTC sits.  It may or may not be more efficient.

If BTC mining was more efficient on quantum computers, it wouldnt necessarily be the end of BTC.  As long as the length of SHA2 hashes permit, quantum mining rigs will be dealt with by difficulty adjustments.  Just like GPU, FPGA, ASIC technology each is so much more efficient than the previous generations.  The network has compensated for all of them and is still running as designed.

There is a maximum possible difficulty though.  Only when the network hashing power gets beyond that point, BTC mining is broken.  Until then: business as usual.

Other areas of BTC (such as the public key crypto) are probably much more vulnerable to quantum computers than the mining process.

And finally, many scientists doubt that the D-wave is actually a quantum computer in the first place.  It may be a quantum computer simulator but does not solve any problems faster then a traditional large computer so far. 

To me if there is a computer powerful enough to attack bitcoin then it is powerful enough to attack traditional banking institutions as well.  All monetary systems would be at risk not just bitcoin.

There'd be a lot more things in danger, too.

Indeed all that I read about the D-wave device was that it can outperform classical computers for certain optimisation problems, but it is not a "general purpose quantum computer" which could either run Grover's algorithm for sqrt(N) searches in unsorted lists, or Shor's algorithm for integer factoring and discrete logarithms.  Note that in my opinion, mining / SHA-2 is not the crucial point if a quantum computer is ever dangerous to bitcoin.  Instead it is the public key cryptography and ECDSA (although I don't know how susceptible ECDSA is to quantum computing).

If / when quantum computers are available and have enough bits to run algorithms to brute force SHA256, to maintain it's current security level Bitcoin would have to implement SHA512

http://en.wikipedia.org/wiki/Key_size#Effect_of_quantum_computing_attacks_on_key_strength


So 512 bits of security in a classical computer would give 256 bits of security for a quantum computer.

The question is, will only the bad guys have quantum computers? What will be the computational power of personal q.c. versus large q.c.? If reasonable quantum computing power is available to everyone, nothing will change - people will use small q.c. for encryption and the NSA will have big ones that take trillions of years to brute force.

Only if normal people are stuck with classical computers, and the bad guys have q.c. then we're fucked.

Lol, I'm actually tempted to put this statement in my sig. Funny shit.

Prediction: The next Pirateat40 will be advertising a quantum miner. He'll make a fortune and delivery will be pending for years.