Deploy Bravely — Secure your AI transformation with Prisma AIRS
Table of contents

Brief: Cryptographically Relevant Quantum Computers (CRQC)

4 min. read
Table of contents

A cryptographically relevant quantum computer is one capable of breaking widely used public-key encryption by running algorithms like Shor's at scale.

It requires fault-tolerant operation, stable logical qubits, and enough coherence to complete deep quantum circuits. While no such machines exist today, their eventual arrival poses a direct threat to current cryptographic infrastructure.

 

How is a CRQC different from the quantum computers we have today?

Not all quantum computers are cryptographically relevant. That's an important distinction—because the machines available today are fundamentally limited.

Most current systems fall into a category called NISQ, or noisy intermediate-scale quantum.

These machines can run small-scale experiments. They can demonstrate quantum behavior. But they aren't stable or powerful enough to run cryptographic attacks. Not even close.

A large, vertically suspended quantum computing apparatus hangs at the center of a metallic laboratory frame, with multiple stacked circular tiers made of copper and gold-colored components connected by intricate wiring and cooling structures. The surrounding environment is dim, with structural beams, cables, and equipment framing the system. To the right, dark green text on a white background reads 'A current quantum computer at Google's quantum research lab in Santa Barbara, California.'

Why not?

Because NISQ devices are error-prone.

They can't correct those errors in real time. And they don't maintain coherent operations long enough to run large, structured algorithms. That means they're great for research, but not useful for breaking encryption.

A cryptographically relevant quantum computer—also called a CRQC—represents a completely different threshold. It's not just a bigger version of today's machines. It's a future class of hardware capable of performing complex, fault-tolerant quantum computations at scale.

Bold black text at the top reads 'Cryptographically relevant quantum computer (CRQC).' Beneath it, a paragraph in dark green explains that a CRQC is a future quantum computer capable of breaking public-key cryptography by running fault-tolerant quantum algorithms at scale. On the left, a section titled 'KEY TRAITS:' in purple lists bullet points describing fault-tolerant computation, logical rather than physical qubits, deep stable quantum circuits, long coherent runtime, and the ability to run Shor's algorithm at RSA/ECC scales. Below the list, a rounded gray box contains a lock icon and the text stating that CRQCs do not yet exist but will render current public-key encryption insecure once they do. On the right side, a stylized illustration shows a futuristic quantum computing platform with a circular purple quantum processor displaying a glowing atomic symbol, surrounded by digital panels, stacked purple server-like units, flowing data streams, and graphical interface screens.

In other words:

A CRQC doesn't exist yet. But it's the point where quantum computers stop being experimental and start becoming a real-world security threat.

 

What would a quantum computer need to become cryptographically relevant?

The term cryptographically relevant isn't about hype. It's about thresholds.

For a quantum computer to break today's public-key cryptography, it would need to reach a very specific level of maturity. And that bar is higher than most people think.

Here's why:

It's not enough to increase the number of qubits.

The machine also needs to be fault-tolerant.

That means it can detect and correct its own errors during a computation. Without that, deeper algorithms like Shor's simply don't work.

Plus, fault tolerance requires another step:

Logical qubits.

Note:
A qubit is the quantum version of a bit. Unlike classical bits, which are either 0 or 1, a qubit can exist in multiple states at once. A logical qubit is a stable, error-corrected version created by encoding one qubit's information across many physical qubits.

A CRQC would likely need thousands of logical qubits.

Achieving that could take millions of physical qubits. Because each logical qubit demands error correction across dozens or hundreds of physical qubits, depending on error rates.

Then there's runtime.

A CRQC would need to maintain coherent, error-corrected operation long enough to finish the full circuit depth required to factor an RSA key or solve an elliptic-curve discrete log problem.

To put it more simply: it would need to run complex quantum calculations cleanly and reliably—without drifting off course or breaking down. That means running cleanly across billions of quantum gate operations. Possibly for hours.

Important:

We're not just waiting for more power. We're waiting for stability, precision, and time. Those are the real barriers.

Until a quantum system can meet all three, it's not cryptographically relevant. It may be useful for other things. But it won't threaten encryption at scale. Yet.

| Further reading: What Is Q-Day, and How Far Away Is It—Really?

 

Which encryption methods would a CRQC break?

A cryptographically relevant quantum computer wouldn't disrupt everything. But it would break the cryptographic foundations that most digital systems rely on today.

