Shor and Grover: Qubit Counts Plummet

▶ Watch (14:22)

Original Shor’s algorithm estimates required a billion noisy qubits. Gidney’s 2021 paper showed 20 million noisy (6,000 logical) could factor 2048-bit RSA in 8 hours. His 2025 solo work dropped that to under a million noisy (1,399 logical) with a 5-day runtime. Grover’s algorithm needs 1,000 to 3,000 logical qubits to weaken AES-128 to a 64-bit security level. Algorithm optimisations like windowed arithmetic and magic state cultivation drove the 100-fold space-time reduction.

IonQ and IBM: 2028–2030 Beats 2035

▶ Watch (23:43)

IonQ projects 256 physical qubits with 12 logical in 2026, then 10,000 physical (800 logical) in 2027. Lightsync interconnects push that to 1,400 logical in 2028 – the Gidney threshold. By 2029 all papers are feasible; by 2030 two million physical qubits exist. IBM’s plan reaches 200 logical in 2029 and 2,000 logical by 2033. Both roadmaps land before NIST’s 2035 deprecation deadline. Karagiannis called the five-year overlap a “major problem.”

Detection Is Possible – If Anyone Looks

▶ Watch (30:43)

Shor and Grover leave unmistakable patterns. Shor uses quantum Fourier transforms and modular exponentiation that repeat identically across runs. Grover repeats Hadamard and oracle blocks thousands of times. These fingerprints appear at the circuit, compiler, transpiler, and even pulse-control level. But cloud providers like AWS and IonQ do not inspect user jobs. Karagiannis noted that if someone ran a botnet on AWS, it would get stopped. “Why can’t they?” he asked. New license agreements and terms of service will be needed before anyone monitors for attack execution.

Migration Lags: 6% OpenSSH and the 128-Bit Blindspot

▶ Watch (37:06)

Forescout’s scan found under 20% of internet servers on TLS 1.3. Only 6% of 168 million surveyed OpenSSH boxes run version 10, which enables post-quantum cryptography by default. NIST allows 128‑bit symmetric encryption for now. Karagiannis argued that Grover reduces 128 bits to a 64‑bit security level – the same range cracked by the EFF’s DES cracker in the 1990s. He urged everyone to default to 256‑bit symmetric encryption immediately.

Notable Quotes

shows under 2500 cubits are needed to attack Bitcoin Konstantinos Karagiannis · ▶ 6:15

we know the approximate date of a zero day. For the first time in computer history Konstantinos Karagiannis · ▶ 10:24

under 20% of servers on the internet are TLS 1.3 right now Konstantinos Karagiannis · ▶ 37:10

literally all you have to do is update to 10. That’s it. Konstantinos Karagiannis · ▶ 37:37

128 bits of security means that if I run Grover’s algorithm, it’s going to behave as if it was 64 bits of security Konstantinos Karagiannis · ▶ 38:34

Key Takeaways

  • IonQ projects 1,400 logical qubits by 2028, enough to crack RSA 2048.
  • NIST’s 2035 deprecation deadline leaves a five-year gap to quantum capability.
  • Under 6% of SSH servers use post-quantum cryptography despite a simple version update.

About the Speaker(s)

Konstantinos Karagiannis is Protiviti’s Director of Quantum Computing Services. He has been in infosec since the 1990s and a quantum computing pioneer since 2012. He hosts The Post-Quantum World podcast and serves as a Venerable Village Elder of DEF CON’s Quantum Village.