You might as well ask what would be required to factor an 8 bit integer key.
Because decades after the factorization of 21, we're still waiting for a quantum computer able to factor any product of two 4-bit primes with the general Shor algorithm.
Ok, so ... what would be required for the 8 bit key? Do we have reputable numbers? And are the qubits in the article equivalent to other qubits or are they lacking in some way?
You need a few dozen logical qubits. Qubits that have negligible errors and do not lose coherence. The problem is that a single logical qubit takes hundreds of physical qubits and advanced error correction techniques to construct.
The more I hear about quantum computing the more it sounds like make believe grift. I first heard about it in a 2600 magazine in 1997 or so. And the claims and "way forward" then and now are roughly equivalent.
Read as: I've heard for nearly 30 years that quantum is just around the corner, and we need post quantum cryptography.
Or, as reverend Sharpton said: "All hell's gunna break loose; and you're gunna need a Bitcoin!"
To be fair the story has been consistent. The hardware is lacking and the predictions are testable given advances in it.
When you compare it to the historical development of classical computers it's proceeding at a decent rate. Imagine if we'd needed hundreds of thousands of transistors before being able to demonstrate actually useful work by a classical computer. They likely never would have been developed in the first place.
Cryptography wise I'd expect dire warnings about any theoretical attack that's reasonably plausible. Better to react immediately than sit around waiting for it to materialize. It took over 15 years after the warnings for SHA to be broken in practice and I don't necessarily expect that SHA2 ever will be but we've moved on to SHA3 nonetheless.
to compare, ENIAC had 18,000 tubes and 1200 relays, and could perform 5000 additions, or 3 square roots per second. in 1956, when it was decommissioned.
that was 80 years ago, for the military. So plotting that out, first actual PC was 25 years after ENIAC was decommissioned, the IBM PC 5150, with 29,000 transistors in the 8088. 12 years later, the 586 had 3.1mm transistors, P4 had 42mm, 10 years later (2003) p4xe had 169mm (but a year earlier there were only 65mm in the p4). haswell, ten years later, 1.4 billion transistors. in 2023, AMD ryzen 7800x3d had 6.5 billion transistors.
Well, i did this a few times between 2011-2016 and predicted SSD/NVME and spindle sizes through this year pretty accurately. Moore's "law" said the graph has a maximum angle, but i think most people think it implies a minimum angle. the graph i plotted is a lot less steep than Moore's law ought to imply, but these are all desktop CPUs - workstation/server CPUs are over 100 billion transistors already and are well within the constraints of Moore's law.
> Is there some minimum number of qubits at which some minimum viable quantum-supreme task can theoretically be achieved?
That is a very broad range of possibilities, so allow me to narrow it to cryptography. I am by no means an expert on this, but I spent the weekend reading about quantum motivations to change the cryptographic algorithms society uses and as at as I can tell, nobody knows what the hard lower bound is for breaking hardness assumptions in classical cryptography. The best guess is that it is many orders of magnitude higher than what current machines can do.
We are so far from machines capable of this that it is unclear that a machine capable of it will be made in our lifetimes, despite optimism/fear/hope, depending on who you are, to the contrary.
> What would be required to factor a 1024 bit integer key?
I assume you mean a 1024-bit RSA key (if you mean a 1024-bit ECC key, I want to know what curve). You can crack 1024-bit RSA with 2051 logical qubits according to:
In order for it to actually work, it is believed that you will need between 1000 to 10000 physical qubits for every logical qubit, so it could take up to 20 million qubits.
Coincidentally, the following paper claims that cracking a 2048-bit RSA key can be done in 8 hours with 20 million physical qubits:
That sounds like it should not make sense given the previous upper estimate of 20 million physical qubits for a 1024-bit RSA key. As far as I can tell, there are different ways of implementing Shor’s algorithm and some ways use more qubits and some ways use less. The biggest factor in the number of physical qubits used is the error correction. If you can do better error correction, you can use fewer physical qubits.
Factoring requires much better noise performance. So you don't have to consider the number of qubits yet for that particular application. A fundamental breakthrough is required.
There might be applications other than factoring that can be addressed with the noisy qubits we can actually create.
It is said to be useful for optimization problems like protein folding, although they have so few qubits that I am not sure how useful it really could be. A microcontroller with only 1024 bits of RAM for example has very limited usefulness so I would not think a quantum computer with a similar number of qubits would be very useful either.
What would be required to factor a 1024 bit integer key?