The impact of hardware specifications on reaching quantum advantage
avs.scitation.org
avs.scitation.org
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)
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.
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.
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.
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.
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.
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.