How Many Qubits to Break Encryption? RSA, ECC, AES and SHA-256 Compared

How Many Qubits to Break Each Algorithm

Use this table: CSV · JSON · Permanent table link. Licensed CC BY 4.0; keep each row’s assumptions when you cite it.

Quantum resource estimates for RSA, ECC, AES and SHA-256 — SynergyX Research, https://synxcrypto.com/how-many-qubits-to-break-encryption.php#estimates

Two kinds of number appear in that table and they are not interchangeable. A logical qubit is an error-corrected qubit, the unit an algorithm is written in. A physical qubit is one noisy device on a chip, and hundreds of them may be needed to make one logical qubit, depending on the error rate and the code. Headlines that compare a 105-qubit chip with “4,099 qubits to break RSA” are comparing physical qubits with logical ones. For more on the distinction, see what a logical qubit is.

How Many Qubits to Break RSA-2048?

The figure most often quoted, 4,099, comes from Beauregard’s 2003 circuit, which runs Shor’s algorithm on an n-bit number with 2n+3 qubits. Those are logical qubits, and that circuit minimises qubits rather than time, so it says little about the machine an attack would need.

The practical estimates count physical qubits and runtime. In 2019 Craig Gidney and Martin Ekerå estimated that RSA-2048 could be factored in eight hours by a machine with 20 million noisy qubits. In May 2025 Gidney cut that to fewer than a million noisy qubits in less than a week, keeping the same assumptions: a square grid with nearest-neighbour connections, a 0.1% gate error rate, a one-microsecond surface-code cycle and a ten-microsecond control reaction time. The saving came from approximate residue arithmetic, storing idle logical qubits in “yoked” surface codes, and cheaper magic states through cultivation.

2026 brought two more reductions, both depending on newer error-correcting codes. The Pinnacle architecture, from Paul Webster and colleagues, uses quantum low-density parity-check codes to factor RSA-2048 with fewer than 100,000 physical qubits under the same error-rate and timing assumptions. A Caltech and Oratomic team including John Preskill showed that Shor’s algorithm can run “with as few as 10,000 reconfigurable atomic qubits,” with factoring RSA-2048 taking one to two orders of magnitude longer than their few-day elliptic-curve run. In Gidney’s estimates and in the neutral-atom study alike, fewer qubits cost more time.

How Many Qubits to Break RSA-4096?

Shor’s algorithm scales polynomially with key length. By Beauregard’s 2n+3 construction a 4096-bit key needs 8,195 logical qubits, twice the 2048-bit figure, and the gate count grows roughly with the cube of the key length, so doubling the key multiplies it about eightfold. None of the 2025 and 2026 papers above publishes a full physical estimate for RSA-4096, so any single number you see for it is an extrapolation. What is certain is the direction: RSA-4096 buys time, not safety, which is why post-quantum guidance replaces RSA rather than lengthening it.

How Many Qubits to Break Elliptic-Curve Cryptography?

Elliptic curves need fewer quantum resources than RSA at comparable classical strength, which is bad news for the cryptocurrencies that rely on them. The estimates for 256-bit curves such as Bitcoin’s secp256k1 and NIST’s P-256 have fallen from 2,330 logical qubits in Microsoft’s 2017 analysis to fewer than 1,200 or 1,450 in Google Quantum AI’s March 2026 paper, which fits the attack in fewer than 500,000 physical superconducting qubits running for minutes. Slower hardware trades size for time: IonQ researchers modelled 19,397 trapped-ion qubits for about 25.7 days, and the Caltech and Oratomic study a few days on 26,000 neutral atoms.

Google’s paper adds that the first fast-clock machines, superconducting or photonic, “would enable on-spend attacks on public mempool transactions” of some cryptocurrencies. We keep the full, annotated list of curve estimates in how many qubits it takes to break Bitcoin’s secp256k1, and what they mean for Bitcoin holders in is Bitcoin quantum resistant.

How Many Qubits to Break AES-256?

AES is a symmetric cipher, so Shor’s algorithm does not apply. The quantum attack is Grover’s search, which finds a key in roughly the square root of the number of guesses: about 2⁶⁴ iterations for AES-128 and 2¹²⁸ for AES-256. The 2016 estimate by Grassl, Langenberg, Roetteler and Steinwandt found the qubit count surprisingly modest, 2,953 logical qubits for AES-128 and 6,681 for AES-256, but the circuit depth enormous, because Grover’s iterations must run one after another and cannot be spread across many machines the way classical key searches can.

That is why governments treat symmetric cryptography differently. NIST’s transition report states that its symmetric standards “are significantly less vulnerable to known quantum attacks than the public-key cryptography standards,” and that every approved symmetric primitive with at least 128 bits of classical security is believed to meet at least its lowest post-quantum security category; AES-128, AES-192 and AES-256 map to categories 1, 3 and 5. The NSA’s CNSA 2.0 suite for national security systems specifies AES-256. More on the cipher itself is in our glossary entry for AES-256, and on the algorithm in Grover’s algorithm.

How Many Qubits to Break SHA-256?

