• Home
  • Industry Blog
  • What Are Quantum Computers Good For? The Limits of Quantum Advantage and Bitcoin

What Are Quantum Computers Good For? The Limits of Quantum Advantage and Bitcoin

Picture2wolfgang.png
Wolfgang Amadeus VitaleCrypto Protocol Expert
19 Nov 20269 Min

Breaking the elliptic curve cryptography (ECC) behind Bitcoin's signatures would take a quantum computer running Shor's algorithm, and the requirements for such a machine keep falling. Hardware is advancing at the pace the credible roadmaps have been presuming, and AI has entered the debate as a possible shortcut to the same break. 

On November 6, the research lab Physical Superintelligence (PSI) announced an AI-assisted proof of the Aaronson–Ambainis conjecture, an open problem about quantum speedups since 2008. Within days, posts on social media were declaring quantum supremacy dead. The proof shows nothing of the kind, but it brings into focus which quantum computing applications could deliver a genuine advantage**,** and why Bitcoin's cryptography ranks so high among them.

What did the Aaronson–Ambainis proof show about quantum advantage? 

The conjecture PSI's system proved concerns the quantum speedup, a measure of how much faster a quantum computer solves a problem than a classical computer. Aaronson and Ambainis asked whether that speedup could be exponential for yes-or-no questions about random data, with the quantum computer needing far fewer looks at the data than a classical computer. An exponential speedup is the largest kind, in which the gap grows ever wider as problems get bigger. 

The proof shows it cannot: on almost all random data, a classical computer never falls exponentially behind. An exponential speedup requires structure in the problem for the quantum computer to exploit. Shor's algorithm works because the mathematics behind Bitcoin's keys contains a hidden repeating pattern, which a quantum computer can find far faster than a classical one, and random data has no such pattern. 

The conjecture was widely expected to hold, and much of the attention went to the AI system that found the proof. If exponential speedups depend on structure, the case for quantum computers rests on which problems have it.

Which quantum computing applications offer an exponential speedup? 

A compendium published in October by researchers from Google Quantum AI, Microsoft, MIT, NVIDIA, JPMorganChase and CERN's Open Quantum Institute, among others, catalogs the problems with good evidence for more than a quadratic speedup, the smaller kind, in which a quantum computer needs roughly the square root of the classical effort, such as a million steps instead of a trillion. Two types of application stand out to me. For both, researchers have quantum algorithms whose speedup over the best classical methods known today is mathematically established. 

The first is cryptanalysis, the breaking of encryption and digital signatures, including the ECC behind Bitcoin's. The second is quantum simulation of molecules and materials for chemistry and drug discovery, where classical methods break down as systems grow. Cryptanalysis already has concrete targets in keys of a known size, while for quantum simulations there is more ongoing research on which molecular calculations would give a quantum computer a clear advantage over the best classical methods. 

Both applications remain far beyond what today's quantum computers can do. They need a large, error-corrected machine that does not exist yet, and Shor's algorithm has so far run only in simplified form on toy numbers such as 15, which it factors into 3 and 5.

Can quantum computers solve optimization problems? 

Pitches for quantum computing in finance and logistics usually involve optimization: routing supply chains, scheduling flights or balancing portfolios. Quantum algorithms can speed these problems up in principle, but for the problems companies actually need to solve, an advantage remains unproven, even on a powerful machine. The compendium finds strong evidence for only a few optimization problems, each with a specific mathematical structure, and weaker evidence for the broad versions used in supply chains and scheduling. I treat these applications as exploratory, promising enough to research but too uncertain to justify building a machine on their own.

Could Grover's algorithm help quantum computers mine Bitcoin? 

Some quantum algorithms are proven to work but offer only a quadratic speedup. The best known is Grover's search algorithm, and it has an obvious connection to Bitcoin, since mining is a search with no pattern to exploit: no one can predict which number will give a block a valid hash, so miners have to test them one after another. Grover's algorithm would need only about the square root of the number of tests, which might suggest that a quantum miner could outpace other miners and centralize mining. 

In practice it could not, because of cost overhead and speed. Each error-corrected quantum operation is far slower than a classical one, so needing fewer of them does not add up to a saving. Grover's search also parallelizes poorly, while mining runs on specialized chips that compute hashes in parallel at speeds well beyond any foreseeable quantum computer.

Why does Bitcoin's cryptography stay at the top of the list? 

Building a quantum computer at cryptographic scale will cost enormous sums, and the investors funding that effort expect a return. Of the quantum computing applications above, mining offers no return and optimization an uncertain one. Simulation is the most promising commercial use, and its first targets are still being mapped. Cryptanalysis has the most concrete targets of any application, from government and corporate communications to the ECC that secures Bitcoin holdings. 

Bitcoin is prominent enough among those targets that developers outside the crypto industry address it directly. Alice & Bob, which builds quantum computers, states in its October resource estimate that its results on the elliptic curve problem have practical consequences for Bitcoin's security. I draw no conclusion about the company's intentions, but the reference shows how central Bitcoin has become to the case for cryptanalysis. 

The Aaronson–Ambainis proof does nothing to weaken the quantum threat to Bitcoin, and it does not change my timeline. Quantum computers will be built for the problems where they hold a proven edge, and Bitcoin's signatures are one of them. For holders, the measure that matters is the progress of Bitcoin's own migration. We follow these developments on our Quantum Hub and track them each month in the Quantum Update.

Related Articles

  • Quantum Research

    Magic States and Record Error Rates: Quantum Error Correction Keeps Pace

    Google’s magic state cultivation and Quantinuum’s quantum error correction record moved quantum hardware forward. What do they mean for Bitcoin?

    29 Oct 20269 Min
  • Quantum Research

    Bunker Mode: Can AI Break Elliptic Curve Cryptography?

    Justin Drake warns AI could break Bitcoin's elliptic curve cryptography before quantum computers do. What cryptographers say and what holders should do.

    15 Oct 20267 Min
  • Quantum Research

    Bitcoin Quantum Readiness: A Guide for Institutional Holders

    Quantum readiness for institutional Bitcoin holders: which address types are exposed, what to ask your custodian, and what a chain split means for ETFs.

    30 Sep 20269 Min

Personal Support, Every Step

Our team of native experts are here to provide you with the tools, insights and support you need.

Opening hours

24/7 online

Monday to Friday: 7am to 7pm

contact@bitcoinsuisse.com

0800 800 008

Call us toll-free from Switzerland

+41 41 660 00 00

Call us from abroad