What a cryptographically relevant quantum computer is

A cryptographically relevant quantum computer, or CRQC, is a quantum computer able to run Shor's algorithm at sufficient scale and reliability to recover RSA and elliptic curve private keys in practical time. No CRQC is known to exist. The threshold is defined by error-corrected logical qubits and circuit depth, not by headline physical qubit counts.

What is a cryptographically relevant quantum computer?

A CRQC is defined by capability rather than by size. The requirement is a machine that can execute a specific long computation, Shor's algorithm, with enough error correction to hold the calculation together from start to finish. A quantum computer with a large number of unreliable qubits is not cryptographically relevant, and neither is a small, highly reliable one.

The term matters because it separates the security question from general quantum computing progress. Most quantum computing milestones reported in the technology press concern optimisation, simulation or benchmarking tasks that have no bearing on cryptography. A CRQC is a narrower and more demanding object.

How quantum computing breaks cryptography

Two algorithms are relevant, and they have very different consequences.

Shor's algorithm

Published by Peter Shor in 1994, this algorithm solves integer factorisation and the discrete logarithm problem in polynomial time. Those two problems are the security foundation of RSA, ECDSA, ECDH and Diffie-Hellman. A CRQC running Shor's algorithm recovers the private key from the public key, which means the affected algorithms are not weakened but defeated. Increasing key sizes does not help, because the required work grows slowly with key length.

Grover's algorithm

Grover's algorithm provides a quadratic speed-up for unstructured search, which reduces the effective strength of symmetric ciphers and hash functions. AES-128 falls to a 64-bit security level; AES-256 falls to 128 bits, which remains sound. Symmetric cryptography therefore requires a review of key lengths rather than replacement.

The asymmetry is the whole point. A CRQC removes the public key cryptography that underpins certificates, key exchange, code signing and authentication, while leaving bulk data encryption broadly intact.

What a CRQC actually requires

Three properties must hold simultaneously, and progress on each compounds progress on the others.

Logical qubits, not physical qubits

Physical qubits are noisy. Meaningful computation requires logical qubits, each assembled from many physical qubits using quantum error correcting codes. In superconducting architectures with nearest-neighbour connectivity, roughly a thousand physical qubits are needed per logical qubit. Architectures with better connectivity require far fewer. Headline physical qubit counts are therefore not comparable across hardware types and are a poor measure of cryptographic risk.

Sustained error correction across a long computation

Shor's algorithm against RSA-2048 is a deep circuit that must run for hours to days without accumulating fatal errors. This requires error rates below the fault-tolerance threshold, maintained continuously. Google's Willow result in December 2024 was significant not for its qubit count but because it demonstrated a logical qubit in the surface code that improved as the code grew, which is the property scaling depends on.

Algorithmic efficiency

The quantum software matters as much as the hardware. The resources required to break RSA-2048 have fallen substantially through algorithmic optimisation alone, with no change in the machines available.

Why quantum computing cryptography estimates keep changing

Published resource estimates for breaking RSA-2048 and P-256 have moved by more than an order of magnitude in six years.

The 2025 result reduced the requirement roughly twentyfold through quantum software optimisation. The 2026 neutral atom estimate reflects both a different hardware architecture, requiring approximately three to four physical qubits per logical qubit rather than a thousand, and further architecture-specific optimisation. Separately, Google reported an improved algorithm for breaking elliptic curve cryptography, providing a zero-knowledge proof of the result without publishing the method.

The planning implication is straightforward. Estimates have consistently moved in one direction, and each revision brings the threshold closer without any single hardware breakthrough being announced. Any quantum risk assessment that fixes the arrival of a CRQC at a single date is treating a moving quantity as a static one.

How we would know a CRQC exists

There is no single announcement to wait for. The indicators worth monitoring are technical and specific.

Logical qubit counts and logical error rates are the primary measure, in place of physical qubit totals. Sustained magic state distillation throughput matters, because it governs whether the non-Clifford gates Shor's algorithm depends on can be supplied at the required rate. Demonstrated factoring of general semiprimes without special structure would be decisive, as distinct from the small or specially constructed numbers used in laboratory demonstrations. Finally, watch for the completion of the remaining engineering step for each architecture rather than for gradual qubit growth, since the last missing capability is what converts a research device into a scalable one.

A useful counter-indicator also exists. Detailed public resource estimates for attacking deployed cryptosystems have been a reliable source of insight. Scott Aaronson has noted that researchers will eventually stop publishing them, to avoid informing adversaries, and that the point may already have passed. Reduced publication should be read as a signal in its own right rather than as evidence that progress has slowed.

Why the arrival may not be announced

A CRQC is a strategic intelligence capability before it is a commercial product. The first working machine will be expensive, scarce and operated by a state or a very large technology organisation, and there is no reason to expect its existence to be disclosed.

This produces an asymmetry that governs defensive planning. An adversary needs the capability once. A defender must have completed migration before that point, across an entire estate, including systems owned by suppliers. Because the defender's timeline is measured in years and the adversary's disclosure obligation is zero, migration cannot be scheduled against a confirmed arrival date.

Expert opinion reflects this uncertainty rather than resolving it. The Global Risk Institute's Quantum Threat Timeline Report published in March 2026 recorded that between 28 and 49 per cent of surveyed experts assigned a probability above 50 per cent to a CRQC existing within ten years. That is a wide distribution, and it is the correct input to planning: a range to be tested against, not a date to be relied on.

What a CRQC is not

Several developments are routinely reported as cryptographic threats and are not.

Quantum annealing machines, including those built by D-Wave, cannot run Shor's algorithm. They address optimisation problems and are not on a path to cryptographic relevance.

Quantum advantage or supremacy demonstrations use tasks chosen because they are hard for classical computers and easy for a specific quantum device. They say nothing directly about factoring capability.

Laboratory factoring records involving small integers or numbers with special structure do not scale. Factoring 21 with a bespoke circuit is not a step towards factoring RSA-2048.

Quantum key distribution is a defensive technology, not an attack, and it is not a substitute for post-quantum cryptography. It addresses key exchange over dedicated optical links and does nothing for authentication, code signing or data at rest.

What this means for migration planning

In practice, the CRQC threshold has almost no bearing on what an organisation should do in the next two years, and complete bearing on why it should start.

The constraint is rarely the algorithms. It is that organisations do not know where their cryptography is. Discovery of embedded keys, appliance firmware, hardcoded trust stores and supplier interfaces is the longest single activity in most programmes, and it is identical work whether a CRQC arrives in 2030 or 2040. It also delivers value independently, since the same cryptographic inventory supports audit, incident response and certificate outage prevention.

The sequencing question that the CRQC threshold does affect is priority. A distant threshold makes harvest now, decrypt later the dominant concern, favouring encryption and key exchange. A nearer threshold raises authentication, because a forged signature or compromised code signing key grants immediate access rather than retrospective disclosure. The revisions published through 2025 and 2026 have moved that balance towards authentication, which is why major platform providers brought their internal targets forward to 2029.

How Unsung helps

Unsung is a UK-based, vendor-neutral consultancy specialising exclusively in public key infrastructure and cryptographic systems, working across central government, defence, healthcare, financial services and critical national infrastructure.

We establish where quantum-vulnerable cryptography exists across an estate through our PKI health check and cryptographic bill of materials services, then design the target architecture and certificate lifecycle management capability needed to migrate on a schedule the organisation controls rather than one dictated by disclosure.

For the wider pattern that this transition follows, see our analysis of why every encryption algorithm eventually fails.

‍