Hadamard Get the app

Can Quantum Computers Break SHA-256? What Grover and BHT Really Do

Can Quantum Computers Break SHA-256? What Grover and BHT Really Do — Hadamard

No, quantum computers cannot practically break SHA-256. The best known generic quantum attack, Grover’s algorithm, reduces SHA-256’s preimage resistance from about 256 bits to about 128 bits, which is still considered secure, and running that attack on real hardware costs far more than the headline number suggests.

So the honest answer to “can quantum computers break SHA-256” is that they weaken it in a bounded, well-understood way. This article explains what Grover’s algorithm and the Brassard–Høyer–Tapp (BHT) collision algorithm actually do, why hardware costs matter, what this means for Bitcoin mining and addresses, and how NIST uses SHA-256 as a yardstick for post-quantum security.

Can quantum computers break SHA-256? The short answer

SHA-256 bends, but it does not break. That makes it very different from RSA and elliptic-curve cryptography, which rely on factoring and discrete logarithms. Those problems have mathematical structure that Shor’s algorithm exploits, which is why public-key schemes built on them are considered broken by a sufficiently large quantum computer.

A well-designed hash function offers no comparable structure. The quantum attacks known against an ideal hash are generic search algorithms with polynomial speedups: a square root for preimages, a cube root (on paper) for collisions. A polynomial speedup can be absorbed by using enough output bits. An exponential one cannot.

Preimages vs. collisions: the two properties at stake

Quantum attacks on hashes target two different security properties, and confusing them is the source of most misleading claims.

  • Preimage resistance: given an output y, find any input x with H(x) = y. For an ideal n-bit hash, the generic classical cost is about 2^n evaluations, so about 2^256 for SHA-256.
  • Collision resistance: find any two different inputs that produce the same output. The attacker gets to choose both inputs, so this is easier: the classical generic cost is about 2^(n/2), or 2^128 for SHA-256.

Which property matters depends on the use. Commitments, address derivation and proof-of-work mining are preimage-style problems: the attacker must hit a specific output or target. Signing message digests is where collision resistance matters, because two colliding documents would share one signature.

Grover’s algorithm and hash functions: a square-root speedup, no more

Lov K. Grover introduced his algorithm in “A fast quantum mechanical algorithm for database search”, presented at STOC ’96. It searches an unstructured space of N possibilities in roughly the square root of N steps, a quadratic speedup over classical brute force.

Applied to hash functions, a preimage search on an ideal n-bit hash drops from about 2^n to about 2^(n/2) evaluations. As PostQuantum.com’s Grover explainer summarizes, SHA-256’s preimage resistance therefore goes from 256 bits to 128 bits, which remains secure.

Why a square root is the ceiling

Grover’s speedup is not just the best anyone has found so far. Boyer, Brassard, Høyer and Tapp proved tight bounds on quantum searching (Fortschritte der Physik, 1998), and C. Zalka showed in Physical Review A (1999) that Grover’s quantum searching algorithm is optimal. For a hash function with no exploitable structure, no quantum algorithm can do generic preimage search with substantially fewer queries.

From query counts to hardware

“2^128 evaluations” counts abstract hash queries. It ignores the cost of running SHA-256 as a reversible quantum circuit on error-corrected qubits. Amy, Di Matteo, Gheorghiu, Mosca, Parent and Schanck estimated these costs in “Estimating the cost of generic quantum pre-image attacks on SHA-2 and SHA-3” (SAC 2016).

According to the figures quoted in the “Quantum Horizon” evaluation of quantum threats to Bitcoin and Ethereum, a fault-tolerant SHA-256 preimage attack costs approximately 2^166 logical-qubit-cycles, potentially “as much as 275 billion times more expensive” than the simple query count suggests. We have seen this figure only as a quotation and have not checked it against the original paper. The two numbers are at least internally consistent: 2^166 divided by 2^128 is 2^38, which is roughly 275 billion.

Quantum collision attacks: BHT and its hidden cost

For collisions, the relevant algorithm comes from Gilles Brassard, Peter Høyer and Alain Tapp, then at Université de Montréal and Odense University. Their May 1997 paper, “Quantum Algorithm for the Collision Problem”, finds collisions in r-to-one functions with O((N/r)^(1/3)) expected evaluations.

For an n-bit hash, this translates on paper to about 2^(n/3) evaluations, roughly 2^85 for SHA-256. That looks like a meaningful drop from the classical 2^128. The catch is in what the algorithm needs to run.

As a CRYPTO 2021 talk on quantum collision attacks against reduced-round SHA-2 summarizes, BHT needs time 2^(n/3) plus 2^(n/3) of qRAM, a large memory that can be queried in quantum superposition. Without qRAM, the best option is parallel rho search with a time–space tradeoff of T = 2^(n/2)/S, the same scaling available to classical attackers.

