Bitcoin Forum

http://www.naturalnews.com/040859_Skynet_quantum_computing_D-Wave_Systems.html

So, does that mean Bitcoin is soon to become irrelevant?

No.

Yes.

it is both doomed and not doomed at the same time.

we need a quantum computer to solve this

also a bit more on yes or no cases

+1
I'm doing a Schrodinger's cat
https://i.imgur.com/EHpnY.gif

Here is a video interview with D-Wave Chief Scientist, Eric Ladizinsky
http://www.youtube.com/watch?v=fArXhQBLDWE

Quantum Journey

Try actually reading this article.

My eyes glazed over 1/3 of the way through from all the FUD.

Author has a wild imagination.

I do agree that at some point, the author did become a bit delusional and started writing FUD.

rofl ;D

It is like one of those Yin-Yang kind of things, but not exactly.

"According to Google and NASA, this computer will be tasked with research in the realm of "machine learning"

Oh no, they are going to use this computer, In Space?

>natural news
top lel

Sounds legit.  ;) :P

Anyone?

First, how about read the actual original article instead of someone's interpretation of it: http://www.nature.com/news/google-and-nasa-snap-up-quantum-computer-1.12999

Second, the article notes that any problem designed for this computer can still be done faster on existing classical computing resources.

Third, quantum has been discussed quite a bit on here before. I'll leave OP to search, but IIRC, bitcoin is quantum-resistant in that if practical and powerful quantum computers existed, the bit-space for the crypto problems bitcoin uses would be reduced, but would still be huge.

 A multi million dollar machine set to get bitcoins doesn't make a lot of sense.

Tinfoil hat DETECTED

I want to pre-order USB powered Quavalon mining rig that do 1PH/s  :D

and, EVERYBODY PANIC

Yes, this is the correct answer.

Qubit Quantum Computer = Qubitcoin.

Wrong, there are infinite states, that's what make it that useful

Wrong, number of states is a very big but finite number.

