19
$\begingroup$

Yesterday IBM announced that they have a 433 bit quantum computer, called Osprey. There is nothing in the press releases I can find that says whether it can or cannot run Shor's Algorithm.

They also say they are on track to release "Condor", an 1121 bit processor next year.

Shor's algorithm, as far as I know, requires twice the number of bits in the key, so a 256 bit key requires 512 qubits to crack. Hence Osprey cannot do this, but apparently Condor will be able to.

256-bit keys are widely used - for example Ed25519 as used by Bitcoin, and is a valid TLS algorithm.

Is it expected that Osprey will be able to run Shor's algorithm?

If it can, how can the loss of security best be mitigated?

Improve this question
$\endgroup$
3
  • 6
    $\begingroup$ I have yet to find any claim that a physical quantum computer has run Shor's algorithm to factor an integer larger than 21. And then it's disputed if such claimed implementations of Shor's algorithms factor, or verify a known result. See Largest integer factored by Shor's algorithm? for details and references. I don't make this comment an answer because I can't make an independent informed opinion, for I know too little on Quantum Computers and Shor's algorithm, and next to nothing on Osprey. $\endgroup$
    – fgrieu ♦
    Nov 10, 2022 at 11:00
  • $\begingroup$ It wasn't using Shor's algorithm, but I believe Collin Williams demonstrated factoring numbers using N^2 QBITS on a D-Wave quantum computer. I believe he was able to factor numbers up to 16 bits using the machine he had at the time. $\endgroup$
    – user4574
    Nov 10, 2022 at 22:22
  • $\begingroup$ @user4574: That falls under "Stunts" in this answer: crypto.stackexchange.com/a/59796/7218 $\endgroup$
    – R.. GitHub STOP HELPING ICE
    Mar 7 at 2:08

1 Answer 1

Reset to default
26
$\begingroup$

No. The issue here is the distinction between physical qubits and logical qubits. The back of the envelope estimate for Shor's algorithm for a 256-bit elliptic curve is 512 logical qubits, but a more accurate costing by Roeteller et al is 2330 logical qubits.

Logical qubits are idealised computational resources that would need a perfectly engineered physical qubit to achieve. The Osprey chip and its ilk have physical qubits that degrade over time and perform operations with a certain error rate. Instead several physical qubits of the Osprey sort would be need to emulate the behaviour of a logical qubit using quantum error correction. Estimates for the number of physical qubits required to break 256-bit ECC in one hour (and these physical qubits would still be to a high engineering specification, perhaps beyond that of Condor) is $317\times 10^6$ per work by Webber et al. Similarly, they quote $13\times 10^6$ physical qubits of this high quality to solve this problem inside a day.

Improve this answer
$\endgroup$
5
  • 2
    $\begingroup$ The second citation is: Mark Webber, Vincent Elfving, Sebastian Weidt and Winfried K. Hensinger: The impact of hardware specifications on reaching quantum advantage in the fault tolerant regime, in AVS Quantum Science (2021), doi: 10.1116/5.0073075. It flies high over my head but I like the idea that we can make such estimates. I hope I'll someday be proven pessimistic for conjecturing human civilization will never get to CRQC. $\endgroup$
    – fgrieu ♦
    Nov 10, 2022 at 11:18
  • 8
    $\begingroup$ For those who read this answer, the estimate of 317 million qubits is to break the 256-bit key within one hour assuming certain hardware properties. The same paper estimates 13 million required to break in 24 hours. $\endgroup$
    – Simon G.
    Nov 10, 2022 at 11:33
  • $\begingroup$ Thanks fgrieu, Simon G, I have incorporated both of your comments into the answer. $\endgroup$
    – Daniel S
    Nov 10, 2022 at 13:54
  • 1
    $\begingroup$ @DeanMacGregor I'm afraid those were the headline data points picked by the authors, though their methodology could produce others. The qubits to time relationship is certainly not (inverse) linear as the longer and more operations that a logical qubit has to exist for increases the number of physical qubits need to emulate it. The two data points therefore might represent the most achievable values, thought the authors would know better. $\endgroup$
    – Daniel S
    Nov 10, 2022 at 18:45
  • 5
    $\begingroup$ Further to the above, fig. 1 of the paper seems to suggest a hard-ish lower bound of around $8\times 10^6$ physical qubits of the chosen specification. $\endgroup$
    – Daniel S
    Nov 10, 2022 at 19:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.