Daniel J. Bernstein made this argument in detail in “Cost analysis of hash collisions: Will quantum computers make SHARCS obsolete?” (SHARCS 2009). He concluded that BHT has a fundamentally worse price-performance ratio than classical van Oorschot–Wiener parallel collision search, even under optimistic assumptions about quantum hardware.

The “64-bit” misconception

Some papers, such as this 2025 arXiv preprint, claim that Grover reduces SHA-256 to “around 64 bits.” That figure does not match either attack. Grover gives about 128 bits for preimages. BHT gives about 85 bits for collisions as a theoretical query count, and Bernstein’s cost analysis indicates it does not beat classical collision search in practice. The 64-bit number appears to come from mixing up collision and preimage resistance or from treating a theoretical bound as a practical attack.

Quantum Bitcoin mining and Bitcoin addresses

Can a quantum computer out-mine ASICs?

Bitcoin mining is a search for block headers whose double SHA-256 hash falls below a target, so Grover applies in principle. In March 2026, Pierre-Luc Dallaire-Demers and the BTQ Technologies team published “Kardashev scale Quantum Computing for Bitcoin Mining”, which concludes that out-mining the Bitcoin network with Grover would be physically impossible.

CoinDesk’s coverage reports that such an attack would require roughly the energy output of a star. We have not independently verified the paper’s specific qubit and energy estimates, so we do not repeat them here. The conclusion is a useful corrective to the kind of speculation discussed in our piece on the hype around quantum stocks.

HASH160 addresses: the thinnest hash margin

Bitcoin also hashes public keys into addresses using HASH160, a 160-bit construction. The Quantum Horizon paper notes that Grover cuts this from 160 to about 80 bits of preimage security, the thinnest margin among the hashes it examined. Like the 2^128 figure for SHA-256, this is a query count, and the hardware overheads described above still apply.

For cryptocurrencies, the more serious quantum concern is generally the signature layer, not the hash layer, because ECDSA rests on the discrete logarithm problem. That distinction is the design premise of BB84, the Layer 2 rollup on Ethereum built by Hadamard: accounts are one-time addresses based on hash commitments instead of ECDSA keys. The technical details are in the BB84 developer docs.

How NIST uses SHA-256 to define post-quantum security levels

The clearest sign that SHA-256 is not considered broken is that NIST uses it as a benchmark. In its call for post-quantum proposals, NIST defined five security categories relative to the cost of attacking AES and SHA, as summarized in this IACR ePrint paper:

NIST category Reference attack
1 AES-128 key search
2 SHA-256 / SHA3-256 collision search
3 AES-192 key search
4 SHA-384 / SHA3-384 collision search
5 AES-256 key search

SHA-256 collision search sits in Category 2, above AES-128 key search. Post-quantum signature and encryption schemes are measured against how hard it is to find a SHA-256 collision, which only makes sense if that remains hard in a quantum world. For the current approval status of specific hash functions during the post-quantum transition, check NIST’s own publications at csrc.nist.gov.

What developers should actually do

  1. Keep SHA-256 for preimage-style uses. Commitments, content addressing and similar uses retain a generic quantum margin of about 128 bits under Grover.
  2. Choose output length by the category you need. If your threat model calls for collision resistance at NIST Category 4, use SHA-384 or SHA3-384.
  3. Don’t expect a same-length switch to help. The generic quantum bounds depend on output length, so SHA3-256 and SHA-256 sit in the same NIST category.
  4. Prioritize signatures and key exchange. RSA and ECC are where quantum computers pose a structural threat. Options range from post-quantum algorithms to physics-based approaches covered in our article on the quantum internet and secure communication.
  5. Question low bit-security claims. Ask whether a number refers to preimages or collisions, and whether it counts queries or real hardware cost.

FAQ

Will quantum computers be able to mine Bitcoin faster than ASICs?

Not on any realistic hardware. A March 2026 analysis by Dallaire-Demers and the BTQ Technologies team concludes that out-mining Bitcoin with Grover’s algorithm would be physically impossible, with energy requirements reported as comparable to a star’s output.

If Grover halves security, is SHA-256 now only as strong as a 128-bit hash, and is that enough?

Grover halves the exponent, from about 2^256 to about 2^128 for preimages. A 128-bit generic margin is still considered secure, and fault-tolerant hardware overheads make the real attack far more expensive than 2^128 hash evaluations.

Should I switch from SHA-256 to SHA-384 or SHA-3 to be quantum-safe?

For most uses, SHA-256 is fine. Moving to SHA3-256 does not change the generic quantum bounds because the output length is the same. If you need NIST Category 4 collision resistance, SHA-384 or SHA3-384 is the reference choice.

Why is RSA/ECC considered broken by quantum computers but SHA-256 isn’t?

RSA and ECC rely on factoring and discrete logarithms, which Shor’s algorithm solves efficiently by exploiting their mathematical structure. Hash functions lack that structure, so quantum attacks only gain a provably limited square-root (or theoretical cube-root) speedup.

Sources