Wrong (http://en.wikipedia.org/wiki/Quantum_superposition)

Wrong (http://en.wikipedia.org/wiki/God)

Wrong (http://en.wikipedia.org/wiki/Flying_Spaghetti_Monster)

Touché

Have you seen Hash Grease? It uses quantum technology from NASA.
https://bitcointalk.org/index.php?topic=240760

Scott Aaronson has commented numerous times on the so-called quantum computer produced by D-Wave.  Here is an excerpt from his blog (full article available at http://www.scottaaronson.com/blog/?p=954):

"The second question is one that I’ve encountered many times on the blogosphere: who cares how D-Wave’s system works, and whether it does or doesn’t exploit quantum coherence, as long as it solves practical problems faster?  Sure, maybe what D-Wave is building is really a series of interesting, useful, but still basically “classical” annealing devices.  Maybe the word “quantum” is functioning here as the stone in a stone soup: attracting money, interest, and talented people to build something that, while neat, ultimately doesn’t much depend on quantum mechanics at all.  As long as D-Wave’s (literal!) black box solves the problem instances in such-and-such amount of time, why does it matter what’s inside?"

"To see the obtuseness of this question, consider a simple thought experiment: suppose D-Wave were marketing a classical, special-purpose, $10-million computer designed to perform simulated annealing, for 90-bit Ising spin glass problems with a certain fixed topology, somewhat better than an off-the-shelf computing cluster.  Would there be even 5% of the public interest that there is now?  I think D-Wave itself would be the first to admit the answer is no."

A brief summary is that the D-Wave "quantum computer" referenced by the OP may not even be a quantum computer and will certainly not be a threat to Bitcoin without further major scientific breakthroughs.

Here is Scott's Bio from his latest book, "Quantum Computing since Democritus," which is highly recommended for those interested in the subject:

Scott Aaronson is an Associate Professor of Electrical Engineering and Computer Science at the Massachusetts Institute of Technology. Considered one of the top quantum complexity theorists in the world, he is well known both for his research in quantum computing and computational complexity theory, and for his widely read blog Shtetl-Optimized. Professor Aaronson also created Complexity Zoo, an online encyclopedia of computational complexity theory, and has written popular articles for Scientific American and The New York Times. His research and popular writing have earned him numerous awards, including the United States Presidential Early Career Award for Scientists and Engineers and the Alan T. Waterman Award.

Even if D-WAVE could do SHA256 the best algorithm for brute forcing it using quantum computers in 2^(n/2) compared with 2^n for classical computers.

By implementing SHA512, bitcoins would be just as secure from quantum computers as they are from classical computers.

See for reference:

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

Absolutely, delivery is scheduled for October.  ;D

Well, the article doesn't quite say that  (and in fact it's thought this type of device, more evolved, may be able to yield results vastly faster than any conventional computer, on large optimization problems).

But it does amusingly present a superposition of answers, both implying -- and not implying! -- that this particular device may be faster than conventional computers at what it does:


What would matter to us is whether these annealing devices can be used for universal quantum computing. Surprisingly, there are claims that this should be possible, though the number of qubits required would be greater than with a gate-based system, and there might be sacrifices in speed as well.

Regardless, there are enough reasonable paths to true quantum computing that in a few years it seems we will want to upgrade at least the signing protocol, or stop the convenient practice of reusing bitcoin addresses after the first spend.

The latter option would bring an end to static vanity, donation, and green addresses (though the last two could be replaced with other, dynamic mechanisms if needed).

The threat of Quantum computers isn't breaking SHA256 (or any hashing algorithm) it is in theory performing a faster than brute force attack on public key cryptography such as ECDSA used by Bitcoin but the system in the OP isn't a threat to Bitcoin for a variety of reasons.

By the time QC gets used for cryptocracking or mining, Bitcoin will be using entanglement cryptography.

here is a defacto sticky on QC's

Quickly sell all your bitcoins! Oh wait nevermind you guys are already working on that. Tnx for cheap coins.

No it's not.

this is a good video, thanks for posting.

D-Wave also has a fairly good introductory tutorial on Quantum Computing for programmers:

http://www.dwavesys.com/en/dev-tutorial-intro.html

Quantum cryptography. Problem solved

I wouldn't worry if it presented a risk, developers could patch it up with something more resistant to quantum computers.

The search space for private keys via ECDSA is reduced from 2^128 to 2^64 using Shor's algorithm if I recall correctly, so not really.

No, but I am.  Send your share bids to the address in my profile.

Due to the Heisenberg uncertainty principle, the more we check on the delivery date the harder it will be to lock it down.  Right now delivery will be at some point in the future and I don't want to risk anything by trying to be more precise.

Unless D-Wave has changed their direction in the last 5 years (the last time I checked in with their progress), nothing they are doing actually constitutes a "real quantum computer".  When I say "real," I mean one of those quantum computers that actually leverages quantum interference to solve problems, which could be used to break not just Bitcoin cryptography, but all the cryptography on which the internet is based.  If this was a real problem, you can be sure that alarm bells would be ringing around the world, and for much more than just Bitcoin. 

Real quantum computers aren't just faster -- they solve problems differently.  Shor's algorithm takes integer factorization from O(e^cuberoot(N)) on a classical computer to O(N²) on a quantum computer.  This isn't just faster -- this makes a whole class of essentially-unsolvable problems, solvable (including the discrete logarithm problem on which Bitcoin crypto is based). 

Yes, you can get a speedup on pure-guessing problems using Grover's algorithm -- from O(2^N) to O(2^N/2).  That's a unique capability that QCs can exploit, but the least interesting in terms of breaking cryptosystems.  Most crypto systems use key sizes big enough that even if you halved the keysize, it would still be secure.  And the defense is to just double your keysizes, once, and the problem goes away.  But not with Shor's algorithm -- the whole class of problems is compromised.

D-Wave has always been a joke in the world of QCs.  What they are doing is cool, and they may be developing technology that is somewhat related to QCs, but they shouldn't be using the phrase "Quantum Computing" in their product name, because that terms is reserved for a whole new class of computing systems, not classical computers that use quantum bits to do things classically faster.

etotheipi, an article I just ran into that reflects your comments here : http://www.scottaaronson.com/blog/?p=1400

It's true that when you cross over into the commercial arena, you typically encounter disjoints between promises and reality.  Whenever you get enough public interest in some scientific idea, eg. Quantum Computing, someone will claim to be delivering it despite it being impossible.

There are projects being advertised right here in this forum, that claim even to be Open Source, that don't even come close to living up to the claims made about it.


sounds a lot like a project I know...

Quantum computing is possible

dooomed, dump all your btc now

:trlf:

Dump to me @1$ each, don't worry it's a good investment the price of $ will rise by 1% psst!  ::)

I'd take them at $20 each
Beware they may contain viruses too

maybe  ;D

Yes, Bitcoin is doomed so give me all your coins and run away like a little school girl that had her first period in a white skirt at the school cafeteria.

So detailed  ;)

Edits In: Question Authority wants to be a little girl
(Moot)

+1
Best geek joke of the day.
Then again quantum computing lends itself to easy geek jokes..

Nice quote from Umesh Vazirani, a professor at UC Berkeley on the D-Wave hardware:

"even if it turns out to be a true quantum computer, and even if it can be scaled to thousands of qubits, would likely not be more powerful than a cell phone"

Great skepticism out there as to whether D-Wave is doing anything truly Quantum or, rather, is just building dedicated hardware to create approximate, not exact (i.e. useless for Crypto) solutions to complex problems.

Nothing D-Wave is doing will have any effect of the strength of cryptography they are definitely NOT building general purpose quantum computers or quantum computers that can break high grade cryptography algorithms.

No.

By now, there are so many threads on quantum computers that to have missed them all is simply impossible.  Just typing the word "quantum" into the search box gives 28 pages of results.

We need a time out corner.

Quantum computing = the "hydrogen-powered car" of computer research.

Always "just around the corner", lots of hype and FUD, but never quite moving beyond a technical curiosity. The only way quantum computing could generate more baseless hype is if someone ports the litecoin client to run on a D-Wave box  :)

