Not as such, that was only ever an empirical observation anyway, not a law of any kind.
Having said that, IBM just unveiled a 127 qubit machine, and their roadmap is to to to scale to 433, and then 1121 qubits in the not too distant future.
Yes, that's a lot considering that large systems today have in the order of 100-1000 qubits. Mind you, the systems currently saying that are larger than 100 qubits are debated if they really are quantum computers in the broadest sense, or a subset (consensus is they are a subset of quantum computers, and not full fledged). So the largest, "really quantum computers" are in the order of ~100 qubits.
Edit: for context, I'm referring to D-Wave, that some years ago said they had broken the 1000-qubit mark, but their systems aren't generic quantum computers, but rather computers tham implement quantum annealing.
It wouldn't be that insane for a factory to be able to create so many qubits. Building one qubit is hard, building two qubits is not double the effort.
My, highly imperfect, complete layman understanding is that the challenge has nothing to do with the "manufacture" of qubits, but rather getting them to work in the same computer without interfering with each other. I believe it gets harder with each qubit, not easier.
Is it possible to scale it by building separate computers and using distributed computing techniques? e.g. would 100 1 qubit computers be equivalent to a single 100 qubit computer?
The set of qubits needs to be an isolated system while the quantum computation happens, so no. By taking the qubits apart you would only make this much harder, if not impossible.
No. Most of the benefits of quantum computing requires the qbits be entangled with each other, so, crudely speaking, the difference between 100 (1-qbit-computers) and 1 (100-qbit-computer) is ability to compute using the 2^100 different ways the latter qbits can be entangled.
Right, and I don't understand why it took the industry so many decades for 64-bit computing to become dominant. If a factory is creating bits, it shouldn't take 64x the effort to create 64 of them versus 1 bit...
64 bit computing became dominant because of the need to address memory larger than 32 bits. They have the capability to scale quite 'easily' to 128 bits or further if they wanted to, there just wouldn't be a benefit. The Play Station 2 for example has 128 bit SIMD [1], 128 bit computing has been possible for a long time.
Once you have the ability to create a processor at 7nm with some bits, scaling is not so tough. Even if you cannot reliably create larger pieces of silicon, you just do something like AMD did with multiple dies connected by a fabric to mitigate risk. Absolutely worst case, you have a motherboard with multiple processors, or even computers in different buildings.
In terms of qubits, it is very likely that the problem can be distributed over multiple quantum computers. A significantly incentivized actor could definitely pull it off. If you can reliably manufacture ~100 qubit quantum computers, it's just a matter of scale.
> In terms of qubits, it is very likely that the problem can be distributed over multiple quantum computers.
No, this is very wrong. Qubits are only different from classical bits of they can communicate before becoming entangled with the environment (decoherence). You can't run some kind of "quantum cable" between two separate QCs in a rack and get twice the qubits - the interactions with the wire will break the entanglement between the qubits, and you will just have an unreliable classical computer with 100 bits of memory.
To perform a quantum computation, ALL the qubits (all your memory) must be in an entangled state together - this is the massive problem. Even worse, this state must be maintained while applying different transformations on the qubits from the outside.
In the paper they suggest that spending ~24 hours more doing computation means you can divide the number of qubits by 24, indicating that at least in one sense it is linearly scalable.
From my limited understanding, you process for a given amount of time, after which you can classically pull out an answer with some given probability, with some trade off with time and noise.
I imagine it would be somewhat possible to have several quantum computers running in parallel which end early, each correctly deducing the answer with some given probability. If each of the N^x machines has a 1/N chance of having the correct answer, you could simply test each solution classically.
And that assumes there is not some way to seed the search effort classically during the setup of the quantum circuit.
There are two aspects here. In order to implement a quantum algorithm, you need a minimum number of interacting qubits, which the article calls a qubit depth. All of these qubits must be entangled with each other in order to achieve any quantum speed-up. Below this number, your quantum algorithm simply can't be represented on the machine - it would be like trying to multiply two 128-bit numbers on a processor with 2 8-bit registers: you simply don't have enough working memory to do the calculations you need.
An extra complication for QCs is that you also need error correcting calculations in addition to your base calculations. So, if you want to multiply 2 128-bit numbers, not only do you need at least 256 (q)bits of working memory, you need some additional number to correct for errors in the calculation - and with currently known error correcting methods, you need A LOT more.
That's why the article is giving a minimum number of qbits for the Bitcoin calculation: 10^7 physical bits, which represent a measly ~2000 logical (perfect) qubits. This is the minimum number you would need to keep entangled for your your minimum clock period.
We are currently at 10^2, and even getting to 200 is a research-level task; 10^3 is far away. Once we get to something like 10^7, we may be able to start thinking of parallelizing at the whole machine level.
Even still, it's important to understand that quantum algorithms have, as far as we know for now, an exponential advantage over classical algorithms (note: this only applies to certain algorithms, NOT any algorithm). This only applies as long as you are running in the quantum regime. That is, if a particular quantum computer can resolve a problem for N components in 1 minute, and a quantum computer of double the qubit number can finish it in 30s, 2 QCs of the first type will finish it in something like 59s, since they will not benefit from the exponential quantum speedup.
> Building one qubit is hard, building two qubits is not double the effort.
No, it's much, much more than double the effort to build a QC with twice the qubits. The problem is that you want the qubits to interact with each other, but to be entirely perfectly isolated from the outside world for as long as necessary for signals from one to reach the others. The difficulty of achieving this isolation even for an instant at all increases by something like n^2 or n^3 (surface/volume of the isolated space) with the number n of qubits. Then, the more qubits you have, the more time you need for them to interact, so you multiply by an additional factor.
The numbers above are very handwavy, of course, but the point is that it's MUCH harder to build a bigger QC than a small one. So hard that it's not even clear if the current approaches can actually achieve this even in principle - we may need a different kind of qubit to scale up.
Yes, but the problem becomes who can evaluate it? Inevitably another AI system because of the complexity. And who has the most powerful AI? And what is their agenda? Ah! another backdoored algorithm.
But the real issue is the loss of confidence in the “blockchain technology”. If bitcoin is cracked the cryptomania scam will be done for a generation.
For a hash function to be mathematically secure, it needs to have a formal proof that the computational complexity of a preimage or collision attack (depending on the threat) meets some criteria. For example, [1]. As far as I'm aware, no such formalism exists for anything in the SHA family. This means in theory someday someone could discover a way to short circuit the desired complexity by taking advantage of some weakness in the algorithm, as they did to MD5 and SHA1 already.
In principal, these attacks are getting to the complexity where any new discovery will probably be aided by some form of AI (using a pretty loose definition of AI, computer aided search through an attack space). I only comment because the OP seemed rather flippant about 'math' protecting SHA256 where unless I'm mistaken there is no such protection.
FWIW I'm not trying to say that SHA256 is broken by anyone. I personally believe it may never be broken. I'm merely saying it's not mathematically proven to be as robust as we assume it is, but our assumption is fine for now for all practical purposes.
You’re correct that there is no proof of the security of SHA1. The existence of any one-way function would imply that P != NP.
And if it turns out that P = NP then it will turn out that most of the cryptographic guarantees we rely on today will be unrealizable on classical computers.
Quantum computers may not help us as it is currently unknown if quantum computers are more powerful than classical computers in terms of time complexity (it’s strongly suspected that this is the case though).
What relationship do any SHA family hashes have to do with P vs NP? I'm not aware of any. If there is some proof that subset sum reduces to constructing a preimage of anything in the SHA family then I would count that 'mathematically' secure but I don't think any such reduction exists.
The relationship is that computing the SHA hashes takes polynomial time. One way you can think of NP is that it is the set of problems whose solutions that can be deterministically verified in polynomial time. So for any hash computable in polynomial time, the pre-image problem is in NP.
Note that this doesn’t prove the security of SHA256, it just says that to prove it secure would be to prove P != NP. You could still prove SHA256 insecure and that proof could be totally separate from P =? NP.
There is no encryption in Bitcoin. It uses asymmetric cryptography for signatures, and it uses hashing. Encryption might be used by wallets, but that is not part of the consensus layer and therefore not part of Bitcoin.
But the signature is an encrypted hash value, which is decrypted when verifying the signature. Maybe you could say signature verification as a concept is not encryption, but certainly Bitcoin's implementation uses encryption, and I don't think there's any definition of 'asymmetric cryptography' that is not also some form of encryption.
I'm not an expert on BTC, but I'd guess that if you can derive the private key of a signature from its public key (which is what the paper is describing), you can use that to place transactions from said wallet on the blockchain (ie. spend that wallet's money), right? Genuinely curious if I understand this correctly, there's a lot I don't know about how bitcoin's protocol works.
No. Encryption is just one type of cryptography, used to make data unreadable without the secret key. Signatures are something else, used to prove that the holder of a secret signed the public data. Zero knowledge proofs are another, used to prove you know a secret without revealing it. It's a fascinating subject.
I'm not saying all cryptography is encryption, I'm not even really talking about signatures, I'm specifically talking about asymmetric cryptography. I don't see any example of "asymmetric cryptography" which is not just a usage of public-private key encryption.
If you're talking specifically about RSA, then it's true that encryption and signatures both use the same type of asymmetric math, but in opposite directions. But most asymmetric cryptography doesn't have this property.
No I don't think the paper is talking about breaking hashing here, they're talking about breaking the 256-bit elliptic curve encryption of keys in the Bitcoin network.
Hashing isn't really the same thing... you're not "encrypting" data when you hash it, you're putting it through a one-way function that produces a consistent fixed-size output, such that if you provide the same input again, you get the same output.
Hashes aren't "reversible" in any reasonable sense of the word. Sure, you can keep guessing inputs until you produce one that has the same hash, but it's misleading to say that you're "decrypting" it. I'd instead say you're finding collisions.
To me, "decryption" implies that there's some secret you have which can take the hash and turn it back into its original input in constant or linear time. Using the word "decryption" to describe "finding a hash collision" isn't really correct.
Can someone give a quick rundown on why quantum computers so far only have small numbers of qubits? I remember reading something about errors creeping in somehow, and it's hard to build a large system, but don't really understand why.
Current architectures aren't ready to operate enough gates fast/accurate[1] enough to attempt sustained (i.e. longer than milliseconds) protection of quantum data. So making more qubits would not be very useful until we can make them talk to each other.
[1]: Qubits are always decohering, so fast and accurate are closely linked.
Decoherence is the answer. Veeeeery long story short, qubits have to be isolated from the world as much as possible to maintain their "magical quantum properties". Decoherence is when those ideal conditions break, and the qubits no longer behave as needed for the quantum computer to work. The more qubits you have, thet harder it gets to fend off the inteference from the outside world that decoheres the qubits.
Ok, so it gets N times harder, but you get M times more compute power. Is there a relation between N and M? Is at least M larger than N? Will N get lower with more qubits?
Thinking about things being N times harder is probably the wrong approach at the current time.
We’re so early in the engineering of these computers that it’s “we don’t know how to make more than X usable qbits in this configuration at any cost” rather than “X+1 qbits is Y dollars more expensive”.
Worth noting that the value of X depends heavily on the configuration and the things holding the qbits; IIRC the D-wave design is scalable but also not a “universal” quantum computer. I’m unclear on the specifics of how and why.
The D-Wave design is for quantum annealing, which is still super interesting and solves practical problems, in particular optimization problems. You can read a few summaries of the different systems and how they were compared to classical computers at launch in Wikipedia[0].
For a quick tl;dr: D-Wave computers can speed up certain optimization problems, but more than a few times it's been in doubt if they provide an advantage over classical computers or not (notice that a few times they compared against single threaded systems).
Before you get too excited, it's important to remember that existing qubit implementations do not achieve a physical gate error rate of 10^-3 (best right now is more like 10^-2).
Oh yes sorry my mistake, I merged the two data and I made a bit of confusion, I thought it was 317 x 10(6) and 130 x 10(6), instead is 13 not 130. Sorry. By the way moderators have changed the title (but now I don’t know who will understand what this post is about)
If hypothetically this would happen, wouldn't gaining access to everyone's wallets render it useless since BTC would no longer have value? If so, the goal would just be to disrupt the financial markets, not necessarily to gain directly.
Also, wouldn't we be able to restore everyone's wallets from the latest snapshot on a new blockchain?
If I had ability to gain access to everyone's wallet I'd probably attempt to siphon off a few million dollars a day worth of bitcoin. If people catch on that all is lost after awhile oh well - I've already cashed out significantly.
For the second, it would depend on easy/hard it is to mine to get to the point where you can replicate a snapshot, and how easy/hard it is to continue mining on from that point. It is very unlikely the new protocol will hold the same value as BTC would have had.
Indeed, a viable QC that can break existing widespread asymmetric crypto is worth far more than the total mkt cap of all "crypto" at their combined peak.
Most likely this will be wielded by USA or China in secret (if not being done already)
Likely the crypto methods would evolve well before the hardware caught up. It's unlikely that suddenly out of the blue someone would show up with a 13M qubit quantum computer that could crack all wallets.
I gotta imagine you could probably sneak a good chunk of selling in before people noticed or the thing went to zero. You'll likely have time to plan after breaking it, so you could move quick, and there are many long inactive wallets with tons of BTC in them. Some have keys lost in landfills, some have dead or jailed owners, and so on.
So I can see how you could pull it off before the price tanked, and even then, it's not a given that it'd go to zero. Just because a powerful actor can compromise your Bitcoin wallet doesn't _necessarily_ make it completely worthless -- just look at all the chains that are trivial to 51% attack which are still chugging along with small valuations. The price probably would collapse though.
Still they could extract a fair amount of value before everyone catches on. Especially if you don't know the exact day/month/year that became possible; when would you take the snapshot? No one would accept transactions after that snapshot date either, if they worry it'll all get rolled back.
Of course the market would just sink in the years leading up to that threshold, in anticipation of this (assuming no mitigation in this case).
The idea is that for the Bitcoin network "knowing the private key" is 1:1 entriely equivale to "being the legitimate owner of the wallet". Onve someone has found out the private key of a wallet, they have the exact same access to that wallet as anyone else who knows the private key.
This is different from finding out someone's password or even password + MFA on a centralized service, say Gmail. There, Google and/or the court systems step in, ascertain the legitimate owner, reset the credentials to the account, and give only the legitimate owner access.
There is no way to do this in Bitcoin, by design. Even if the US Supreme Court decided that you are the only legitimate owner of this wallet, there would be no way to prevent someone else who knows the private key from moving "your" Bitcoin. Of course, they could be punished for this, in principle, but it would be impossible to prevent it from happening.
Well, DWave claims 5,000 qbits. Unclear if they can work on this problem. So, if you had 100 of those, you could break Bitcoin wallets in a year. Retrieve all those lost coins from the early days.
Dwave don't make general purpose quantum computers. They do something called quantum annealing, which is only useful for a very specific set of problems.
The problem isn't quantum annealing, the problem is that what dwave is actually doing is throwing a ball of mud at a wall, and saying that if enough mud sticks, you can do quantum annealing with the spackle pattern.
83 comments
[ 0.22 ms ] story [ 151 ms ] threadHaving said that, IBM just unveiled a 127 qubit machine, and their roadmap is to to to scale to 433, and then 1121 qubits in the not too distant future.
https://newsroom.ibm.com/2021-11-16-IBM-Unveils-Breakthrough...
Edit: for context, I'm referring to D-Wave, that some years ago said they had broken the 1000-qubit mark, but their systems aren't generic quantum computers, but rather computers tham implement quantum annealing.
Yes. Now the most powerful quantum computers have less than 100 qubits. We have to reach 130,000,000 qubits. Take a beer meanwhile =)
Once you have the ability to create a processor at 7nm with some bits, scaling is not so tough. Even if you cannot reliably create larger pieces of silicon, you just do something like AMD did with multiple dies connected by a fabric to mitigate risk. Absolutely worst case, you have a motherboard with multiple processors, or even computers in different buildings.
In terms of qubits, it is very likely that the problem can be distributed over multiple quantum computers. A significantly incentivized actor could definitely pull it off. If you can reliably manufacture ~100 qubit quantum computers, it's just a matter of scale.
[1] https://en.wikipedia.org/wiki/PlayStation_2_technical_specif...
No, this is very wrong. Qubits are only different from classical bits of they can communicate before becoming entangled with the environment (decoherence). You can't run some kind of "quantum cable" between two separate QCs in a rack and get twice the qubits - the interactions with the wire will break the entanglement between the qubits, and you will just have an unreliable classical computer with 100 bits of memory.
To perform a quantum computation, ALL the qubits (all your memory) must be in an entangled state together - this is the massive problem. Even worse, this state must be maintained while applying different transformations on the qubits from the outside.
From my limited understanding, you process for a given amount of time, after which you can classically pull out an answer with some given probability, with some trade off with time and noise.
I imagine it would be somewhat possible to have several quantum computers running in parallel which end early, each correctly deducing the answer with some given probability. If each of the N^x machines has a 1/N chance of having the correct answer, you could simply test each solution classically.
And that assumes there is not some way to seed the search effort classically during the setup of the quantum circuit.
An extra complication for QCs is that you also need error correcting calculations in addition to your base calculations. So, if you want to multiply 2 128-bit numbers, not only do you need at least 256 (q)bits of working memory, you need some additional number to correct for errors in the calculation - and with currently known error correcting methods, you need A LOT more.
That's why the article is giving a minimum number of qbits for the Bitcoin calculation: 10^7 physical bits, which represent a measly ~2000 logical (perfect) qubits. This is the minimum number you would need to keep entangled for your your minimum clock period.
We are currently at 10^2, and even getting to 200 is a research-level task; 10^3 is far away. Once we get to something like 10^7, we may be able to start thinking of parallelizing at the whole machine level.
Even still, it's important to understand that quantum algorithms have, as far as we know for now, an exponential advantage over classical algorithms (note: this only applies to certain algorithms, NOT any algorithm). This only applies as long as you are running in the quantum regime. That is, if a particular quantum computer can resolve a problem for N components in 1 minute, and a quantum computer of double the qubit number can finish it in 30s, 2 QCs of the first type will finish it in something like 59s, since they will not benefit from the exponential quantum speedup.
No, it's much, much more than double the effort to build a QC with twice the qubits. The problem is that you want the qubits to interact with each other, but to be entirely perfectly isolated from the outside world for as long as necessary for signals from one to reach the others. The difficulty of achieving this isolation even for an instant at all increases by something like n^2 or n^3 (surface/volume of the isolated space) with the number n of qubits. Then, the more qubits you have, the more time you need for them to interact, so you multiply by an additional factor.
The numbers above are very handwavy, of course, but the point is that it's MUCH harder to build a bigger QC than a small one. So hard that it's not even clear if the current approaches can actually achieve this even in principle - we may need a different kind of qubit to scale up.
But crypto won’t last long enough for that to be meaningful. I give bitcoin 3 months to the floor.
AI cannot magically make math not exist, but nice try.
https://en.wikipedia.org/wiki/One-way_function
In principal, these attacks are getting to the complexity where any new discovery will probably be aided by some form of AI (using a pretty loose definition of AI, computer aided search through an attack space). I only comment because the OP seemed rather flippant about 'math' protecting SHA256 where unless I'm mistaken there is no such protection.
[1] https://en.wikipedia.org/wiki/Security_of_cryptographic_hash...
And if it turns out that P = NP then it will turn out that most of the cryptographic guarantees we rely on today will be unrealizable on classical computers.
Quantum computers may not help us as it is currently unknown if quantum computers are more powerful than classical computers in terms of time complexity (it’s strongly suspected that this is the case though).
Note that this doesn’t prove the security of SHA256, it just says that to prove it secure would be to prove P != NP. You could still prove SHA256 insecure and that proof could be totally separate from P =? NP.
Encryption is just a sub type of cryptography. In fact, signatures are a more common use of asymmetric cryptography than asymmetric encryption.
Isn't that...asymmetric encryption?
Hashing isn't really the same as encryption; hashes can't be decrypted.
*) https://avs.scitation.org/doi/10.1116/5.0073075
Hashing isn't really the same thing... you're not "encrypting" data when you hash it, you're putting it through a one-way function that produces a consistent fixed-size output, such that if you provide the same input again, you get the same output.
Hashes aren't "reversible" in any reasonable sense of the word. Sure, you can keep guessing inputs until you produce one that has the same hash, but it's misleading to say that you're "decrypting" it. I'd instead say you're finding collisions.
To me, "decryption" implies that there's some secret you have which can take the hash and turn it back into its original input in constant or linear time. Using the word "decryption" to describe "finding a hash collision" isn't really correct.
Edit: something to do with decoherence, I think: https://en.m.wikipedia.org/wiki/Quantum_computing#Quantum_de...
[1]: Qubits are always decohering, so fast and accurate are closely linked.
We’re so early in the engineering of these computers that it’s “we don’t know how to make more than X usable qbits in this configuration at any cost” rather than “X+1 qbits is Y dollars more expensive”.
Worth noting that the value of X depends heavily on the configuration and the things holding the qbits; IIRC the D-wave design is scalable but also not a “universal” quantum computer. I’m unclear on the specifics of how and why.
For a quick tl;dr: D-Wave computers can speed up certain optimization problems, but more than a few times it's been in doubt if they provide an advantage over classical computers or not (notice that a few times they compared against single threaded systems).
[0] https://en.wikipedia.org/wiki/D-Wave_Systems#Computer_system...
Before you get too excited, it's important to remember that existing qubit implementations do not achieve a physical gate error rate of 10^-3 (best right now is more like 10^-2).
Also, wouldn't we be able to restore everyone's wallets from the latest snapshot on a new blockchain?
It would only be useful for the wallets with known public keys. That's mainly old bitcoins, new ones only have its hash written to the chain.
This would certainly crash the price, but not to zero.
> Also, wouldn't we be able to restore everyone's wallets from the latest snapshot on a new blockchain?
Yes, but what good will it do you if the private key is leaked?
For the second, it would depend on easy/hard it is to mine to get to the point where you can replicate a snapshot, and how easy/hard it is to continue mining on from that point. It is very unlikely the new protocol will hold the same value as BTC would have had.
Most likely this will be wielded by USA or China in secret (if not being done already)
So I can see how you could pull it off before the price tanked, and even then, it's not a given that it'd go to zero. Just because a powerful actor can compromise your Bitcoin wallet doesn't _necessarily_ make it completely worthless -- just look at all the chains that are trivial to 51% attack which are still chugging along with small valuations. The price probably would collapse though.
Of course the market would just sink in the years leading up to that threshold, in anticipation of this (assuming no mitigation in this case).
This is different from finding out someone's password or even password + MFA on a centralized service, say Gmail. There, Google and/or the court systems step in, ascertain the legitimate owner, reset the credentials to the account, and give only the legitimate owner access.
There is no way to do this in Bitcoin, by design. Even if the US Supreme Court decided that you are the only legitimate owner of this wallet, there would be no way to prevent someone else who knows the private key from moving "your" Bitcoin. Of course, they could be punished for this, in principle, but it would be impossible to prevent it from happening.
(it would require 317M qubits at minimum, title has a typo)