Bitcoin Forum

512 qbit quantum computer is here...

How much time would it take to convert Bitcoin address to key??

https://www.youtube.com/watch?v=CMdHDHEuOUE

I think, still not there. Someone said it should be thousands of qubits.

1000 qbit ≈ 2 * 512 qbit processors

I think, they (NASA, google, D-Wave) should have few hundreds of 512 qbit processors.

It would be better used to optimize FPGA code and make a better ASIC, then move on to other things.

It doesn't work that way.  x 512 qbit QC can't do anything more complex than 1 512 qbit QC although they can do 2x as many simulations.  


As posted many times D-Wave is not a general purpose quantum computer.  DWave is a type of specailized quantum computer which uses a concept called quantum annealing to simplify complex simulations.

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

DWave is not capable of and was never designed to implement Shor's algorithm. It has absolutely no ability to break ECDSA keys.  Even if D-Wave was a general purpose quantum computer and capable of implementing Shor's algorithm against ECDSA keys it would need to be on the order of tens of thousands qbits.  Lastly an address is the hash of the public key.  Even if a general purpose quantum computers with sufficient qbits and capable of implementing Shor's algorithm against ECDSA keys the PUBLIC KEY is still needed.  If coins haven't been spent from an address (no address reuse) then the public key remains unknown and thus unsolvable.

So the question is, can this crack SHA256?

No.

(Chewed, digested and vomited D&T's answer for you. It wasn't much of an effort... Enjoy your vomit.)

This might be slightly off-topic for the thread, but it's quantum related and has implications for both Bitcoin and cryptography in general.  Do any of our resident quantum gurus (D&T, gmaxwell, or anyone else) have an opinion on this:

http://noospheer.wordpress.com/2013/09/04/why-turing-machines-are-quantum/

It essentially claims that, based on some new research from the past couple decades, it might be possible to efficiently simulate certain kinds of quantum circuits on classical computers, with only n*logarithmic (as opposed to exponential) overhead.

Quantum is still in it's infancy. The day a major fully functional quantum computer comes online will be a big day. It won't even seem like a computer as it will have superhero abilities, such as breaking encryption.

This device is not the same class of device that computer scientists are speaking about when they say "quantum computer". It's analogous to building a digital computer that can only perform addition: An add-only-machine "computes", but it's not turing complete. The DWAVE devices are not quantum turing complete: they cannot perform the fast quantum period finding algorithms which would are apparently needed to recover a private key from a public key. It is a quantum computer only in the sense that it computes and (maybe) uses some quantum effect. Nor does their device appear to have any clear way to generalize to quantum turing completeness in the future, nor are they claiming that it does.

Moreover, you asked for an even harder problem: Converting an address to its private key requires finding the pre-image to RIPEMD160+SHA256 (and its discrete log), and this wouldn't be efficiently computable on a real quantum computer.

The noospheer guy has been all over the place trying to collect money for his batshit craziness. He emits a lot of technobabble that doesn't have any credibility. If he actually could do what he claims he could trivially prove it to anyone (e.g. by finding a discrete log of a nothing-up-my-sleeve point).

People frequently exaggerate the capabilities of quantum computers. Indeed, such a device would be magical and a breakthrough and would help solve many interesting problems. But quantum computers are not even conjectured to break _all_ encryption, they only break some classes of cryptography (such as asymmetric cryptography based on the hardness of hidden subgroup problem in abelian groups, like factoring and discrete log), and even then only if the QC is sufficiently large (in terms of gates and coherence length).

True. But SHA256 would be at risk. And as far as quantum being magic, it is as close as physics comes. lol  ;D

I'm not trying to kiss your ass here, but we are so lucky that you (and other equally talented devs) have decided to focus your efforts on Bitcoin.

Finally, something that can run Windows smoothly.