Quantum computing will be big for many things, but cracking bitcoin keys - or running Windows 8 -  are probably not two of them.

last part +1

If the being can run on normal conditions... The being requires helium (close to zero K) to stablize the operation. Of the being can be operated with nitrogen (L), then the bitcoin may be doomed.

Well in theory a true general purpose quantum computer with a massive number of quibits (say 30,000+) would be very useful for breaking all types of public key cryptographic including ECDSA used by Bitcoin.

The good news is like you said it is one of those things (economical fusion power being another) which has been "so close" for decades now.  The other thing is that DWAVE computer isn't a general purpose quantum computer so while the threat exists it is still academical at this point.

This article almost seemed serious, until I saw the words: "[Raymond] Kurzweil is <...> the leader of the transhumanist cult -- a group of insane technology worshippers who believe they will upload their minds into quantum computers and 'merge with the machines,' achieving some weird shadow of immortality (in the same way, I suppose, that a photograph of you makes you 'immortal.')"

Then I stopped reading.

I can bet, that at least some of the technology used to write that article, was invented by the genius Raymond Kurzweil. The author (Mike Adams) is a disgusting excuse of a human being.

It is both sad and scary, that such people as the Mike Adams exist. It means, that a war between neo-Luddites and technically-savvy people is inevitable.

Schroedinger's Bitcoin?

Come on, polio - just try to infect my child. I have HERBS, bitch.

just like cold fusion.

Looks like it might be closer than you all think.

http://www.cbc.ca/m/touch/technology/story/1.2426986

More likely to help improve their search and thus their targeted advertising through learning from your past searches etc. Google is becoming self aware in other words.

This also has applications for their cars that can drive themselves etc.

When they announced the great hadron collider, there was a group of idiots writing articles how it's gonna open a portal to another dimension or suck Earth into a black hole.
This is exactly the same level of journalism.

what if we actually did get sucked into an alternate universe but we didn't realize, and the people at power now are the ones behind the LHC and they trapped us in a matrix like scheme, and satoshi is also one of the guys from the original universe, but he has gone rogue.

and now they're trying to make really powerful agents to stop the bitcoin threath.

