What is a Quantum Algorithm?

Overview

A quantum circuit is a description of gate operations. A quantum algorithm is a strategy that uses circuits + measurement + classical interpretation to extract information about a problem.

This distinction matters because the “algorithmic” part is not the gates themselves—it’s how you structure evolution so that measurement reveals the information you want.

Quantum algorithms are built around three ideas:

• interference: amplitudes can add or cancel,
• phase: information can be stored in phase and later converted into observable differences,
• measurement: you only get samples, so you design the circuit so the desired answers become likely.

Intuition

Think of a quantum algorithm as “probability sculpting.”

1. You start with a state that spreads amplitude across many possibilities.
2. You apply transformations that encode problem structure into relative phase and amplitude relationships.
3. You apply further transformations that cause constructive interference for “good” answers and destructive interference for “bad” answers.
4. You measure and get a classical output.

The key is step (3): quantum algorithms rarely “compute and read out everything.” Instead they engineer interference patterns so that measurement is biased toward useful outputs.

Why not all problems benefit?

• Measurement gives samples, not the full internal state.
• If the problem requires reading an exponential amount of information, quantum mechanics doesn’t let you magically extract it from one measurement.
• Many problems don’t have a known way to encode structure into phase/interference in a way that measurement can reveal efficiently.

So the quantum advantage question is: does the problem have structure that can be turned into phase patterns and then into measurable bias?

Formal Description

A typical (idealized) quantum algorithm has a hybrid structure:

1. Initialization: prepare an $n$-qubit input state $|\psi_0\rangle$.
2. Unitary processing: apply a circuit unitary $U$ to get

$$|\psi\rangle = U|\psi_0\rangle.$$

3. Measurement: measure (some or all) qubits, producing a classical outcome $x$ sampled from the distribution

$$P(x)=|\alpha_x|^2\quad\text{if }|\psi\rangle=\sum_x \alpha_x|x\rangle.$$

4. Classical post-processing: compute the final answer from measured samples (possibly using many shots).

Two clarifications that prevent confusion:

• The unitary part is deterministic given the input state.
• The randomness comes from measurement (and from sampling variation when you run multiple shots).

Worked Example

A toy “algorithmic pattern” (not a full famous algorithm):

Goal: identify which outcomes are “good” by making them more likely.

• Start with a uniform superposition over a small set of states.
• Apply a transformation that flips the phase of the “good” state(s).
• Apply a mixing step that converts phase differences into amplitude differences.

For a simple two-outcome world (good vs bad), you can imagine amplitudes like:

• before: equal amplitudes on good and bad
• after: the bad amplitude partly cancels while good partly reinforces

The measurable effect is not that you “see phase directly,” but that phase changes how amplitudes add.

Turtle Tip

Common Pitfalls

Quick Check

What’s Next

Many quantum algorithms are expressed using a standard abstraction: an oracle (a black-box that encodes a function or property). Next we explain what oracles are, why theorists use them, and what their limitations are.