Not only that, but it appears that simulation for random QUBO instances within a D-Wave constraint graph can be beaten by a standard laptop with simulated annealing code (http://www.scottaaronson.com/blog/?p=1400).

More here:
http://www.archduke.org/stuff/d-wave-comment-on-comparison-with-classical-computers/

Don't get me wrong, they might be on the cusp of something truly interesting here, but there's a lot of smoke and mirrors about whether or not this is a true technological breakthrough.

And as gmaxwell is saying, this is far from being able to decrypt anything right now.

Dont worry, D-Wave is not true quantum computer.

No the opposite is actually true.   Symmetric encryption (like AES) and cryptographic hashing algorithms (like SHA-2) are not significantly effected by quantum computing.   Grover's algorithm makes then faster than brute force but not fast enough to be useful.   The vulnerabilities lies in public key cryptography (ECDSA, RSA, etc).

Can we get a script that posts this answer every time someone starts a new thread with the word "quantum" in it?

D-wave's machine is reported to be 3600x faster than a Core 2 Quad CPU (on certain specifically suited calculation), which can do 20MH/s in bitcoin mining. That makes it 72Gh/s = one Avalon ASIC mining rig

I didn't see anything in there about logN overhead? 

   

Anyone know if this quantum computer generates 51% of Bitcoins hashing power?

OP aside, when is it speculated that quantum computers exist that can break SHA-256 encryption? Or is this still sci-fi territory?

No.  It'll generate, as said before, about 72GH/s. 

Enough with all this rational discourse of esoteric concepts made startlingly clear by well-versed computer scientists.  This is bitcointalk, just tell me where I'm supposed to send all my money.

Better to ask in technical but the opinion is that we end up in a paradox

General purpose programmable Quantum Computer is kinda like fusion power.  In the 1980s there were headlines that commercial fusion power was less than 40 years away.  In the 1990s it was less than 40 years away.  In the 2000s it was less than 40 years away.  IIRC just recently a fusion reactor acheived unity (power out = power in) and .... <drumroll> commercial power may be possible within 40 to 50 years.  I know would be willing to bet (even money if anyone is interested) that I won't see a commercial fusion power plant in my lifetime.  This is despite nearly 4 decades of research.  It some way it seems we are further away then scientists thought we were in the 1980s.

SHA-256 (or any other hashing algorithm or symmetric encryption algorithm) is not vulnerable to quantum computing.  The speedup what QC provides against those types of systems is low.   Public key cryptography (ECDSA, RSA, SSL, PGP, etc) is the "vulnerable" area at least in theory.  So the ECDSA used to verify transaction signatures, not SHA-256 used in mining would be the "target" of an ECDSA "attack".  It will take ~4,000 logic* qubits (the number of physical qubits is much more see below if you want to see how far the rabbit hole goes) to implement Shor's algorithm to break a 256 bit ECDSA private key.  Even then it is impossible if the pulic key is unknown.   For the record DWAVE is exactly 0 qubits for the purpose of breaking ECDSA and the largest general purpose quantum computer built to date (IBM) is 7 qubits

Some general purpose quantum computing milestone:
In 2001 IBM researchers were able to factor the number 15 using a quantum computer.  This would be the equivalent of breaking a 4 bit private key.
In 2011 Chinese were able to factor the number 143 using a quantum computer.  This would be the equivalent of breaking an 8 bit private key.

So roughly a doubling of the vulnerable bit strength per decade.  Note this shouldn't be taken seriously but rather is used to illustrate the absolute baby steps being taken.  In both scenarios the amount of time necessary to "solve" these problems with known finite solutions was many orders of magnitude longer than it would take to do it by hand with a pen and paper.  If this doesn't accelerate faster than Moore's law then public key cryptography may never be vulnerable as one can continue to use larger keys.  For Quantum computing to be a threat the capabilities would need to eclipse Moore's law by a significant amount to "catch up" to what is already possible using classical computing.

AFAIK 143 (8 bit number) is the largest number factored used quantum computing.  I think it was Gavin who said (paraphrased) let me know when they can factor a 32 bit number in reasonable time and cost.  Honestly we may be years from even that milestone.

*  As large as 4,000 qubits sounds, quantum computing is very "noisy" and thus to get any reasonable accuracy more than 1 physical qubit is used to represent a single logical qubit to provide a measure of error correction.  This is similar to error code correcting ram using extra bits to correct errors so that number of physical bits on a memory stick is larger than the number of logical bits seen by the computer.   Due to noise the simulation is run over and over and over with the solution of each iteration recorded, the simulation reset and then run again.  Over a large number of simulations the "real solution" will be detectable from the noise.  Very simplified but imagine you used a Quantum Computer and the solutions were represented by letters, the output of a sequence of simulations might look like  A, C, D, A, D, R, F, T, I, L, A, G, Y, J, I, L, K, G.  Since A, D, G occur more frequently it is probable they represent more than just noise, while "Y" for example could simply be the computer recording random noise.  The more qubits used for error correction to more accurate the simulation.  It isn't even really known how much error correction will be needed to get results in any timely manner but one paper I read estimated it at 10 physical qubits for 1 logical qubit.  So we are looking at something on the order of a 40,000 physical qubit machine to break a 256 bit ECDSA private key.  While in theory a 4,000 qubit computer can implement Shor's algorithm unless our material sciences improve to sci-fiction capabilities (building a space elevator would be less of a challenge) it may take an utterly useless number of simulations to identify the true solution from the noise.

I think everything has its time. More people will be involved in it more results will be.

Is it anywhere simplified?

What physical laws are holding us back?

NO.

Nah, unless you have a whole factory of it..

lol

LOL..  shut up and take my money... 

Thank you sir..  truly a laugh out loud

How is that a useful bet for you to make? You have to die to win!  :D

Nerd life insurance policy?

The two main branches of research into realizing a quantum computer are photonics and nuclear magnetic resonance.  Both of which have their issues, but there's been some interesting research in converting entangled states of one "medium" into another, if you will.  The main issue is the fact that we will never have a truly closed quantum system.  Between external potentials and pre-existing external entanglement, you introduce bias towards certain states, which ruins the computation.  Scaling up the qubit registers and circuits only amplifies this bias further.  Error correcting circuits can help with this, but the circuit complexity then increases accordingly (I believe this is a n*log(n) relation IIRC).

I'd do that.

Thanks for the explanation. :)

Do you really think they're going to get this amazing world's first quantum computer and go, yep lets use it to destroy that Bitcoin thing? Even if it was powerful enough to do that. They'll use it for important stuff like answering scientific questions that have never been answered before about physics, space etc.

FYPFY but no I don't think  Bitcoin will be a high priority

Confirming.  Don't worry though, I doubt they have any universal quantum computer with more than 32 qubits right now (not necessarily a least upper bound).

this will not work and if it will Bitcoin will adopt :)

has anyone even tried hashing on it yet, or gotten a miner software for it?

Only if a BSOD is not observed directly.