Quantum Computing and AI: A Conditional Promise and Early Preparation

In 2019 it was estimated that breaking 2048-bit RSA encryption would take about 20 million noisy qubits and roughly eight hours. In May 2025 Craig Gidney published a new estimate: fewer than a million qubits, and a running time of under a week. A large reduction in numbers, in exchange for a longer time. This news is about encryption, not artificial intelligence, and that is precisely where the confusion lies.

What distinguishes a quantum computer?

An ordinary computer carries information in a "bit" whose value is zero or one. A qubit draws on two properties of quantum physics, superposition and entanglement, which allow certain algorithms to explore many possibilities in a way an ordinary computer cannot imitate at reasonable cost. But this does not make a computer faster at everything. The advantage appears in problems of a particular structure, the best known being what Peter Shor showed in 1995: a quantum algorithm that factors integers and computes discrete logarithms in polynomial time. Known cryptographic systems have been built on these two problems.

Does it speed up AI?

It is tempting to think that training models is a huge calculation, so perhaps quantum computing would shorten it. But it is not that simple. In 2018 Ewin Tang presented a classical algorithm for the recommendation problem that performs the same task and trails the well-known quantum algorithm in this area by a polynomial, not exponential, margin, and she concluded that the latter does not in fact give an exponential speed-up over classical algorithms. That algorithm had been considered one of the strongest candidates for a quantum speed-up in machine learning. This does not mean no benefit is possible; it means that claims need to be examined problem by problem, and that the slogan "quantum AI" is no substitute for evidence.

An engineering obstacle also remains. Gidney's own estimate assumes a gate error rate of 0.1% and an error-correcting code that devotes a large number of physical qubits to protecting each logical qubit. It is a theoretical estimate on paper, not a description of an existing machine.

The nearer risk: encryption

What makes encryption different is that the harm may precede the event. The UK's National Cyber Security Centre (NCSC) describes an adversary who collects encrypted data today in order to decrypt it later, should they obtain a sufficiently capable quantum computer, and it considers this worthwhile mostly for very high-value information. The implication is that what should concern us is how long a secret must stay secret, not the expected date of the machine.

Preparation has in fact begun. In August 2024 the US National Institute of Standards and Technology (NIST) issued the first three post-quantum encryption standards (FIPS 203, FIPS 204 and FIPS 205), and the project lead said there is "no need to wait" and that integration takes time. The draft of its transition document (November 2024) proposes that RSA and elliptic-curve cryptography at the 112-bit security level be deprecated after 2030, and that all levels be disallowed after 2035. The schedule is an official proposal, not a prophecy, and we do not know whether the machine will lag behind it or get ahead of it.

What should be done?

• Take stock of the systems and data that rely on RSA and elliptic-curve cryptography, and of which must remain secret for many years.
• Begin with the longest-lived and highest-value data, then the rest.
• Follow system suppliers' adoption of the new standards, and consult a licensed cybersecurity specialist before any decision.
• Treat with caution marketing that promises to train models "at quantum speed".

Taking the means is a trust owed to people's data here. A quantum computer capable of breaking encryption may not arrive soon, but delay in preparing costs more than early action, and knowledge of the unseen belongs to God alone.