Bold black text at the top center reads 'What a CRQC would break — and what it would weaken.' Two rounded rectangular panels are positioned side by side. The left panel has an orange circle at the top containing a prohibition symbol and is labeled 'Fully broken' in bold orange text with a subheading 'Via Shor's algorithm.' Below it, three items appear with small orange key icons: 'RSA,' 'ECC / ECDSA,' and 'DSA, ElGamal.' The right panel has an orange circle at the top containing an unlocked padlock icon and is labeled 'Weakened but still secure' in bold orange text with a subheading 'Via Grover's algorithm.' Three items follow with orange key icons: 'AES (128-bit),' 'AES (256-bit),' and 'SHA-2, SHA-3.' Beneath both panels, centered gray text with a warning icon reads 'Retrospective impact:' followed by the statement 'Any data encrypted with broken algorithms — even years ago — becomes vulnerable the moment a CRQC exists.'

Let's start with what would be directly compromised.

All widely deployed public-key cryptography would be broken.

That includes RSA, which is used for secure connections and key exchanges. It also includes elliptic-curve cryptography, which underpins modern authentication, digital signatures, and encryption schemes.

These algorithms rely on mathematical problems—like factoring and discrete logarithms—that quantum algorithms could solve efficiently at scale.

In other words:

Once a quantum computer can run Shor's algorithm against real-world key sizes, public-key cryptography as we know it becomes insecure.

Symmetric encryption is a different story.

It wouldn't be broken outright. But it would be weakened. A quantum computer could use Grover's algorithm to reduce the effective security level. That means 128-bit symmetric keys could offer just 64 bits of security in a quantum scenario. Hash functions would see similar reductions in collision or preimage resistance.

Critical point:

These changes don't happen gradually. The moment a CRQC exists, this impact becomes real. And it applies retroactively to any encrypted data that's already been captured. Which is why quantum security has become such a critical initiative.

| Further reading: Quantum Readiness: What It Means and How to Achieve It

 

Why does the CRQC threat matter now?

According to NIST IR 8547, Transition to Post-Quantum Cryptography Standards, encrypted data is already at risk because it can be captured today and decrypted later using quantum computers. Since many types of sensitive data remain valuable for years, this threat model is a key reason to begin migrating to post-quantum cryptography now.

It's easy to assume this is a future problem. After all, cryptographically relevant quantum computers don't exist yet.

But the threat is already active. Just in a different way.

The risk comes from what's called harvest now, decrypt later.

Encrypted data can be intercepted and stored today. That data might not be readable now. But once a CRQC becomes available, any old traffic encrypted with broken algorithms can be decrypted. The threat is delayed, not prevented.

Horizontal process diagram titled 'Harvest now, decrypt later (HNDL)' showing five sequential steps connected by arrows. Step 1, in a blue square, reads 'Data exfiltration' with subtext 'Steals encrypted traffic or files.' Step 2, in a lighter blue square, reads 'Cold storage' with subtext 'Keeps ciphertext for years.' Step 3, in an orange square, reads 'Advances in quantum computing' with subtext 'Waits for quantum systems.' Step 4, in a white square with a blue lock icon, reads 'Decrypt later' with subtext 'Shor's breaks RSA/ECC.' Step 5, in a purple square, reads 'Use the plaintext' with subtext 'Read, sell, or forge identities.' Small text under several steps notes 'Years can pass' to indicate elapsed time between stages.

This matters most for long-lived data. Think government records, medical histories, trade secrets, or source code. Anything with value that extends beyond a few years is at risk.

Here's why:

Even if the quantum threat is ten years away, the damage could already be done by then. And some secrets—like private keys or firmware signatures—don't expire. If they're ever compromised, the effect is permanent.

Digital signatures have the same issue. Once forged, trust breaks down. And you can't go back and revalidate the past.

In short:

The CRQC threat doesn't begin the day one gets built. It begins the moment your sensitive data gets captured—if it's protected by cryptography that won't hold up when quantum finally arrives.

| Further reading:

 

What are common misconceptions about CRQCs?

There's growing interest in quantum computing. But there's also confusion. Especially around what a cryptographically relevant quantum computer actually is.

So let's clear a few things up.

