Bitcoin Forum

I'm intrigued by the possibility of a quantum Bitcoin mining platform. Quantum computers have already been theorized to be able to break the underlying mathematics behind hashing algorithms (see Shor's Algorithm (http://en.wikipedia.org/wiki/Shor%27s_algorithm).) Could quantum computers mine for Bitcoins at a much higher rate than what is achievable today?

Related information:
https://bitcointalk.org/index.php?topic=26788.0
https://bitcointalk.org/index.php?topic=191.msg1585#msg1585

Shor's Algorithm applies to prime factorization, which SHA256 doesn't use.

What you're looking for to crack SHA256 is Grover's Algorithm (http://en.wikipedia.org/wiki/Grover%27s_algorithm). Basically under classical models of computation the optimal way to find a matching hash is to simply search through the entire space yielding O(n). Under Quantum Computing the optimal time is O(n^0.5), which means effectively you have halved the key-length.

For SHA256, it effectively becomes SHA128 to a Quantum computer. Now the question remains, can a Quantum search for SHA128 faster than a classical computer search through SHA256?

With our current technology and for the foreseeable future, we still cannot build a Quantum computer that can yet begin to tackle this problem, let alone solve it in a time within our lifespan.

Thus SHA256 is considered "secure enough" for now.

I see. So it is still unknown whether SHA-128 is BQP...

What's the point when you get knocked back to 10 minutes per block like every other jackass on the block?

True. But it would still give you a lot of hashing power=money. Just wondering whether there would be a quantum algorithm to compute a very large number of hashes every second.

Hopefully if Bitcoin is still around when a new computing technology is emerging that truly threatens the security of the SHA256 hashing we do now, we can rally enough support to get a mainline fork like P2SH to switch to a more secured hashing system for future blocks.  The hashing algorithm CAN be changed, even in the main Bitcoin chain, if the devs and the miners can all agree that the change is necessary for the currency to continue.

If a quantum computer can fullfill the function of bitcoin mining, and accomplishes it far more rapidly than current technology, would this not impact the dynamics of how bitcoin operates in terms of economics?

There are a few academic papers in circulation that point to a possible early prototype of a quantum computer within 2020s to 2030s.  Despite the pace of our understanding picking up in this type of computing, there is still a long way to go before they become commercialized to the general public.

So far we just reached the 22 nm node for integrated circuits, it is predicted by 2015 we will hit 15 nm. Quantum Tunneling is predicted to be an issue below this node, some academicians this year proved otherwise, indicating Ohm's law still functions below 15 nm. Maybe the design/approach to computing might be rethought as we shrink further before reaching quantum computers, such as going from an incandescent light bulb to a LED bulb.

I'm certainly not worried about this happening unexpectedly.  The bitcoin community is very involved in technology, and I'm sure if something appeared on the horizon as a game-changer, the forums would light up much faster than that technology became available.  If the technology improves steadily and we just see continual hash rate growth, it's no issue.  The only time I would see a "threat" is if some new technology appears that is hard to obtain, yet able to either break sha256 or at the very least trivialize the current brute forcing of it.  Quantum computing has often been mentioned as a potential threat in this way, though I don't know if there is much validity in that concern.

If SHA256 is suddenly useless then bitcoin will be probably the minor problem: the whole world, banks etcetc use SHA

Never considered this. Of all the ways you could get rich by cracking SHA encryption, bitcoin's reward:work ratio is relatively low.

But if you hack a bank if you can crack SHA, the authorities will probably come for you.
If you can hash way faster than other people, it's perfectly legal.

Why is the bank always the first thing people think of. No imagination.  :P

http://www.dwavesys.com/en/dw_homepage.html

Price tag of only $10,000,000 and that's probably old tech now since it's commercially available. Bitcoin is already vulnerable and has been since it was created.

Consumer products will probably be out in 2020.

Ahh, good old Canadian Innovation ;) I applaud DWave for their innovation, though it should be mentioned that much of academia has concerns that DWave's Adiabatic Quantum Tech isn't "Real" Quantum Computing... How one would determine that I'm not sure lol :)

Also the question is once again (as stated earlier in the thread) can this machine hash any faster than a GPU or FPGA? Quantum computers are not the be-all end-all of computing, they thrive on very specific types of problem spaces. If the problem isn't one that can benefit from the unique properties of Quantum Computing, then it won't necessarily be any faster. (hell in many cases it will be SLOWER) ;)

You can determine if it is a "real" quantum computer if there is entanglement involved. There's a certain experiment for testing that but I can't recall its name.


Very true. However certain NP problems (problems not computationally feasible to solve on a classical computer) might just be BQP (solvable in polynomial time on a quantum computer.) The question is whether SHA-256 (or SHA-128) is NP-complete: if so, it is probably not BQP.

*If* BQP = P then classical computers / Turing machines can run Grover's quadratic (square root time) search. After a few hundred thousand mined the hardness catches up and process is slow again. If additionally, GP constant time search [ http://arxiv.org/abs/1303.0371 ] is in BQP then all remaining coins are mined/minted near instantaneously (no SHA hardness is sufficient to slow the search). Further, double spending is possible if one can search in constant time.

QKD is a possible solution to keeping transaction integrity --- http://en.wikipedia.org/wiki/Quantum_key_distribution

No matter how 'unlikely' that all might sound by running standard software, just keep in mind that strictly speaking no theorems (including Grover's optimality for linear QC) would be violated.

Why would you spend 100 billion dollars to crack bitcoin?  If you took over 100% of the hashrate BTC would become worthless.  If you spent that much on a computer there would be better things to use it for.

No you wouldn't. It would be far cheaper to throw 28nm ASICs at it.  In fact, it would be cheaper to throw 5nm ASICs at it, since the R&D for a 5nm chip would be less then the R&D for a quantum computer.

If you had the money for a quantum computer, you could fab a 5nm or even 1nm chip in a year.

DWave is a joke.  It can't solve BQP problems, which is the entire point of what's normally considered a "Quantum Computer"

Not.

Eventually if it does become a problem, you do something against it, same thing happens with pirating, the gov will never stop pirating, nor will quantum computers or anything of the sorts stop bitcoin  ;)

AFAIK the most advanced quantum computer today can only add 2 digits where the sum is 7 or lesser....

It wont be like one fine day you would see physicists come out and announce "Today we have built a quantum computer advanced enough to do double sha256 and mine bitcoins @ 1 gazilion PH/s" .... Im pretty sure before then, quantum computing would become common in day to day life for simpler tasks... and the algo would have evolved taking that into account.

The risk, if there ever is one, is not from the mining aspect but rather from quantum computer being used to crack private keys, but im certain devs will adapt to stronger key algo by then.

That's what I'm talking about, it keeps adapting with the new technology, no worries  ;)

This technology is still a long way off.

Amen to that.

I agree, I think the forums would light up a great deal.  I think if the quantum computer does become available, most of the bitcoins would all be mined by then if not all.  If a new cryptocurrency (other than the ones available) were to become popular, it may need to consider Quantum computing whereas bitcoin doesn't.

Why would you think a quantum computer would be able to solve SHA256 any faster then a regular computer?  The problem is that a quantum computer could potentially compute the private keys of other wallets.