Wrong (https://encrypted-tbn3.gstatic.com/images?q=tbn:ANd9GcSO54Xz6fiER98aB3fryKt6ysvK0kVeHc7RytkF1hbhPpkGFMBN)

Bitcoin isn't doomed.

Quantum computers have the potential to be hashing monsters in the near term should anyone come up with a Quantum Miner to crunch SHA256 algos, but the algorithm that protects our keys is Elliptic Curve cryptography based which is many orders or magnitude higher.

That's not to say it's impossible for Quantum Computers to catch up.

But even if this was the case, the moment any real risk came up we always have the option of having Bitcoin's equivalent of a constitutional amendment, a hard fork. Provided it was properly managed, scheduled and agreed on there is no reason a stronger encryption function couldn't be implemented onto the blockchain.

Think about the transition from IPV4 to IPV6 - it didn't stop the old addresses from working, it just added the extra functionality on top and anyone who wanted to take advantage of the new functionality simply opts into it.

Much the same for Bitcoin, there just has to be consensus.

So quit worrying - Bitcoin is community run and can evolve to handle anything that gets thrown at it.  8)

You have this exactly backwards.   Quantum computers are  not particularly effective at breaking symetric encryption algorithms and hashing algorithms.   

The massive potential in encryption cracking comes from Shor's algorithm which only works on public key (asymmetric) encryption algorithms like ECDSA.   That being said the qubits requires to break 256 bit key is ~30,000 and the largest general purpose quantum computer to date is 7 qubits.

Still as you point out Bitcoin can be extended to provide quantum resistant address schemes however it also provides immediate protection in another way.  If you don't foolishly reuse an address the pubkey is unknown to an attacker until funds are spent (payments are to the pubkeyhash) and Shor's algorithm is only possible against private keys where the attacker knows the pubkey.

Sorry , but is that a true and working quantum computer?

Then only the chosen one can save us, or someone with a red pill  ;)

Yes it was able to factor 21 into 7 & 3.  One capable of breaking a 256 bit ECDSA key would need to be 4000x to 5000x larger and there has been essentially no progress in building even modestly larger QC (i.e. one that could break an already obsolete 32 bit key in a reasonable amount of time) in the last decade.

What you're saying is that nothing available in the present or near future can work against Bitcoin. If something capable were developed in the distant future we would simply fork Bitcoin with an improvement that defeats it. This thread should be finished now.

Excellent! At least I know that in another timeline I did not don a pink tutu in Las Vegas, albeit I pity them souls that were forced to listen to the Bitcoin for Goats presentation.

~TMIBTCITW

PS: This thread should be finished now.

I found the paper in May that put two different qubit chips up against software and hardware solvers in a very specific class of problem, and the results were that with a problem that is most suitable for the chip it found a solution in half a second, several thousand times faster than the best traditional methods.

There were a lot of ifs/buts and exceptions however the V5 and V6 chips tested, when given the right kind of problem, were indeed able to solve it (it was an annealing problem) in a grand flash.

A clear eyed summary on that May paper, and the D-Wave devices is here: http://spectrum.ieee.org/computing/hardware/dwaves-year-of-computing-dangerously

I've no doubt that quantum computing is going to be an arms race, and it will start to solve in parallel more problems over time. Whether that includes searching for keys or cryptography I've no idea but if it does you CAN BET THAT NSA WILL NOT TELL US ABOUT IT.

That's a bit scary ! :/

I will bring my linked blog into play here on my Theory of Everything.

