<!DOCTYPE html>
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
</head>
<body>
<p><br>
</p>
<div class="moz-cite-prefix">On 2026/05/24 9:14, Jon Callas wrote:<br>
</div>
<blockquote type="cite"
cite="mid:D04B9C96-2E70-48A9-A191-5190F9595E17@callas.org">
<pre wrap="" class="moz-quote-pre">
</pre>
<blockquote type="cite">
<pre wrap="" class="moz-quote-pre">On May 23, 2026, at 03:11, Peter Gutmann via cryptography <a class="moz-txt-link-rfc2396E" href="mailto:cryptography@metzdowd.com"><cryptography@metzdowd.com></a> wrote:
I was updating the slides for my talk ("Why quantum cryptanalysis is
bollocks")</pre>
</blockquote>
</blockquote>
<p>Love the humor and history, no surprise I don't agree with all
the conclusions.</p>
<p>One request: can you put a date on your slides? We've studied
them before, and had to forensically estimate a date.</p>
<p><text cut in the interest of length></p>
<blockquote type="cite"
cite="mid:D04B9C96-2E70-48A9-A191-5190F9595E17@callas.org">
<pre wrap="" class="moz-quote-pre">
</pre>
<blockquote type="cite">
<pre wrap="" class="moz-quote-pre">
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?
</pre>
</blockquote>
<pre wrap="" class="moz-quote-pre">
There are a number of things going on:
(1) <shortened here and below to a few points I will respond to></pre>
</blockquote>
<br>
<blockquote type="cite"
cite="mid:D04B9C96-2E70-48A9-A191-5190F9595E17@callas.org">
<pre wrap="" class="moz-quote-pre">
(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?</pre>
</blockquote>
<p>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.<br>
<a class="moz-txt-link-freetext" href="https://qce.quantum.ieee.org/2026/">https://qce.quantum.ieee.org/2026/</a><br>
<a class="moz-txt-link-freetext" href="https://tqe.ieee.org/">https://tqe.ieee.org/</a></p>
<p>A few of my friends and collaborators here in Japan are listed at<br>
<a class="moz-txt-link-freetext" href="https://rdvlivefromtokyo.blogspot.com/2024/12/quantum-computer-architecture-work-in.html">https://rdvlivefromtokyo.blogspot.com/2024/12/quantum-computer-architecture-work-in.html</a></p>
<blockquote type="cite"
cite="mid:D04B9C96-2E70-48A9-A191-5190F9595E17@callas.org">
<pre wrap="" class="moz-quote-pre">
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!"</pre>
</blockquote>
<p>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.</p>
<blockquote type="cite"
cite="mid:D04B9C96-2E70-48A9-A191-5190F9595E17@callas.org">
<pre wrap="" class="moz-quote-pre">
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.</pre>
</blockquote>
<p>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.<br>
<a class="moz-txt-link-freetext" href="https://arxiv.org/abs/2408.08292">https://arxiv.org/abs/2408.08292</a><br>
My group has made a small contribution in this direction.<br>
<a class="moz-txt-link-freetext" href="https://arxiv.org/abs/2504.18334">https://arxiv.org/abs/2504.18334</a></p>
<p>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.<br>
<a class="moz-txt-link-freetext" href="https://arxiv.org/abs/2310.03011">https://arxiv.org/abs/2310.03011</a></p>
<blockquote type="cite"
cite="mid:D04B9C96-2E70-48A9-A191-5190F9595E17@callas.org">
<pre wrap="" class="moz-quote-pre"></pre>
<span style="white-space: pre-wrap">
</span></blockquote>
<blockquote type="cite"
cite="mid:D04B9C96-2E70-48A9-A191-5190F9595E17@callas.org">
<pre wrap="" class="moz-quote-pre">
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.</pre>
</blockquote>
<p>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.</p>
<p>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.<br>
<a class="moz-txt-link-freetext" href="https://arxiv.org/abs/2409.17595">https://arxiv.org/abs/2409.17595</a></p>
<p>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.</p>
<p>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:<br>
<a class="moz-txt-link-freetext" href="https://docs.google.com/presentation/d/1AxAbTODxzMYpK4czExcvhIckcX5b5VGd68r9gXrWFkE/edit?slide=id.g3e27a30b1cb_3_36#slide=id.g3e27a30b1cb_3_36">https://docs.google.com/presentation/d/1AxAbTODxzMYpK4czExcvhIckcX5b5VGd68r9gXrWFkE/edit?slide=id.g3e27a30b1cb_3_36#slide=id.g3e27a30b1cb_3_36</a></p>
<p>There has also been work on efficient circuits for arithmetic, a
lot of it also done by Gidney and collaborators:<br>
</p>
<ul
style="margin: 4px 0 4px 24px; padding: 0; list-style-position: outside">
<li style="margin: 2px 0; padding: 0; color: #1d1c1d"><span
draggable="true" style="color: inherit"><a target="_blank"
href="https://quantum-journal.org/papers/q-2018-06-18-74/"
rel="noopener noreferrer"
style="color: #1264a3; text-decoration: none"
class="moz-txt-link-freetext">https://quantum-journal.org/papers/q-2018-06-18-74/</a></span></li>
<li style="margin: 2px 0; padding: 0; color: #1d1c1d"><span
draggable="true" style="color: inherit"><a target="_blank"
href="http://arxiv.org/abs/2407.17966"
rel="noopener noreferrer"
style="color: #1264a3; text-decoration: none"
class="moz-txt-link-freetext">http://arxiv.org/abs/2407.17966</a></span></li>
<li style="margin: 2px 0; padding: 0; color: #1d1c1d"><span
draggable="true" style="color: inherit"><a target="_blank"
href="http://arxiv.org/abs/2505.15917"
rel="noopener noreferrer"
style="color: #1264a3; text-decoration: none"
class="moz-txt-link-freetext">http://arxiv.org/abs/2505.15917</a></span></li>
</ul>
<p><br>
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.</p>
<blockquote type="cite"
cite="mid:D04B9C96-2E70-48A9-A191-5190F9595E17@callas.org">
<pre wrap="" class="moz-quote-pre">
One of the threats to the Quantum Threat is that there are getting to be contrarian QIS physicists.</pre>
</blockquote>
Contrarians have existed since the beginning of the field. As
experimental success has continued, they have had to shift their
arguments.
<blockquote type="cite"
cite="mid:D04B9C96-2E70-48A9-A191-5190F9595E17@callas.org">
<pre wrap="" class="moz-quote-pre"> 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,</pre>
</blockquote>
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.
<blockquote type="cite"
cite="mid:D04B9C96-2E70-48A9-A191-5190F9595E17@callas.org">
<pre wrap="" class="moz-quote-pre"> 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.</pre>
</blockquote>
<p>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.</p>
<blockquote type="cite"
cite="mid:D04B9C96-2E70-48A9-A191-5190F9595E17@callas.org">
<pre wrap="" class="moz-quote-pre"> 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.</pre>
</blockquote>
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.
<blockquote type="cite"
cite="mid:D04B9C96-2E70-48A9-A191-5190F9595E17@callas.org">
<pre wrap="" class="moz-quote-pre"> I think we'll see a home Mister Fusion before we'll see a Quantum PC.</pre>
</blockquote>
<p>I'm in favor of that.</p>
<p>--Rod</p>
<p><br>
</p>
</body>
</html>