Quantum Computing and Bitcoin

[tk808]

How will the arrival of quantum computing in the next years or decades effect bitcoin?

[exokk]

well I guess it takes a while - say 10 to 15 years - so that there will be any quantum computer available.
So who wants to predict the future of BTC UNTIL the first "arrival" of a quantum computer? maybe btc is long ago by then - overtaken by a new crypto

but I know. its all about speculation here.

Just want to add then: don't forget about DNA computer technology! it has about the same potential or an even higher one.

[exocytosis]

Commercial quantum computers have been in use for a while: http://www.forbes.com/sites/alexknapp/2011/10/31/lockheed-martin-installs-quantum-computer/

The NSA probably have quite a few of the more advanced ones.

[Bono]

Obligatory.

https://i.imgur.com/VjtG3.jpg

[doof]

great poster, can we get the high res somewhere?

[Bono]

great poster, can we get the high res somewhere?

That's the highest-quality I've seen. Grabbed the image URL right off this forum.

[tl121]

The poster looks nice. Unfortunately, the laws of physics do not mandate a minimum amount of energy to do computing.  It takes energy to flip a bit, but the energy can be reclaimed when the bit flips back.  Some smart people have shown how to make computing completely reversible, except for the cost of copying out the answer.

Ed Fredkin explained it to me this way,  "If computation took energy, how could the Universe compute its future?"

http://en.wikipedia.org/wiki/Reversible_computing

[lnternet]

Ed Fredkin explained it to me this way,  "If computation took energy, how could the Universe compute its future?"

Thanks for confusing the hell out of me

[tl121]

It confused me too. 

When I ran into the guy at the local airport where I fly gliders, I had just read this article from Scientific American:

http://web.eecs.umich.edu/~taustin/EECS598-HIC/public/Physical-Limits.pdf

[sgravina]

...  It takes energy to flip a bit, but the energy can be reclaimed when the bit flips back.  ...

No you can't.  Go ahead try it.

You can't decouple bits from the universe.  If you could then you wouldn't be able to see them.

Entropy increases.

[Kazimir]

Ed Fredkin explained it to me this way,  "If computation took energy, how could the Universe compute its future?"

The thing is, computation doesn't "take" energy. In fact, one could argue energy doesn't exist in the first place, it's just an abstract concept we introduced to describe some sort of equivalence between different physical phenomena. Thanks to Einstein, we can say that x amount of mass somehow 'equals' y amount of photons or z amount of heat. This equivalence is expressed in terms of energy, measured in Joules, but saying these things are all different forms of energy is mostly an abstraction.

Hence, computing the future doesn't "take" energy, but rather converts a few tiny physical objects or phenomena into others. Just like a combustion engine doesn't "take" energy but merely converts fuel into gases, heat and motion. Similarly, the universe will (verrrrrry slowly) convert itself to a homogenous mixture of low-energy-density gases and radiation, while continuously computing its own future.

[oprahwindfury]

Early quantum computers exist already, and they represent a very real threat not just to bitcoin, but to cryptography as we know it. By the time someone deploys a quantum computer against the bitcoin network it will be far too late to do anything about it from a system-wide standpoint. Individuals can send their coins to fresh addresses (ones with no spending transactions) since the public key is obfuscated by a few rounds of SHA256, but I believe there is an inverse SHA256 function for quantum computers as well.

To adequately defend against a quantum computer Bitcoin will have to move to a different type of cryptography all together. To present Bitcoin's algorithm as "unbreakable" through a tantalizing picture and a few witty scientific sounding phrases is misleading.

[Kazimir]

I believe there is an inverse SHA256 function for quantum computers as well.

Is there now, really? You do realize that this is mathematically impossible, right?

[Honeypot]

So about dem invincible bitcoins....

[Meni Rosenfeld]

Lots of confusion in this thread.

1. Schneier (quoted in the poster) was wrong. There is no known lower bound on the energy required for computation. As far as we know it is possible to build a computer that reverses SHA-256 without a significant energy consumption, and without any algorithm breakthrough.

2. It's possible an algorithm exists that can reverse SHA-256 without a new type of computer.

3. Quantum computers are more effective for reversing SHA-256 than classical computers, and Schneier's comment, even if it was correct, would not apply for them. Brute forcing on a QC scales like 2^128 which is a massive improvement. On the other hand, increasing the hash length would solve this particular problem. The real problem is that it is trivial for a QC to break ECDSA, so we may need to switch to Lamport signatures or something.

4. Lecture by Vitalik Buterin: http://www.youtube.com/watch?v=DkUpZkeqhF4&feature=youtu.be

[gmaxwell]

1. Schneier (quoted in the poster) was wrong. There is no known lower bound on the energy required for computation. As far as we know it is possible to build a computer that reverses SHA-256 without a significant energy consumption, and without any algorithm breakthrough.

He's referring to the lower bound for a non-reversible computer. Reversible computation has no known lower bound, no higher efficiency reversible computer yet exist yet. (As an aside, quantum computing requires reversible computing as well, so they're often talked about at the same time. But reversible computing is a subset, it may turn out that QC doesn't scale in practice due to yet unknown physical effects but highly efficient reversible computation works out just ducky).

[newguy05]

Dont worry guys, BFL will have a quantum miner for preorder soon, and of course it will ship 2nd quarter of 2014...guaranteed!

[bluemeanie1]

Lots of confusion in this thread.

1. Schneier (quoted in the poster) was wrong. There is no known lower bound on the energy required for computation. As far as we know it is possible to build a computer that reverses SHA-256 without a significant energy consumption, and without any algorithm breakthrough.

notice that Schneier seems to be the only one who posits what the other cryptographers only insinuate.

I've suggested elsewhere that it's quite possible that Scheier has some kind of special role in the promotion of popular concepts in cryptography.

It's not only possible that ECDSA has a back door, it's probable.

[niothor]

I wonder sometimes if that picture won't look in 200 years as a proof on how stupid humans were?
We claimed in the past many things and not just that "heavier that air" thing pops in my mind when i think about wrong predictions and statements.

[exocytosis]

Commercial quantum computers have been in use for a while: http://www.forbes.com/sites/alexknapp/2011/10/31/lockheed-martin-installs-quantum-computer/

Apparently, the NSA is currently building one: http://rt.com/usa/quantum-computer-nsa-encryption-100/