Quick disclaimer up front:
This is not a post claiming Grover’s algorithm makes it practical to break SHA‑256 or any modern hash function. That’s not the point.
What I am saying is that Grover applies to problems that are fundamentally meant to be solved, like Proof of Work (PoW), and in those contexts, it might actually be useful. Or at the very least, not “useless.” While its quadratic advantage is far less impressive than the exponential speed up of Shor’s it has a much wider range of potential uses.
I’m the author of the two papers this post is based on:
- “Quantum advantage on proof of work” (Array, 2022)
- “Quantum Blockchain Miners Provide Massive Energy Savings” (arXiv, 2023)
Both take a close look at what happens when you apply Grover’s algorithm, combined with some realistic engineering assumptions, to Bitcoin-style PoW.
A few more disclaimers:
- Do I think this is the biggest threat facing Bitcoin? No.
- Do I think it could become a concern one day (e.g. the 2047 date we mention in the first paper)? Probably not, and even then, it would only take some honest quantum miners to join the network to neutralise the threat.
- Do I think this is a realistic medium-term use case for quantum computers? Possibly.
There’s even a built-in self-reinforcing loop: as quantum miners join, they increase difficulty, which increases quantum advantage, which makes it more attractive for others to join.
What Grover does and doesn’t do
Grover gives a quadratic speedup for search problems. That’s well-known. The common pushback is that quadratic isn’t “enough”, especially for cryptographic tasks.
But that assumes the problem is supposed to be hard. PoW isn’t.
PoW problems are deliberately solvable. The goal isn’t to make them impossible, it’s to make them costly. Miners find valid blocks every 10 minutes. When the problem is meant to be solved regularly, even a square-root speedup matters.
So Grover is a surprisingly natural fit here. It’s not doing something magical, it’s just reducing the search space more efficiently in a setting where that actually helps.
Where this is a real attack vector
This isn’t a theoretical doomsday for Bitcoin, but it could be a serious issue for smaller PoW chains with low hash rates.
For example, Ethereum Classic, which has already suffered 51% attacks, could be vulnerable well before Bitcoin is. In those cases, a quantum miner doesn’t need to outpace the entire network, just a small portion of it.
Where else Grover might be useful (at a high level)
Grover’s algorithm doesn’t just apply to PoW, it can be useful anywhere you’re searching a large space for an answer, and you can check if the answer is correct. A few examples:
- Password cracking (in theory): If a password is hashed without salting or rate limits, Grover can speed up brute-force attacks. It’s not a major threat to well-designed systems, but the structure fits.
- Drug discovery or materials search: Trying to find a molecule that binds to a target or meets certain properties? Grover can reduce the number of test cases you need to run.
- Route or schedule optimisation: If you’re trying to find the best solution out of millions of combinations (e.g. shortest delivery route or most efficient shift rota), Grover helps narrow the field faster.
- Searching large databases or logs: Say you’re trying to find one record in a sea of data that meets a specific condition, Grover gives a consistent speedup.
These are all cases where brute-force search is expensive, but still feasible, which is exactly where Grover is meant to help.
Why this might matter for mining
In our second paper, we model the energy costs of running Grover-based PoW miners, not just in theory, but with real-world numbers for ASICs and quantum hardware.
We look at three quantum setups:
- A basic, non-error-corrected (NISQ) quantum miner
- A miner with one layer of error correction
- A miner with two layers of error correction
Even with basic setups, the potential energy savings are enormous, in the order of 10¹¹ to 10²¹ times lower energy use per block compared to a classical miner. This is largely because Grover takes fewer steps, and quantum hardware (especially reversible computation) has a much lower theoretical energy floor.
Add to that the fact that mining doesn’t require perfect success. Even a noisy quantum miner with a low success rate could still be profitable, as long as it runs faster or cheaper than classical hardware.
So why might Grover still be impractical?
Despite all that, there are still big hurdles:
- Oracle construction isn’t free: For Grover to work, you need to build a quantum version of your problem, including the full hash function circuit. That adds overhead.
- Depth and error rates: Quantum circuits need to be deep enough to run many Grover iterations. If your qubits decohere too quickly, the advantage vanishes.
- Fault tolerance is expensive: The more robust your quantum computer needs to be, the more error correction layers you need, and that adds massive complexity and physical qubit counts.
- Classical hardware is still improving: ASIC miners are already highly optimised. For Grover to win on performance or energy, it has to beat very good classical baselines.
- Return on investment may not justify the build: Even if quantum miners are technically better, the cost of building and running them might not be worth it, at least not for a while.
I’m keen to know if any of you think I’m completely out to lunch on this topic. Or whether there’s a reason I’ve missed that would mean its completely impractical to use Grover’s at all either as a PoW miner or for other limited use-cases.