Quantum Algorithms

A quantum algorithm is a step-by-step procedure — built from qubits, gates, and circuits — designed to solve a problem in a way that takes advantage of superposition, entanglement, and interference. Not every problem benefits from a quantum approach, but for the right problems, the speedup can range from modest to breathtaking.

What makes an algorithm "quantum"?

At a technical level, a quantum algorithm is simply a quantum circuit: a specific sequence of gates applied to a set of qubits, followed by measurement. What makes it interesting is how those gates are arranged — the goal is to use interference so that, by the time you measure, the probability of getting a useful answer is much higher than it would be by chance.

A useful mental model: a quantum algorithm doesn't "try every possibility and pick the best one." Instead, it arranges probability amplitudes so that wrong answers interfere destructively (canceling out) while the right answer interferes constructively (reinforcing) — making it the most likely outcome when you measure.

Categories of quantum speedup

Quantum algorithms are often grouped by the type of speedup they offer over the best known classical algorithms:

• Exponential speedup — the quantum algorithm's running time grows polynomially with problem size, while the best classical algorithm grows exponentially. Shor's Algorithm for factoring is the most famous example.
• Quadratic speedup — the quantum algorithm is roughly the square root of the classical running time. Grover's Algorithm for searching is the classic example: a problem that takes N steps classically takes roughly √N steps quantumly.
• No speedup (or unknown) — for many problems, no quantum algorithm is known to beat the best classical approach. Identifying which problems fall into which category is an active area of research.

Two foundational algorithms

Two algorithms, both developed in the 1990s, remain the most widely-referenced examples of quantum advantage — and both are covered in dedicated articles on this site:

• Shor's Algorithm — efficiently finds the prime factors of large numbers, threatening widely-used encryption methods.
• Grover's Algorithm — searches through unsorted data quadratically faster than any classical method.

Beyond Shor and Grover

Modern quantum computing research extends well beyond these two landmark algorithms:

• Variational algorithms (like VQE — the Variational Quantum Eigensolver) combine a quantum computer with a classical optimizer, and are considered promising for near-term "noisy" hardware because they can tolerate some errors.
• Quantum simulation algorithms directly simulate the behavior of molecules and materials — arguably the most natural application of quantum computers, since Richard Feynman's original motivation was that quantum systems are hard for classical computers to simulate.
• Quantum machine learning algorithms explore whether quantum circuits can speed up certain components of machine learning, such as linear algebra operations used in training models.

Why algorithm design matters so much

Unlike classical computing, where almost any problem can eventually be solved by "just writing more code," quantum speedups are carefully constructed and problem-specific. Finding a new quantum algorithm with a genuine speedup is a significant research achievement — which is part of why, decades after Shor's and Grover's algorithms, the list of algorithms with proven, dramatic speedups remains relatively short.

What's next?

Let's look at the two landmark algorithms in detail, starting with the one that put quantum computing on the map for cybersecurity.

Continue to: Shor's Algorithm →

Frequently Asked Questions

Do quantum algorithms always run on a quantum computer alone?

Not necessarily. Many practical near-term approaches are hybrid: a classical computer handles most of the work, occasionally calling a quantum processor to perform a specific sub-task — similar to how a CPU might offload certain calculations to a GPU.

Can any classical algorithm be converted into a quantum one?

Any classical computation can, in principle, be run on a quantum computer (quantum computers are at least as powerful as classical ones). However, simply "porting" a classical algorithm rarely produces a speedup — genuine quantum advantage usually requires fundamentally rethinking the approach to exploit superposition, entanglement, and interference.

How do I know if my problem could benefit from a quantum algorithm?

As a rough guide, problems involving large-scale search, optimization, factoring, or simulating quantum systems (like molecules) are the most promising candidates. Problems that are already efficiently solvable classically, or that are inherently sequential, are less likely to benefit.