← Q-Day

Explainer

How Many Qubits to Break AES-256? Estimates vs. Reality

qdayiscoming.com · November 17, 2026

Bar chart of logical qubits needed and time to run: RSA-2048 about 1,399 logical qubits and under a week, Bitcoin elliptic curves about 1,200 and minutes, both broken by Shor's algorithm; AES-128 about 2,953 logical qubits and about 89 billion years, AES-256 about 6,681 and about 2 × 10^30 years, both holding against Grover's algorithm

The qubit count for AES is in the same range as for RSA. The time is not (estimates as of November 17, 2026).

The best-known estimate puts a quantum attack on AES-256 at about 6,681 logical qubits. That number is not the problem: the attack would also need around 2145 steps in a row, so AES-256 stays safe against quantum computers.

Below: where that number comes from, why AES is so different from RSA, and what does break on Q-Day.

What AES is, and how a quantum computer would attack it

AES (Advanced Encryption Standard) is the lock on most stored and transmitted data: your disk, your password vault, the traffic of almost every website. It is symmetric: the same secret key locks and unlocks. AES-256 uses a 256-bit key, so there are 2256 possible keys.

The only known quantum attack on AES is Grover's algorithm. Lov Grover showed in 1996 that a quantum computer can find one item among N unsorted items in about √N steps, where an ordinary computer needs on the order of N (Grover, 1996).

Think of a phone book with a million names in random order. You would check about half a million names on average. Grover's method needs about a thousand steps. That sounds dramatic. But for a key, the square root only halves the length: 2256 keys become about 2128 steps. That is still an astronomical number.

Compare that with RSA. Shor's algorithm does not search at all. It uses the mathematical structure of RSA to calculate the private key directly. That is why RSA falls in days and AES does not.

The estimate: 6,681 logical qubits

In 2015, Markus Grassl, Brandon Langenberg, Martin Roetteler and Rainer Steinwandt built complete quantum circuits for Grover's attack on AES and counted every part (Grassl et al., arXiv:1512.04965). Their table 5 (qubits and depth) and section 3.4 (Grover rounds) give:

KeyLogical qubits · steps in a row (circuit depth) · Grover rounds
AES-1282,953 qubits · 1.16 × 281 · π/4 × 264
AES-1924,449 qubits · 1.33 × 2113 · π/4 × 296
AES-2566,681 qubits · 1.57 × 2145 · π/4 × 2128

A logical qubit is an error-corrected qubit built from many physical ones. Later work found other trade-offs: Samuel Jaques, Michael Naehrig, Martin Roetteler and Fernando Virdia designed AES circuits with less depth, at the cost of more qubits (Jaques et al., Eurocrypt 2020). The picture stays the same: the qubit count is in the thousands, the number of steps is out of reach.

Why the qubits are not the hard part

For RSA-2048, Craig Gidney of Google estimated 1,399 logical qubits and less than a million physical qubits, running for under a week (Gidney, arXiv:2505.15917). So AES-256 needs only about five times as many logical qubits. A machine that breaks RSA would not be far off in size.

The difference is time. Our own rough calculation: 1.57 × 2145 is about 7 × 1043 steps. Even at a generous million steps per second, that takes about 2 × 1030 years. AES-128, with 1.16 × 281 steps, would take about 89 billion years on one machine.

Can you split the work over many machines? Only a little. Christof Zalka proved that Grover's search gains nothing beyond dividing the keys among independent machines (Zalka, 1999). With a million machines, the search gets only about a thousand times faster. AES-128 would still take some 89 million years, on a million quantum computers that each hold thousands of logical qubits.

For scale: the largest number of logical qubits we have seen measured in a benchmark is 8, in a study by Sandia with Quantinuum and NVIDIA in September 2026 (Proctor et al., arXiv:2609.12146). Our Q-Day tracker follows that number.

What breaks and what does not

CryptographyQuantum attack and what the sources say
RSA-2048Shor. Breaks: 1,399 logical qubits, under a week (Gidney 2025). See how many qubits to break RSA-2048
ECC (Bitcoin)Shor. Breaks: at most 1,200 logical qubits and under 500,000 physical qubits, in minutes (Google Quantum AI et al., 2026). See how many qubits to break Bitcoin
AES-128Grover. Holds: NIST counts it as post-quantum security category 1, and does not expect to move away from AES (NIST IR 8547, table 6 and §2.1.3)
AES-256Grover. Holds: NIST category 5, the highest. The NSA requires AES-256 in its quantum-resistant CNSA 2.0 suite (NSA, CNSA 2.0 FAQ)
SHA-256Grover. Holds: NIST places collision search on a 256-bit hash in category 2 (NIST IR 8547, table 1)

The NSA puts it plainly: symmetric algorithms "are considered secure, provided the key size is sufficiently large." NIST writes that its symmetric standards are "significantly less vulnerable to known quantum attacks" than public-key cryptography (NIST IR 8547, section 4.1.3).

What we do not know

Better attacks. Zalka's proof is about searching without structure. AES does have structure. We know of no published quantum attack on full AES that does much better than Grover. If one appears, this picture changes.

Cheaper circuits. Estimates for RSA fell from 20 million physical qubits in 2019 (Gidney and Ekerå) to under a million in 2025. AES circuits can get cheaper too. But a cheaper circuit does not remove the 2128 Grover rounds.

Physical qubits. Grassl and colleagues count logical qubits only. Gidney's RSA design uses 897,864 physical qubits for 1,399 logical ones: about 640 per logical qubit on average, overhead included (our own calculation). For AES, nobody has published a comparable full count that we have checked.

What this means for you

A file, disk or backup encrypted with AES-256 holds up against quantum computers. You do not need to re-encrypt it.

The catch is how the AES key reaches the other side. On the internet, that key is usually agreed with RSA or elliptic curves. Someone who records the traffic today could later work out that key with Shor's algorithm and read everything: harvest now, decrypt later. So the weak spot is not AES, but the public-key step around it. That is what post-quantum cryptography replaces.

When could that public-key step fall? Forecasts differ and each has a name attached. The Q-Day countdown runs to the earliest.

Sources