[Cryptography] Two physics experiment questions

[Rod Van Meter]

On 2026/05/24 9:14, Jon Callas wrote:
>
>> On May 23, 2026, at 03:11, Peter Gutmann via cryptography<cryptography at metzdowd.com> wrote:
>>
>> I was updating the slides for my talk ("Why quantum cryptanalysis is
>> bollocks")

Love the humor and history, no surprise I don't agree with all the 
conclusions.

One request: can you put a date on your slides? We've studied them 
before, and had to forensically estimate a date.

<text cut in the interest of length>

>> Secondly, Shor's algorithm is over thirty years old, dating from before when
>> some of the people currently working on PQC stuff were born.  What triggered
>> the panic over the last few years?
> There are a number of things going on:
>
> (1) <shortened here and below to a few points I will respond to>

> (2) Over in the physics side, in particular what's called Quantum Information Science, they were working in earnest on QIS, and getting research. Inevitably, when physicists work on things they point in some direction to some societally useful thing. The real-world implications of physics advancements are important from a sociological/funding aspect. Why should we give them money? Well.... What?

It's worth pointing out that we now have a substantial engineering 
community involved in designing, building and programming quantum 
computers. The machines are real, and they work (with still-high error 
rates, but they work), though we are still a few years away from solving 
post-classical problems. Multiple companies have published roadmaps 
projecting fault-tolerant systems (with low-enough error rates) at 
useful scale in 2029.
https://qce.quantum.ieee.org/2026/
https://tqe.ieee.org/

A few of my friends and collaborators here in Japan are listed at
https://rdvlivefromtokyo.blogspot.com/2024/12/quantum-computer-architecture-work-in.html

>
> Shor's algorithm has an advantage that it's a thing. You can point to it, and it exists, unlike a lot of other QIS things were the actual interaction to the real world is vague at best. However, this is something that can be pointed to.
>
> "Why should we give you money? Whatcha gonna do with that quantum computer that affects the real world?"
>
> "Uhh, uhhhh, uhhh -- uhh, we could factor numbers! Yeah, that's it, we could factor numbers."
>
> "Why should we care?"
>
> "Because, ummm, ummm, encryption!"

Personally, I originally used Shor's algorithm as a study case not 
because I think it is good enough reason to drive an industry but 
because it's concrete and uses key techniques (arithmetic, quantum 
Fourier transform) that appear to be broadly applicable.

>
> Without that, they're struggling to explain things, even now. Recent QIS articles have had headlines like "Quantum computers will finally be useful" (Nature, Feb 2026), "Quantum computers turned out to be more useful than expected in 2025" (NewScientist, Dec 2025), and so on. Without Q-Day, this is pretty faint praise. I've read special magazine sections on QIS and other than cryptanalysis, useful things a quantum computer can do are vague and mealy-mouthed, with fewer results even than quantum cryptanalysis -- and we both know about those.

I always assumed that the other applications would be the reasons to 
build an industry. The other cases have not become as concrete as Shor 
as quickly as I anticipated, but good progress continues to be made on 
fundamental algorithmic techniques. One recent one is Decoded Quantum 
Interferometry, by Jordan et al. of Google.
https://arxiv.org/abs/2408.08292
My group has made a small contribution in this direction.
https://arxiv.org/abs/2504.18334

The best recent resource on quantum algorithms is this tome, 400+ pages 
cataloging numbers of qubits and gates needed for a very long list of 
algorithms in condensed matter physics, quantum chemistry, nuclear and 
particle physics, combinatorial optimization, continuous optimization, 
cryptanalysis (woo-hoo!), differential equations, finance, and machine 
learning with classical data.
https://arxiv.org/abs/2310.03011

> The panic over the last few years is driven by the success of the math side, combined with the lack of progress that folks like you and I have noted.

There has been tremendous progress on the quantum hardware side, which 
makes the news. QuEra and Google have both demonstrated that quantum 
error correction works and suppresses logical errors to below the level 
of physical errors. Still not at useful levels, but now it's "just" a 
matter of engineering.

