A quantum computer is not a faster classical computer. Its advantage is structural: certain algorithms exploit quantum superposition and interference in ways that classical machines fundamentally cannot replicate. Understanding where quantum speedups exist — and where they don’t — is essential for evaluating which quantum applications will matter.
## Shor’s Algorithm: The RSA Threat
In 1994, Peter Shor demonstrated a quantum algorithm for integer factorization running in polynomial time — O((log N)³) gate operations. Classical algorithms for factoring require sub-exponential time, which effectively protects today’s RSA encryption for sufficiently large key sizes.
A quantum computer running Shor’s algorithm with roughly 4 million physical qubits (per Google’s 2022 estimate) could factor a 2048-bit RSA key in hours. This is why cryptographers worldwide are urgently deploying post-quantum cryptography standards — see [NIST PQC](https://csrc.nist.gov/projects/post-quantum-cryptography) and [Quantum Cryptography](https://sunqi.org/quantum-cryptography-en/).
Shor’s algorithm is built on the quantum Fourier transform and quantum phase estimation — subroutines that appear across many other quantum algorithms. The original paper is at [arxiv:quant-ph/9508027](https://arxiv.org/abs/quant-ph/9508027).
## Grover’s Algorithm: Square-Root Search
Lov Grover’s 1996 algorithm searches an unstructured database of N entries in O(√N) queries, compared to O(N) classically. The speedup is quadratic rather than exponential — less dramatic, but universally applicable to any search problem.
The cryptographic implication: brute-force attacks on symmetric ciphers become quadratically cheaper. A 128-bit symmetric key has only 64-bit security against a quantum adversary running Grover’s algorithm — which is why AES-256 is recommended for post-quantum security. Grover’s algorithm is proven optimal: no quantum algorithm can do better on unstructured search.
## The HHL Algorithm: Linear Systems
The Harrow-Hassidim-Lloyd (HHL) algorithm solves systems of linear equations in O(log N) time under certain conditions, compared to O(N³) classically. Linear systems underlie almost all scientific computing.
The catch: HHL requires the matrix to be sparse and well-conditioned, the input to be provided as a quantum state (loading classical data into a quantum state can itself be expensive), and the output is also a quantum state (hard to read out completely). These caveats significantly limit practical speedup in many real applications. The algorithm remains theoretically important but practically cautious.
## Variational Quantum Algorithms: Pragmatic NISQ-Era Approaches
While waiting for fault-tolerant hardware, researchers have developed variational algorithms that run on noisy current devices:
**VQE** (Variational Quantum Eigensolver): optimizes a parameterized quantum circuit to find molecular ground-state energies. Already demonstrated on small molecules.
**QAOA** (Quantum Approximate Optimization Algorithm): produces approximate solutions to combinatorial optimization problems. Quantum advantage over classical heuristics has not yet been established at practical scales.
**Quantum machine learning**: quantum neural networks and kernel methods work well on certain structured data types. See recent work at [arxiv:quant-ph](https://arxiv.org/list/quant-ph/recent).
## Where Quantum Wins (and Where It Doesn’t)
Quantum computers offer genuine exponential speedups for integer factorization and quantum simulation. They offer quadratic speedups for search. For many other problems — including most machine learning and optimization tasks — quantum advantage remains unproven or conditional. The promise is real, but the applications that will first matter in practice are narrow and specific.
For hardware context, see [Quantum Computing Hardware](https://sunqi.org/quantum-computing-hardware-en/) and [Quantum Simulation](https://sunqi.org/quantum-simulation-en/).
—
