A Cryptographically Relevant Quantum Computer (CRQC) is a quantum computer powerful enough to break the public-key cryptography widely used today. Understanding what a CRQC is, why it matters, and how organizations are preparing for it is essential when planning the transition to post-quantum cryptography.
What Is a CRQC?
NIST defines a cryptanalytically relevant quantum computer as a device capable of using quantum algorithms to break a cryptosystem that is secure against classical (non-quantum) computers. The terms “cryptographically relevant” and “cryptanalytically relevant” are used interchangeably. In practice, a CRQC is a large-scale, fault-tolerant quantum computer capable of running Shor’s algorithm, which efficiently solves the integer factorization and discrete logarithm problems that underpin RSA, Diffie-Hellman, and Elliptic Curve Cryptography (ECC). The quantum computers available today are not cryptographically relevant. They lack the number of qubits and the error correction required to run these algorithms at a meaningful scale.
Why It Matters
Public-key algorithms such as RSA, ECDSA, and ECDH secure today’s Public Key Infrastructure (PKI). A CRQC would allow an attacker to derive private keys from public keys, enabling them to decrypt key exchanges and forge digital certificates and signatures. Symmetric algorithms such as AES and hash functions such as SHA-2 and SHA-3 are far less affected and are considered secure with appropriate key and output sizes. The threat is also not limited to the future. Adversaries can capture encrypted traffic today and store it until a CRQC is available to decrypt it, a technique known as “harvest now, decrypt later“. Data that must remain confidential for many years is already at risk.
How Close Are We?
No one knows exactly when a CRQC will be built, but the estimated resources required have dropped steadily. In 2019, researchers estimated that factoring a 2048-bit RSA key would require about 20 million noisy physical qubits. In 2025, Craig Gidney of Google Quantum AI reduced that estimate to fewer than one million noisy qubits running for less than a week. In 2026, Google published estimates showing that 256-bit elliptic curve cryptography could be broken in minutes on a superconducting CRQC with fewer than 500,000 physical qubits. Other theoretical work using different error correction codes and qubit technologies suggests even smaller machines may be sufficient. While no such system exists today, the trend is clear: the bar for building a CRQC keeps falling.
Preparing for a CRQC
The response to the CRQC threat is migration to Post-Quantum Cryptography (PQC), which uses algorithms believed to be secure against both classical and quantum computers. In August 2024, NIST published its first PQC standards: FIPS 203 (ML-KEM) for key establishment and FIPS 204 (ML-DSA) and FIPS 205 (SLH-DSA) for digital signatures. Vendors are already adopting these standards, and Microsoft AD CS now supports ML-DSA. In October 2026, NIST published the final version of IR 8547, which deprecates all quantum-vulnerable public-key algorithms, including RSA and ECC at every key size, after 2030 and disallows them after 2035. Because replacing cryptography across applications, devices, and PKI often takes years, organizations should begin inventorying their cryptographic dependencies and planning their migration now. For more details, see Post-Quantum Cryptography (PQC) in the Enterprise: Timeline and Readiness.
Additional Information
The following resources provide more detail on CRQCs and the transition to post-quantum cryptography.
- Post-Quantum Cryptography (PQC): Enterprise Resources and Guidance
- Post-Quantum Cryptography (PQC) in the Enterprise: Timeline and Readiness
- Microsoft AD CS Adds Post-Quantum Cryptography Support with ML-DSA
- Cryptanalytically Relevant Quantum Computer (NIST Glossary)
- Transition to Post-Quantum Cryptography Standards (NIST IR 8547)
- Module-Lattice-Based Key-Encapsulation Mechanism Standard (FIPS 203)
- Module-Lattice-Based Digital Signature Standard (FIPS 204)
- Stateless Hash-Based Digital Signature Standard (FIPS 205)
- How to Factor 2048 Bit RSA Integers with Less Than a Million Noisy Qubits (arXiv:2505.15917)
- Securing Elliptic Curve Cryptocurrencies Against Quantum Vulnerabilities: Resource Estimates and Mitigations (IACR ePrint 2026/625)
- Quantum-Resistant Cryptography (arXiv:2112.00399)
Start a Conversation
A CRQC may still be years away, but the time to prepare is now. I help organizations assess their quantum readiness, inventory where RSA and ECC are used across their PKI and remote access infrastructure, and build a practical plan for migrating to post-quantum cryptography. Tell me about your environment, and I’ll follow up, typically within one business day.








