What Is a Quantum Algorithm?

A qubit is the quantum version of a bit: a two-level system whose state is described by two numbers called amplitudes — one attached to the value 0 and one attached to the value 1. Amplitudes can be positive, negative, or complex, and the probability of reading a value is the squared magnitude of its amplitude. A gate is a reversible operation that rearranges amplitudes, a circuit is a fixed sequence of gates, and a measurement converts the amplitudes back into one ordinary classical bitstring, at random, with those squared-magnitude probabilities. If any of that feels new, the chapters on amplitudes and on measurement cover it slowly.

A quantum algorithm, then, is a recipe with four parts: classical pre-processing that builds a circuit for your input, the circuit itself, a measurement, and classical post-processing of the measured bits — often repeated over many runs (each run is called a shot). Nothing adaptive happens mid-circuit in the model we use here: the gate sequence is fixed before the run starts, like a compiled program with no branches. The cleverness is entirely in which fixed sequence you choose.

Most famous quantum algorithms are stated against an oracle: a black-box function f you may call but not inspect. Think of it as an API endpoint — you control the inputs, you see the outputs, and the source code is hidden. One call is a query, and query complexity is the number of calls an algorithm needs in the worst case. Counting queries instead of seconds gives a hardware-independent measure, which is why it is the currency of algorithm theory.

Quantum gates must be reversible, and an arbitrary f is not (you cannot recover the input of f(x)=0 from its output). The standard fix is to keep the input and write the answer into a separate output qubit using XOR (exclusive-or, written ⊕: 0⊕0=0, 0⊕1=1, 1⊕1=0). The quantum oracle maps the pair (x, y) to (x, y ⊕ f(x)) — always reversible, because applying it twice undoes it. For the simplest function of all, f(x)=x, this oracle is exactly one standard gate: CX, the controlled-NOT, which flips its target qubit exactly when its control qubit is 1 (see CNOT and controlled operations).

A promise problem comes with a guarantee about the input: you are told in advance that f belongs to one of a few allowed categories, and you only have to decide which. The guarantee is what makes dramatic quantum speedups possible — the algorithm exploits structure it was promised is there.

Worked example 1 — counting queries by hand. Take a 3-bit function f mapping each of the 2^3 = 8 inputs to a single bit, with the promise that f is either constant (same output on all 8 inputs) or balanced (output 0 on exactly 4 inputs and 1 on the other 4). How many queries does a classical program need to answer with certainty, in the worst case?

1. Query 4 different inputs. Worst case: all four answers are 0.
2. You still cannot decide. Constant-zero fits. But so does a balanced function whose four 0-outputs happen to be exactly the inputs you chose.
3. Query a 5th input. If it returns 0, five zeros rule out balanced (which allows only four) — constant. If it returns 1 — balanced.

So the worst case is 2^(3−1) + 1 = 4 + 1 = 5 queries. In general it is 2^(n−1) + 1, which grows exponentially with n. The Deutsch–Jozsa algorithm decides the same promise problem with one quantum query, deterministically. That gap — exponential versus one — is a proved theorem in the query model, and it is where we start in the next chapters.

No, and confusing the two is the most common way to overstate quantum computing. Query complexity counts oracle calls; wall-clock time also depends on how long each call takes, how long each gate takes, and how many repetitions errors force on you.

Worked example 2 — when fewer queries is still slower. Suppose you are searching N = 1,000,000 items for one marked item. All device timings below are illustrative archetype figures, not measurements of any named machine.

1. Classical scan: on average you check N/2 = 500,000 items. At an illustrative 1 nanosecond per check, that is 500,000 ns = 0.5 milliseconds.
2. Quantum (Grover search): needs about (π/4)·√N queries. √1,000,000 = 1,000, and (π/4)·1,000 ≈ 0.7854 × 1,000 ≈ 785 iterations.
3. Each Grover iteration is a full circuit block — the oracle plus a reflection step. At an illustrative 10 microseconds per iteration, total time is 785 × 10 µs = 7,850 µs = 7.85 milliseconds.
4. 7.85 ms ÷ 0.5 ms ≈ 15.7× slower than the classical scan — despite needing about 640× fewer queries.

The quadratic advantage only wins when N is enormous — and a deep circuit over enormous N is exactly what today's error rates forbid without fault tolerance. Honest accounting like this is the subject of Grover's limits.

The headline "quantum supremacy" (now usually "quantum advantage") demonstrations since 2019 are random-circuit sampling experiments: the device runs a deliberately scrambled circuit and outputs bitstrings drawn from a distribution that is believed to be very costly to sample classically at matching fidelity. Three honest observations:

• The task was chosen because it is hard to simulate, not because anyone wants its output. The result is a pile of near-random bitstrings with no business meaning.
• These results are hardware-demonstrated feats of device engineering — a real milestone — but they are not practical-today applications, and the classical-hardness margin has repeatedly shrunk as classical simulation methods improved.
• An application requires the full pipeline of this chapter — a problem someone has, an oracle or input encoding you can actually build, and end-to-end time that beats the best classical method. No sampling experiment has that shape.

QPU137 tracks the difference between demonstration and application on the quantum advantage reality page. Keeping those categories separate is the whole point of this course.

The two-qubit query circuit above is about as easy as quantum programs get, and today's public devices run circuits like it routinely. What ideal simulation hides is that every gate and every readout has an error probability. Using archetype figures — illustrative numbers, not any vendor's specification — of 1% error per two-qubit gate and 1% error per qubit readout: the CX succeeds with probability 0.99, and both readouts succeed with probability 0.99 × 0.99 = 0.9801, so roughly 0.99 × 0.9801 ≈ 0.970 — about 97% of shots — would show the ideal answer, with the rest scattered onto wrong bitstrings. That is why a "deterministic" prediction on paper becomes a dominant-but-imperfect histogram in practice.

Real error rates vary widely by device and are exactly what our sourced data tracks: see two-qubit fidelity, readout fidelity, and the live QPU index.