Quantum superposition is due to the emergent derivation that matter is relative to itself (http://unheresy.com/The%20Universe.html#Matter_as_a_continuum).

When we measure something, i.e. form coherence, it is only valid in our local coherent delusion because (http://unheresy.com/The%20Universe.html#Edge_of_the_universe) it is always aliasing error on the universal scale.

Traditional CMOS electronics constrain quantum effects to local measurement components, i.e. transistors so the potential increased global degrees-of-freedom due to entanglement across the entire circuit are destroyed, i.e. made coherent by quantizing each logic gate locally within the circuit. In other words, pre-mature coherence.

A black hole is superpositioned matter. If we could superposition ourselves, we wouldn't be perceivable (not coherent) in a local reality.

Entanglement doesn't mean two quantum particles are joined across great distance, rather that can be an aliasing error effect that we perceive in the local 3D context. It means that quantum particles (actually waves) can interact on universal global scale (i.e. distance is irrelevant). You see in the superpositioned universe, there are infinite dimensions thus 3D is just a local delusion. When I use the terms local and global I am not referring to distance in 3D, rather to limited versus unlimited perspectives (aka samples or measurements). In superpositioned matter there are infinite perspectives thus no one single coherent realization and thus the black hole-- maximally disordered ether. Now you know what anti-matter is.

This isn't hand waving. This is the only description of the universe that can be logically globally coherent. I discussed these concepts in another thread (https://bitcointalk.org/index.php?topic=342848.msg3789199#msg3789199) and another one (https://bitcointalk.org/index.php?topic=355212.msg3852724#msg3852724).

So the challenge of quantum computing is to build a circuit that allows computation to proceed in the maximally disordered ether, while quantizing only the result of the computation.

The arguable criticism of the D-Wave system is it may not be enabling entanglement between the qubits, i.e. they are just akin to supercooled transistors which locally have two (finite) superpositioned states each.

Edit: many details omitted for brevity.

I'd like to see papers about that

One thing I have pointed out in the past (and likely will need to continue to point out for a very long time ) is that DWAVE's system implements (or it stated to implement there is some controversy over exact what is happening) quantum annealing algorithm which while it does (or may) have some quantum properties is not the same thing as a general purpose quantum computer.

To attack public encryption requires a general purpose quantum computer (QPQC) capable of implementing Shor's algorithm (or one built to only implement ONLY Shor's algorithm, a quantum "ASIC" if you will).  Even if DWAVE's computer was a quadrillion qubits it would be absolutely useless for attacking public encryption.  

The global recognition for successfully factoring larger numbers using a GPQC and Shor's algorithm is a pretty big deal.  To date nobody publicly has shown the ability to factor numbers larger than 143 (an 8 bit number).  Even factoring 32 bit numbers at commercially viable speeds would probably mean we are decades away from being able to break 256 bit ECC keys but we aren't even close to that.  While QC is powerful in theory, practical progress has also been agonizingly slow:

2001
First successful demonstration of Shor's algorithm.
Computer size:  7 qubits
Number factored: 15 (into the factors 5 & 3)
Equivelent RSA keysize: 4 bit

2011
First successful factorization of a three digit number (143)
Computer size:  8 qubits (actually 4 bits using an iterative process)
Number factored: 143 (into the factors 11 & 13)
Equivelent RSA keysize: 8 bit

So the bit strength of "encryption" (I use this term loosely because one could crack 8 bit "encryption" with paper and pencil) that can be broken using QC has gone from 4 bit to 8 bit after a decade of research.  Even if this can scale, at the current growth rate breaking Bitcoin would be more than a lifetime away.  ECDSA is a little different than RSA in that it doesn't involve factoring large numbers and instead uses the properties of elliptical curves but both can be broken using Shor's algorithm.  In general ECC requires smaller keys than RSA for an equivelent level of security.  To achieve 128 bit key strength (which is considered beyond brute force for classical computing) using ECDSA requires 256 bits, but using RSA requires 3,072 bits. Bitcoin could use RSA and be just as secure however transactions would be up 12x as large.  

Still both RSA and ECC in theory can be broken faster than what is possible with classical computing by using a large enough (and fast enough) quantum computer implementing Shor's algorithm. I have only found one paper to date which compares the qubit cost of implementing Shor's algorithm against both RSA & ECC.

http://arxiv.org/pdf/quantph/0301141.pdf  I emphasis of relevant portions is by me.  

So we are looking at a general purpose quantum computer which needs at least 1,800 logical qubits.  Nobody (AFAIK) has even done research on the amount of error correction required for a commercial general purpose quantum computer (because none exists) but lets take the authors estimate of "dozens of physical qubits per logical qubit" and use 24x as a low end.   This would mean (1,800 * 24) a system with 43,200 or more physical qubits.  To put that into perspective the largest (AFAIK please correct me if you find a larger example) general purpose quantum computer capable of implementing Shor's algorithm is ... 7 qubits so we aren't eve in striking range yet.

Still QC "may" may break 256 bit ECDSA within our lifetime, so should be looking to future solutions.  There are a couple things which can be done to improve the quantum security of the Bitcoin network.  The simplest change would be to implement a new address type which uses a larger ECC curve.  While larger ECDSA keys can sitll be broken they do increase the qubit requirements, moving to 512 bit keys doubles the required qubits and 1,024 will quadruple them.  If GPQC proves viable this would buy the network some time for a longer term solution.  I don't even know if 1,024 bit ECC is supported by major libraries, outside of quantum computing there is little need for 1,024 bit ECC because even 256 bit ECC is considered beyond brute force. 

A longer term and more complex solution would be moving to an address scheme based on a post-quantum algorithms (http://en.wikipedia.org/wiki/Post-quantum_cryptography).  These systems generally have no wide spread deployment so there may be unknown security issues so I am not advocating a change anytime soon just pointing out there are algorithms which can be used to protect the network even if large GPQC become available.   The largest obstacle to these post quantum systems is generally they involve much much larger public keys.  The bandwidth and storage requirements of Bitcoin are highly correlated to the size of the public key and we are talking about public keys in the tens of kilobytes (notice the plural) so transactions and blocks would be easily a hundred times larger.   Now it is entirely possible that Moore's law will mitigate this somewhat,  and stat using a 50,000 byte key in 2048 will be no more of a challenge then using a 256 bit key today.

For those who are interested in post quantum cryptography one implementation (which has open source implementation) is NTRU.  It is likely far too early to consider any such implementation in a production system but implementing a patched version of bitcoin on testnet which incorporates NTRU would be an interesting project.

That's a bit reassuring ! :)

To summarize, the OP is wrong. Bitcoin is not doomed because 256 bit keys are beyond brute force using anything that can be manufactured and we could always fork Bitcoin to 512 which is beyond beyond brute force but that will create a blockchain requiring a hard drive the size of Chevy van. lol

No chance.  I don't see the encryption on bitcoin being beaten in our lifetimes, or that of our children's.  Maybe in the very late future.  But if bitcion is doomed, EVERY SINGLE secure process on the internet is too.

Whow, he makes Iranian nuclear bombs look like the last straw of hope for the human race

No need to nuke anyone.  Just blow up some nukes in space, and have the beautiful EMP burn all technology alive.  Then, we won't have to worry about any form of hacking for many years to come!

Seems like the appropriate thread for this:

http://www.eetimes.com/document.asp?doc_id=1326468&_mc=NL_EET_EDT_EET_daily_20150429&cid=NL_EET_EDT_EET_daily_20150429&elq=a59559bfb7664cde842c7b2bb9e68b8c&elqCampaignId=22769&elqaid=25618&elqat=1&elqTrackId=6252292228f14224804cfbfa4bed4c75

But hydrogen cars are already operational in Germany.
They even produce solid hydrogen now.
I think it might catch up in the next decade as some countries like Japan or European countries will want to get away from oil.

I like how you stopped posting at 666.

IBM reports it works well for almost 15 seconds before bursting into a ball of flames. They expect great results as soon as they work out a way to bury it in the core of the ice planet Neptune.

"There is as yet insufficient data for a meaningful answer."

This just means that the news is useless. They haven't figured out a 'working quantum computer'. How can you say that something is working if it isn't stable for longer than 15 seconds?
I wouldn't worry about QComputers right now at the moment. Maybe in the future we will have to consider changing algorithms.

Nice article.
I think the Skynet robots will keep using Bitoins after they have destroyed the human race, because they will think it's perfect. I don't see any problem for Bitcoin here. Chill.

Here is a great exchange from a "mass storage and other technical stuff" related email list that I subscribe to discussing this IBM breakthrough:

First were the questions:


Then the reply to the questions:


Plus a follow on posting:

for those who are too busy/lazy to read D&T's statement, my interpretation is:

If QC starts to look like a threat to Bitcoin over the coming decades, a hardfork could be done into a new set of software and blockchain, that is QC proof. Basically a migration.

The only thing is that this migration has to be done early enough to prevent an (QC proof) altcoin from taking over.  ;)

the problem i could see, if they don't  disclose the release of a possible working machine, and keeps it secret, this could be a real issue

This is basically a science fiction entertainment for those that have too much free time. No, SHA256 is still safe, and if it cracked, the banking system would collapse as well since everything is running under SHA256 those days, from ATMs to electronic payment systems that each bank has implemented for their internet transactions, Paypal would get hit hard as well.