The same logic holds for hash functions. Matthew Amy, Michele Mosca and colleagues estimated in 2016 that a Grover preimage attack on SHA-256 would need about 2^12.6 logical qubits, roughly 6,200, but a circuit depth of about 2^153.8 surface-code cycles, some 2^166.4 logical-qubit-cycles in total. Chaincode Labs’ 2025 report on Bitcoin reaches the plain conclusion that SHA-256 and RIPEMD-160 are “somewhat weakened, but by no means broken.” This is also why quantum computers do not threaten Bitcoin mining in the way they threaten its signatures; the detail is in Grover’s algorithm and Bitcoin mining.

Why Do the Estimates Keep Falling?

Almost none of the reduction since 2019 came from better hardware. It came from better algorithms and codes on paper:

• Arithmetic: approximate residue arithmetic cut the qubits Shor’s algorithm needs for RSA.
• Pamięć: “yoked” surface codes store idle logical qubits more cheaply.
• Magic states: cultivation replaces much of the space once spent on distillation factories.
• Codes: high-rate quantum LDPC codes, which neutral atoms and some new architectures can support, need far fewer physical qubits per logical qubit than the surface code.

Each estimate is a model of a machine that does not exist. The largest number ever factored with Shor’s algorithm is 21, and the most capable machines of 2025 run tens of logical qubits (see the largest number factored by a quantum computer). But the direction is consistent: every year the machine that breaks public-key cryptography gets smaller on paper, while the machine that breaks AES-256 or SHA-256 stays out of reach.

What Replaces the Vulnerable Algorithms?

NIST’s draft transition plan disallows RSA, ECDSA and EdDSA after 2035, and deprecates the weaker 112-bit variants after 2030. Their replacements are the 2024 post-quantum standards: ML-KEM (FIPS 203) for key establishment, and ML-DSA (FIPS 204) and SLH-DSA (FIPS 205) for signatures. Symmetric algorithms stay, at 256-bit strength where long-term security matters. Our explainer on NIST FIPS 203, 204 and 205 covers each standard, and ML-DSA versus SLH-DSA for cryptocurrency compares the two signature families.

Disclosure: synxcrypto.com is published by the team that builds SynX. Everything above this note is sourced to the studies listed below; the next paragraph describes our own project.

SynX takes the conservative end of that choice. Every SynX transaction is signed with SPHINCS+-SHAKE-128s, standardised as SLH-DSA, whose security reduces to hash functions, the family the table above shows quantum computers only weaken; key encapsulation uses Kyber-768 (ML-KEM). For how the underlying signature works, see SPHINCS+ signatures explained.

Sources

• S. Beauregard, “Circuit for Shor’s algorithm using 2n+3 qubits”, 2003.
• C. Gidney and M. Ekerå, “How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits”, 2019; C. Gidney, “How to factor 2048 bit RSA integers with less than a million noisy qubits”, May 2025.
• P. Webster et al., “The Pinnacle Architecture: Reducing the cost of breaking RSA-2048 to 100 000 physical qubits using quantum LDPC codes”, February 2026.
• M. Cain, Q. Xu, R. King, L. R. B. Picard, H. Levine, M. Endres, J. Preskill, H.-Y. Huang and D. Bluvstein, “Shor’s algorithm is possible with as few as 10,000 reconfigurable atomic qubits”, March 2026.
• H. Luo et al., “Quantum Algorithm for Elliptic Curve Discrete Logarithms with Space-Efficient Point Addition”, July 2026, revised September 2026.
• M. Roetteler, M. Naehrig, K. Svore and K. Lauter, “Quantum resource estimates for computing elliptic curve discrete logarithms”, 2017.
• M. Webber, V. Elfving, S. Weidt and W. K. Hensinger, “The impact of hardware specifications on reaching quantum advantage in the fault tolerant regime”, 2021; D. Litinski, “How to compute a 256-bit elliptic curve private key with only 50 million Toffoli gates”, 2023.
• R. Babbush, A. Zalcman, C. Gidney et al., “Securing Elliptic Curve Cryptocurrencies against Quantum Vulnerabilities”, Google Quantum AI, March 2026.
• T. Häner et al. (IonQ), secp256k1 in 26 days on a trapped-ion quantum computer, September 2026.
• M. Grassl, B. Langenberg, M. Roetteler and R. Steinwandt, “Applying Grover’s algorithm to AES: quantum resource estimates”, 2016 (Table 5).
• M. Amy, O. Di Matteo, V. Gheorghiu, M. Mosca, A. Parent and J. Schanck, “Estimating the cost of generic quantum pre-image attacks on SHA-2 and SHA-3”, 2016.
• S. Jaques, M. Naehrig, M. Roetteler and F. Virdia, “Implementing Grover oracles for quantum key search on AES and LowMC”, 2019/2020, on how NIST’s security categories are defined by the cost of key search against AES.
• NIST, IR 8547 (initial public draft), “Transition to Post-Quantum Cryptography Standards”, November 2024, Tables 2 and 6 and section 4.1.3.
• NSA, CNSA 2.0 FAQ, and the NSA-authored IETF draft CNSA 2.0 S/MIME profile listing the suite’s algorithms.
• A. Milton and C. Shikhelman, “Bitcoin and Quantum Computing: Current Status and Future Directions”, Chaincode Labs, May 2025.