BSI study "The status of quantum computer development"

[Kaveh Bashiri]

Dear all,

I would like to draw your attention to the latest update (version 2.1)
of our ongoing BSI study "The status of quantum computer development",
which is available via the following link:
    https://bsi.bund.de/dok/study_status_quantum_computer
The study is conducted by Frank Wilhelm-Mauch (FZ Jülich) as project
leader in joint work with Rainer Steinwandt (University of Alabama in
Huntsville), Daniel Zeuch (FZ Jülich), Paul Lageyre (FZ Jülich) and
Susanna Kirchhoff (FZ Jülich).

The conclusion of this current version of the study is that quantum
computing is making steady progress towards cryptanalytic relevance
according to the reliable mainstream (fault-tolerant (improved) Shor
algorithm, executed either on a superconducting system with the surface
code or an ion-based system with the color code). Major roadblocks in
this scenario were resolved in 2024, bringing us a lot closer to this
goal even without large disruptions. The conservative estimate is that
cryptographically relevant quantum computers are likely to be available
within 16 years.

Moreover, there are now a plethora of new developments in error
correction and mitigation as well as hardware with the large progress in
neutral atoms. The landscape is constantly evolving and significant
changes could still occur, leading to unexpected surprises, and most of
the possible disruptive results in this context could accelerate the
development to below a decade.

Regarding NISQ algorithms, the study currently concludes that the
limited evidence available does not yet permit a conclusive assessment.
However, it makes a cautious assumption of low relevance for cryptanalysis.


Best wishes,
Kaveh (Bashiri) from BSI, Germany's Federal Office for Information Security

[Crick Waters]

If the link above gives trouble, try this link to the main BSI study page.

[John Mattsson]

Hi Kaveh,

 

Thanks for the link!

 

"The conservative estimate is that cryptographically relevant quantum computers are likely to be available within 16 years."

 

I interpret this as meaning that those who are conservative about security should prepare for CRQCs by 2040, while those conservative about their investments should not anticipate CRQCs by that time.

 

Nvidia CEO Jensen Huang recently said that the quantum computers won't be "very useful" for 15-30 years. And even a very useful quantum computer is far from being a CRQC.

https://www.msn.com/en-us/news/technology/quantum-computing-stocks-dive-after-nvidia-ceo-says-tech-15-30-years-away/ar-AA1x8Tix

 

And Nobel Prize Winner Demis Hassabis from Google thinks AI might make many quantum computing obsolete for many use cases, which if true could severely damp investment in quantum computing.

https://www.youtube.com/watch?v=MO6ZvA7U3F0

Regarding the report, I think you should update it to mention that Google created the first logical qubit in the surface code, which I think the coolest thing happening to quantum computing in a long time (even if Google tried their best to devalue their achievement with nonsense statements about Willow proving we live in a multiverse).
https://blog.google/technology/research/google-willow-quantum-chip/
https://www.nature.com/articles/s41586-024-08449-y

 

Another recent report worth reading is Samuel Jaques Landscape of Quantum Computing in 2024
https://sam-jaques.appspot.com/quantum_landscape_2024

 

Cheers,

John Preuß Mattsson

Expert Cryptographic Algorithms and Security Protocols, Ericsson Research

MSc Engineering Physics/Theoretical Computer Science

MSc Business Administration and Economy

[Kaveh Bashiri]

Dear John,

Thank you for your interest in our study and your useful remarks, which I would like to comment on.

- It seems that we did not formulate our conclusion clearly enough as we meant something else than you have interpreted. The "conservativeness" here is meant in the perspective of quantum information. That is, we believe that with high probability cryptographically relevant quantum computers will be available within 16 years.

- We took the impressive Google results into account for the mentioned update of the study; see Sections 8.5.2 or 8.5.3.1. This result is one of the main reasons why we went from 20 years to 16 years for our conservative estimate. There were post-deadline preprints by Google and the ETH that, albeit not as clear cut as the Nature paper, advance fault tolerant quantum computing even further. These will be discussed in the next edition.

- Thank you for the links, which are all very interesting. Especially, I would like to thank you for pointing out the comments by Sam, whose impressive work I really enjoy.

- Jensen Huang of course did not consult us :-) but we would like to remark two things: a) we are within the range of time that he talks about, albeit on the early side and b) we need to distinguish a market-ready, commercially viable quantum computer (which we speculate drives his mindset) from a government-operated computing infrastructure for cryptanalysis - which need not be commercially viable. In spaceflight, the former would be SpaceX and the latter would be Apollo. So it makes sense that we are on the early side of his interval.

If there are any further questions left, I would be happy to discuss.
Best wishes,
Kaveh (on behalf of the authors of the study)

Am 09.01.25 um 10:34 schrieb John Mattsson:

[D. J. Bernstein]

Kaveh Bashiri writes:
> - It seems that we did not formulate our conclusion clearly enough as we
> meant something else than you have interpreted. The "conservativeness" here
> is meant in the perspective of quantum information. That is, we believe that
> with high probability cryptographically relevant quantum computers will be
> available within 16 years.

It would be good to clarify this in the document. I had to do a similar
translation in, e.g., https://cr.yp.to/talks.html#2023.06.15 starting
from the "optimistic" and "pessimistic" predictions from the Global Risk
Institute. Having quantum computers come late is pessimistic for people
working on the technology, but optimistic for security!

> we need to distinguish a market-ready, commercially
> viable quantum computer (which we speculate drives his mindset) from a
> government-operated computing infrastructure for cryptanalysis - which need
> not be commercially viable.

I'd go a step further and say that it's important to distinguish
predictions regarding the timeline for three different events:

(1) Attackers carrying out quantum attacks.
(2) Public demos of quantum attacks.
(3) Quantum computers being useful for the public, not just attacks.

For a long time there has been evidence of investment in #1 being ahead
of public investment in quantum computation. See, e.g.,

https://cr.yp.to/talks.html#2012.09.24

(listing $2.2 million for defense contractor Raytheon as "one of many
publicly announced quantum-computing grants from government agencies"),
or the secret $80 million NSA budget described in

https://www.washingtonpost.com/world/national-security/nsa-seeks-to-build-quantum-computer-that-could-crack-most-types-of-encryption/2014/01/02/8fff297e-7195-11e3-8def-a33011492df2_story.html.

at the beginning of 2014. There are also various data points available
such as

https://irp.fas.org/commission/budget.htm
https://www.wired.com/2012/03/ff-nsadatacenter/

giving an idea of the growth of overall U.S. attack budgets. One can
then plug in models of the impact of investment upon technology
development: how much can you acccelerate technology development by
throwing lots of money at it? Obviously there are big uncertainties in
those models; also, less is known about the budgets for other attackers;
but being uncertain isn't a reason to ignore the risks.

The progress towards #2 is better documented, so timeline predictions
usually look at #2. I've been looking at technology fundamentals (e.g.,
progress in qubit stability, progress in quantum error correction,
progress in quantum algorithms) for many years as a way to predict #2.
My initial median estimate was 2032, and subsequent developments have
been on track; my current median estimate is also 2032; I'm on record in
2014, 2017, and 2023 placing public bets on this at even odds. From the
perspective of fundamentals, the latest Google announcement isn't a
reason to change median predictions: it's what was already expected
sometime around now from technology trends.

My current median estimate is that #1 is 3 years ahead of #2, giving
the unhappy prediction of 2029 for the first secret quantum attacks.
Could be later, could be earlier, but in any case people conflating #1
with #2 will be blind to these attacks ("I don't see a problem yet!").
The attackers won't tell us that they're carrying out quantum attacks.

As for #3, there's a vast literature on quantum algorithms, but most of
it provides far less speedup than Shor's algorithm does. There are many
low-memory combinatorial searches that benefit from Grover's algorithm,
but only once you're carrying out searches at a large enough scale to
overcome quantum overhead; the timeframe for that obviously won't be
anywhere near as fast as quantum factorization, quantum ECDL, etc.

Feynman's original observation was that quantum computers should be much
faster than conventional computers at simulating quantum physics. It's
plausible that useful applications of quantum computers for simulations
of a small number of atoms will take place on a timeframe similar to
public attack demos. But most applications are farther away.

(For any number theorists reading this: Yes, class-group computations
will be fast on a quantum computer. Good luck trying to convince rich
organizations to spend their quantum-computer time on this beyond the
attack applications. It'll be a long time before quantum computing is
democratized.)

For at least a decade we've seen claims of quantum speedups for big-data
problems. Whether those claims are phrased as "quantum machine learning"
or "quantum AI", they pretty much always rely on an implausible cost
model for quantum computation, a model that's sci-fi in a way that
Shor's algorithm isn't. In 2016, in response to a billion dollars of
big-data funding being allocated to quantum technology, I commented in

https://blog.cr.yp.to/20160516-quantum.html

that "the interesting quantum computations are not big-data
computations. They are _big computations on small data_. The big-data
computations that people carry out, and want to carry out, fundamentally
involve much more input and output, exactly the weak point of quantum
algorithms." (If anyone knows an earlier reference for this observation,
please let me know.)

In 2023, the second "key insight" stated in

https://cacm.acm.org/research/disentangling-hype-from-practicality-on-realistically-achieving-quantum-advantage/

(see also https://www.youtube.com/watch?v=ybmKJBTXudk and
https://arxiv.org/abs/2307.00523) was the same thing in pretty much the
same words: "Due to limitations of input and output bandwidth, quantum
computers will be practical for 'big compute' problems on small data,
not big data problems."

What the NVIDIA CEO said recently on an investor's call was that a
quantum computer is "good at small data big compute big combinatorial
computing problems, it's not good at large data problems". Apparently
this led to big stock drops for quantum computing, suggesting that at
least some of the current investment came from people who had been
misled by claims about quantum AI, whereas now there's broader public
recognition of how far away #3 is.

Will this produce what people call a "quantum winter", more than a minor
short-term drop of investment in quantum computing? Maybe, but I don't
think this matters much for cryptographic risk analysis: I'd expect the
impact on #2 to be less than the 3 years mentioned above, and I'd expect
a negligible impact on #1.

---D. J. Bernstein

[Kaveh Bashiri]

Dear all,

I would like to draw your attention to another update (version 2.2) of

our ongoing BSI study "The status of quantum computer development",
which is available via the following link:
https://bsi.bund.de/dok/study_status_quantum_computer

[Daniel Apon]

" If the qLDPC-code demonstrators that are currently being developed perform well, this could even go down to about 10 years  "

Wait - Huh?

This final line of the summary seems totally disjointed from everything else at https://www.bsi.bund.de/EN/Themen/Unternehmen-und-Organisationen/Informationen-und-Empfehlungen/Quantentechnologien-und-Post-Quanten-Kryptografie/Entwicklungsstand-Quantencomputer/entwicklungsstand-quantencomputer_node.html

Is it a reference to the comments on Page 98 of v2.2? Is the sole connection to https://journals.aps.org/prxquantum/pdf/10.1103/PRXQuantum.2.040101 ? Are there other materials worth citing here to explain that comment?

Kind regards,
Daniel

--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.
To view this discussion visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/ac798104-d2b4-425a-b8e0-e2615f721772%40gmail.com.