Quantum Algorithms: Power and Limitations

A quantum computer is only as useful as the algorithms it can run. Over three decades, researchers have identified a handful of algorithms where quantum machines offer a true advantage, plus a class of “hybrid” methods designed for today’s imperfect hardware. This article explains the most important algorithms along with the error correction machinery that will eventually enable them to run at scale. Throughout, the goal is to be precise about how much speedup each algorithm truly offers — because the differences are vast.

Shor’s Algorithm: Factoring and the Cryptographic Threat

The Problem. Finding the prime factors of a large number. Classical computers can multiply two large prime numbers with ease, but reversing that process — factoring the product back into its prime constituents — is believed to take exponential time. The entire security of RSA encryption, which protects HTTPS, digital signatures, and much of cryptocurrency, relies on this difficulty.

The Quantum Solution. Shor’s algorithm cleverly redefines the factoring problem into finding the period of a mathematical function, a task at which quantum computers excel thanks to the quantum Fourier transform.

The Speedup. Exponential. While a classical method requires approximately O(exp(∛n)) steps, Shor’s algorithm needs about O(n³). This is the spectacular speedup that gives quantum computing its formidable reputation.

Reality Check. No quantum computer has yet factored a number larger than 21 using Shor’s algorithm. An effective attack on RSA-2048 would require approximately 1,400 logical qubits (error-corrected qubits) — and millions of physical qubits in early designs, although recent optimizations have cut physical qubit requirements to around and below one million. Expert surveys place the probability of a cryptographically relevant quantum computer emerging within ten years at approximately 28–49%. (See Quantum Threat Timeline Report 2025.)

Grover’s Algorithm: Faster Search

The Problem. Finding a specific item in an unsorted database of N items.

Classical Cost. O(N) — in the worst case, you have to check every item.

Quantum Cost. O(√N), using a technique called amplitude amplification.

The Speedup. Quadratic. For a database of a trillion items, that’s the difference between a trillion steps and a million steps — significant, but far less spectacular than Shor’s exponential speedup.

Grover’s algorithm is more general than Shor’s: it applies to almost any search or constraint satisfaction problem and appears as a subroutine within many other quantum algorithms. Its catch is that you need an efficient “oracle” — a problem-specific quantum circuit capable of recognizing the correct answer — which isn’t always easy to construct. (See Quantum Algorithms for Beginners.)

VQE: Quantum Chemistry on Near-Term Hardware

Variational Quantum Eigensolver (VQE) targets a different goal: finding the lowest energy state (ground state) of a molecule, which is fundamental to drug discovery and materials science.

VQE is a hybrid algorithm. The quantum computer prepares a trial state (an “ansatz”) and measures its energy; then a classical optimizer adjusts the parameters of the trial state to drive the energy lower, iterating until convergence. Because the quantum circuits are kept shallow, VQE tolerates the noise of current hardware relatively well, which is why it is one of the most actively used quantum algorithms today.

However, its weaknesses are real. The classical optimization loop is slow, and deeper circuits encounter the “barren plateau” problem, where the optimization landscape flattens and training stalls. A true quantum advantage over the best classical chemistry methods has yet to be demonstrated for practically relevant molecules. Still, progress is concrete: in 2026, IBM and Cleveland Clinic used a quantum-classical hybrid workflow to simulate the 303-atom Trp-cage miniprotein on IBM’s Heron processor — a first step towards protein-scale quantum chemistry. (See Quantum Computing × Drug Discovery 2026.)

QAOA: Approximate Optimization

Quantum Approximate Optimization Algorithm (QAOA) addresses combinatorial optimization problems — problems like MaxCut, scheduling, and the traveling-salesman problem. Like VQE, it is a hybrid algorithm: it alternates between two types of quantum evolution and uses a classical loop to refine parameters, then measures to extract an approximate solution.

An honest assessment is cautious. QAOA’s solution quality improves with circuit depth, but depth is limited by decoherence on real hardware. More importantly, classical optimization solvers — branch-and-bound, genetic algorithms, modern heuristics — are extremely good, so the bar for demonstrating a quantum advantage is very high, and evidence to date is limited. QAOA is a promising research direction, not a settled victory. (See Frontiers’ foundational article.)

Quantum Error Correction and Fault Tolerance

Every algorithm above shares a common enemy: errors. Qubits decohere and gates malfunction, and these errors accumulate until the computation becomes meaningless. Quantum error correction (QEC) is the answer, and it is the most critical enabling technology for the entire field.

The core idea is to spread the information of a reliable logical qubit across many noisy physical qubits, so that errors can be detected and corrected before they corrupt the result. Two families of codes dominate:

Surface code. A two-dimensional lattice of physical qubits encodes each logical qubit. They are well-understood and require only short-range, nearest-neighbor connections — well-suited for superconducting chips. The cost is steep: approximately 1,000 physical qubits per logical qubit.

LDPC code (low-density parity-check). These require some long-range connections between qubits, making them a natural fit for trapped-ion and neutral-atom platforms. In return, they drastically cut the overhead, potentially requiring only 10–100 physical qubits per logical qubit instead of 1,000.

The phrase to watch for is fault tolerance: the regime where adding more physical qubits actually reduces the overall error rate, rather than introducing more noise than it corrects. Crossing that threshold is the dividing line between today’s noisy machines and tomorrow’s useful ones.

Several 2026 results suggest this transition is underway:

• Google’s Willow achieved the first “beyond breakeven” milestone, where logical qubits live 2.4 times longer than their constituent physical qubits, with errors genuinely suppressed as the code grew larger.
• IBM’s Quantum Loon demonstrated real-time error decoding in under 480 nanoseconds using qLDPC codes — ten times faster than previous methods, achieved a year ahead of schedule.
• QuEra verified 96 logical qubits on 448 physical atoms with a 2:1 qLDPC encoding scheme, showing real overhead savings.
• Iceberg Quantum’s Pinnacle architecture claimed it could cut the number of physical qubits needed for RSA-2048 from 20 million to under 100,000.

(See Quantum Low-Density Parity-Check (qLDPC) Codes.)

Key Takeaways

Quantum algorithms fall into two camps. The first — Shor and Grover — offer demonstrable, sometimes spectacular, speedups but require large, error-corrected machines that do not yet exist. The second — VQE and QAOA — run on today’s noisy hardware but have yet to outperform the best classical methods on practical problems. Bridging the gap between the two camps is the task of error correction. The 2026 milestones suggest that bridge is finally being built, though fully crossing it is still many years away.

References

• PostQuantum: Quantum Threat Timeline Report 2025
• Blockchain Council: Quantum Algorithms for Beginners
• Morning Glory Sciences: Quantum Computing × Drug Discovery 2026
• Frontiers: Quantum computing — foundations, algorithms, and emerging applications
• PostQuantum: Quantum Low-Density Parity-Check (qLDPC) Codes