Bold black text at the top center reads 'Common misconceptions about cryptographically relevant quantum computers.' Below, three horizontal rows compare misconceptions on the left with realities on the right, separated by arrow icons inside dark circular buttons. Each row contains a white rounded rectangle for the misconception and a pale gray rounded rectangle for the reality. The first row lists the misconception 'CRQCs are just bigger versions of today's quantum computers,' followed by smaller text explaining that today's systems are small, noisy, not fault-tolerant, and that lab devices cannot maintain stable states long enough for cryptanalysis. The corresponding reality on the right states that CRQCs require thousands of logical qubits, deep error correction, and long coherent runtime, accompanied by an icon of interconnected circuit elements. The second row lists the misconception 'Quantum supremacy = cryptographic threat,' with subtext describing how supremacy demos show raw power but solve synthetic, not cryptanalytic, problems. The reality panel explains that a CRQC must run complex algorithms like Shor's at scale to break encryption and includes an icon of a chip running algorithms. The third row lists the misconception 'QKD replaces the need for post-quantum cryptography,' with subtext noting that QKD only secures communication channels, does not protect stored data or digital signatures, and requires specialized infrastructure. The reality panel states that post-quantum cryptography is still needed and that QKD does not replace it, alongside an icon showing binary code and a secure document.

A CRQC isn’t just a bigger version of today’s quantum devices.

It's not the same as what researchers use in labs now. Those systems are still noisy, limited, and experimental. CRQCs require something entirely different: stability, scale, and fault tolerance.

They also aren't the same as quantum-supremacy machines.

Demonstrating quantum advantage on a narrow task doesn't mean a system can run cryptographic attacks. That's a much higher bar.

Another common misconception? That quantum key distribution (QKD) replaces the need for post-quantum cryptography.

It doesn't. QKD is a communication protocol. It doesn't protect stored data or signatures. And it requires specialized infrastructure, not just a software update.

To sum up:

Not every quantum breakthrough is a cryptographic threat.

CRQCs are real, but they're specific. And understanding the distinction is what helps organizations prepare, without overreacting.

| Further reading: What Is Post-Quantum Cryptography (PQC)? A Complete Guide

INTERACTIVE EXPERIENCE: IS YOUR ORGANIZATION QUANTUM SAFE?
Dive into an overview of quantum threats, post-quantum cryptography, and NIST's new standards.

Launch experience

 

CRQC FAQs

A cryptographically relevant quantum computer (CRQC) is a fault-tolerant quantum system capable of breaking widely used public-key cryptography, such as RSA and ECC, by running algorithms like Shor’s at practical key sizes.
A CRQC requires thousands of stable logical qubits, deep circuit execution, and long-duration fault-tolerant computation. It must support quantum algorithms at scales sufficient to break current public-key encryption.
No. Current devices are NISQ-class: noisy, small-scale, and not fault-tolerant. They cannot run cryptographic attacks at meaningful key sizes.
No one knows for certain. Estimates vary, but most suggest CRQCs are at least a decade away. Hardware, error correction, and system reliability remain major barriers.
CRQCs would break RSA, Diffie–Hellman, and elliptic curve cryptography. These rely on problems that Shor’s algorithm can solve efficiently at scale.
No. Symmetric encryption would be weakened but not broken. Grover’s algorithm reduces its effective strength, but increasing key sizes can mitigate that.
Data encrypted today can be stored and decrypted later. Long-lived information and digital signatures are already at risk if protected by quantum-vulnerable algorithms.
It’s the practice of intercepting and storing encrypted data now, with the intent to decrypt it later once CRQCs become available.
No. QKD only protects live communication channels. It does not secure stored data or digital signatures and requires special infrastructure.
Supremacy or advantage refers to solving narrow tasks faster than classical computers. CRQCs must support deep, error-corrected quantum circuits that target cryptographic problems—an entirely different capability.
There’s no evidence of that. While governments are investing in quantum research, CRQCs remain beyond current engineering capabilities.
Inventory quantum-vulnerable systems, monitor cryptographic dependencies, and develop migration plans. Transitioning to quantum-resistant algorithms takes time and should begin before CRQCs emerge.
Related content
YouTube playlist: A CISO's Guide to Quantum Security
Binge a 6-video series breaking down why quantum computing is closer than you think but not as difficult.
Podcast: Threat Vector | Is the Quantum Threat Closer Than You Think?
Hear how to start your transition to quantum-resistant cryptography now.
Podcast: Packet Pushers | The Why and How of Making Your Infrastructure Quantum-Safe
Get the facts on making your organization post-quantum safe.
Blog: Palo Alto Networks Announces New Quantum Security Innovations
Learn about the new crypto inventory tool, quantum-optimized firewalls and PAN-OS 12.1 enabled quantum readiness.

Get the latest news, invites to events, and threat alerts