Equally important, but not making as much news, is progress on quantum 
error correction and methods for fault-tolerant execution of gates. One 
of the most important gates is called a T gate, and it can't be executed 
directly in fault-tolerant systems, so it's executed indirectly with the 
help of a "magic state". For a decade or so, it was understood that the 
execution of the T state dominated runtime costs in time and space 
(resources). But a series of advances (many due to Craig Gidney of 
Google and his collaborators) over the last decade has brought that cost 
down by a factor of 10,000x since 1995 -- a HUGE improvement.
https://arxiv.org/abs/2409.17595

Quantum error correction (QEC) has advanced; the current trendy thing is 
qLDPC codes (being pushed by IBM and others), which have a code rate 
asymptotically approaching 1 as code distance is raised, whereas the 
popular surface codes don't. qLDPC codes require additional hardware 
capabilities, but promise big reductions in required hardware resources.

Programming models for FT systems in conjunction with advances in  QEC 
have also made huge advances in the last decade. Back in 2011 Dominic 
Horsman from my group, working with Devitt and Fowler, invented lattice 
surgery, which has now become such a part of the background that people 
use it without bothering to cite the original paper. Work since then has 
brought us Pauli-based computation (PBC), Game of Surface Codes (GoSC), 
Active Volume, and Extractors. See p. 48 of my slides here:
https://docs.google.com/presentation/d/1AxAbTODxzMYpK4czExcvhIckcX5b5VGd68r9gXrWFkE/edit?slide=id.g3e27a30b1cb_3_36#slide=id.g3e27a30b1cb_3_36

There has also been work on efficient circuits for arithmetic, a lot of 
it also done by Gidney and collaborators:

  * https://quantum-journal.org/papers/q-2018-06-18-74/
  * http://arxiv.org/abs/2407.17966
  * http://arxiv.org/abs/2505.15917


So I think it's fair to say that in the last decade the projected 
execution cost of Shor's algorithm at scale has come down by a factor of 
around a million.

> One of the threats to the Quantum Threat is that there are getting to be contrarian QIS physicists.
Contrarians have existed since the beginning of the field. As 
experimental success has continued, they have had to shift their arguments.
>   Some of them are muttering that Q-Day is harder than people think. Some are even saying radical things like it's not as big a threat as we thought -- there's a contrarian consensus that we don't need to worry about Grover's Algorithm at all for practical engineering considerations,
People have examined Grover for use against symmetric key systems, but I 
have always thought of those as sort of a negative case. People on this 
list should largely be reassured by those analyses.
>   and I read someone who said they didn't think a CRQC was going at all for anything bigger than RSA 2K. I don't think I agree, but that's how things are going.

Resources for Shor grow as L^3 for an L-bit key, so doubling the key 
length multiplies resource requirements by 8. The classical cost isn't 
negligible, especially when multiplied by the number of times this is 
done daily around the world, but I'd say the advantage stays with the 
defenders here. If you just want to raise the quantum cost 1000x, be my 
guest and use RSA-20480.

>   Without a sense of urgency, QIS is going to be like Fusion in that we all know it will happen eventually, and yet not anytime soon.
>
> There you go. That's what I think. Personally, though, I think that Q-Day will arrive, but no sooner than the 2050s, and that's at the earliest. I think quantum cryptanalysis is very much like fusion in that it's obviously possible but the engineering is hard enough that it may never be practical.
The machines are coming (cue the theme from Terminator). I'd say the 
question at this point is whether a viable, at least mostly 
self-sustaining commercial market develops before governments (China, 
UK, EU, Switzerland, Japan, Korea, Singapore; the U.S. is a total 
wildcard at this point) (in recent years, India has also dramatically 
ramped up investment, and ASEAN has been steady at modest scale, and the 
Middle East and Africa are new players with reason to be optimistic) 
lose patience with being a big supporter and the primary customer. There 
is already billions in VC money in the field, and a few commercial 
systems have been sold, but the primary supporter and customer remains 
governments today.
>   I think we'll see a home Mister Fusion before we'll see a Quantum PC.

I'm in favor of that.

--Rod

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://www.metzdowd.com/pipermail/cryptography/attachments/20260525/52317b8e/attachment.htm>