This.
On edit:In hindsight it might looks like I am trying to educate you kjj. That wasn't my intention just expanding on what I believe is a similar view on the threat of quantum computing which may be useful to others reading the thread. Then again I haven't had caffeine yet so no promises.
To expand upon what kjj said and to put it in simplified terms, Quantum Annealing is some pretty "interesting" stuff, but it isn't particularly well suited to breaking most forms of cryptography. Even if it was repurposed it can't be used to implement Shor's algorithm. Quantum Computing isn't the magical kill all crypto in the world instantly nonsense that the media makes it out to be. Quantum Computers can implement Quantum Algorithms. For the purpose of breaking public key cryptography the interesting one is Shor's algorithm because it provides a massive reduction in the complexity of the problem bring what otherwise would be an impossible to brute force scenario to one which can be completed in polynomial time. However using Shor's algorithm requires three things. The first is a general purpose quantum computer (which DWave isn't and never will be). The second is a public key to be attacked (and until spent the PubKey in bitcoin is unknown, you actually "send coins" to the PubKeyHash), and the third is the ability to construct said QC using a large enough number of qubits to implement the algorithm against keys of that size (and we are nowhere near the material science necessary to build a computer with tens of thousands of qubits).
So if an articles talks about "quantum computing being a threat to public key cryptography (and thus Bitcoin among thousands of other systems including TLS/SSL) it is paraphrased for
a general purpose quantum computer with a sufficient number of qubits capable of implementing Shor's algorithm to break a particularly sized public key. DWAVE's processors may end up being used for solving a lot of unique and interest problems and I am sure they will get larger and cheaper but it will never implement Shor's algorithm anymore than making an internal combustion engine more efficient will allow you to go faster than the speed of light. Quantum Annealing and general purpose Quantum Computing are two divergent areas of study that sadly are very "nerdy" and share similar names so the media won't ever be accurate enough in their articles. They use "Quantum Computing" to vaguely cover both fields.
So what about those fabled general purpose quantum computers? Do they exist? Well we have two very public and very reviewed milestones in general purpose quantum computers. General purpose means a design that is programmable or one which could someday lead to a programmable design. Much like your PC is an example of a general purpose classical computer. It can run various classical computing algorithms. A general purpose (or programmable) quantum computer would be one that could implement Shor's algorithm (a quantum algorithm which requires a quantum computer to execute in real time).
The first major milestone was in 2001 a general purpose quantum computer with 4 qubits was able to factor the number 15 (into 5 & 3). The next breakthrough came a decade later in 2011. Keep in mind this is a decade later. During that timeframe Moore's law improved the transistor density of "classical" computers by a factor of 32x. That means generally speaking computing power per watt and computing power per dollar also increased by roughly the same magnitude. So weaker encryption became even more weak by a factor of 32x. Quantum computer is in its infancy so the rate of improvement should be much higher right? So 4 bit number factored in 2001, for those playing along at home, how large of a number do you think was broken after a decade of improvement? 18 bits? 40 bits? 64 bits? Even 64 bit would be decades away from factoring 3,076 bit numbers. Don't use google or wikipedia just try to guestimate how much progress was made. From 4 bit to ____ bit after a decade.
Got your guess? Highlight the blue to reveal the answer.
It was the number 21 (into 7 & 3) using a 5 qubit QC and Shor's algorithm. Yes they added a whole one qubit in a decade. Quantum decoherence is a bitch. One good analogy is that is is like stacking pins while on a erratically moving platform. Stacking just two pins is a challenge, stacking 40,000 is a whole different level of "hard". If you wanted to stretch the definition it would be like saying that after a decade they were able to go from breaking 4 bit RSA keys to 5 bit RSA keys using Quantum Computing. RSA has never used 5 bit keys (because you could brute force all possible combinations (2^5 = only 32 possible keys, by hand using a pencil and paper but) saying "5 bit RSA key" provides a frame of reference.
Both 4,096 bit RSA and 256 bit ECDSA provide 128 bit security. 128 bit security is considered beyond brute force when using classical computers (although keys can be weakened through cryptanalysis). Key strength is a way to roughly measure the time/energy required to break various different cryptographic systems by providing the equivalent symmetric key security. 4,096 bit RSA (public key - integer factorization), 256 bit ECDSA (public key - elliptical curve), 256 bit SHA-2 (cryptographic hash), and 128 bit AES (symmetric key) all have 128 bit key strength. Since 128 bit is beyond brute force for any convceivable amount of time the only way these systems will be broken is through cryptanalysis which weakens the key not just using brute force. So if that quantum computer had factored a 4,096 bit number it would have done something that no classical computing system could do. In reality it did something, which millions of children have to do each year using pen and paper.
I have said it in other threads, wake me up when a general purpose quantum computer of sufficient size is able to factor 32 bit (or larger) number using Shor's algorithm faster and cheaper than a classical computer. To put it into perspective
For the record in hexadecimal this is a 5 bit number (what was actually broken):
This is a 32 bit number (my "wake me up milestone"):
This is a 128 bit number (a random symmetric key this size is considered beyond brute force for producing a collision):
0x26ec2f4d32976d86fa7e14a90c545ceb9b18c22564eaaac7b4e9df8dcded7ea699ac204c72f424cc9c82053eb981f317d69d4cac27e2bfaa83072cc0dcbf529a
This is a 4096 bit number (a QC would need to be able factor numbers this large to break 4,096 bit RSA which is the equivalent strength of 256 bit ECDSA):
0xc7f9012cee58a530dc00d5b3187c9e50349be48124ecc6e54d6ee3a5e1ccd0677272234c6f822915fbbf4516ec0905b16b194a68cd3471aafb240823081c9dfe
a8dc299795f597f762c66218a814e04540a6b4af3891cf77a4752e9b2fd702cfdbf424120b83738a87491af89a231f2df5c94507fbada889fdfe62e326adf682
ce20aa9f1209b53b6558e29952f693439d2143f00ded061c82e3762d8ea710d250d14e37d62816a7261c37b31a486a782390c14546ed9bd848cb00961c6168ed
934384bdc98610cd6d65ac33a14abc7efeb777b5b3f53e2273ad7043a954b8c82d8414be251b154160fe761c8e7941c26622b3a620d84a95f34d9ab4943a6dd4
Quantum Computing is a possible attack vector, it isn't an instant Bitcoin killer. There is no evidence that anyone is anywhere close to building a general purpose quantum computer of the size needed to be anywhere close to breaking 256 bit ECDSA. Even if/when that happens there are mitigating factors to consider.
The first is that if the PubKey is unknown Shor's algorithm can't be used, so don't reuse keys. It gives you options to transistion safely to stronger addresses/keys.
The second is that Bitcoin can as an interim step use larger/stronger keys. 512 bit or even 1,024 bit ECDSA. If quantum computing can break smaller keys it would provide a cushion of time/cost.
The third is that there are
Post Quantum Cryptography (PQC). Bitcoin in theory could be extended to use addresses based on PQC.
Note despite the similar names
Post Quantum Cryptography (PQC) shouldn't be confused with
Quantum Computing or
Quantum Cryptography. They are three distinct fields. Quantum Computing is the study of implementing quantum algorithms to solve problems (like breaking Bitcoin public keys). Quantum Cryptography is a system is key exchange which uses photons to ensure a key can not be intercepted by an eavesdropper (observing the photon will alter the photon). PQC are classical computing algorithms for which there is no known polynomial time solution even when using quantum computing. To date the major concerns with PQC are the need for much larger key and signatures sizes (easily 100x that of ECDSA), a lack of extensive testing, and in some cases weaker strength against classical computing.
