What Is a Quantum Algorithm?

Why care? Every quantum speedup you hear about is a claim about an algorithm. To judge the claim, you need to know what an algorithm is and what it counts.

Start with the parts. A qubit is the quantum version of a bit. Its state is two numbers called amplitudes. One goes with the value 0 and one goes with the value 1. An amplitude can be positive, negative, or even complex (a number with two parts). To get the chance of reading a value, you square the size of its amplitude. A gate is a step you can always undo. It moves amplitudes around. A circuit is a fixed list of gates. A measurement turns the amplitudes back into one plain string of bits. Which string you get is random, with those squared chances. If this feels new, read the chapters on amplitudes and on measurement first. They go slowly.

A quantum algorithm is a recipe with four parts:

1. A normal computer builds a circuit for your input.
2. The quantum computer runs the circuit.
3. It measures the qubits.
4. A normal computer works out the answer from the measured bits.

You often repeat this many times. Each run is called a shot. In the model we use here, nothing changes in the middle of a run. The gate list is fixed before the run starts. It is like a program with no if statements. All the cleverness is in which fixed list you pick.

Most famous quantum algorithms work against an oracle. An oracle is a black-box function f. You may call it, but you may not look inside. Think of a web API. You pick the inputs and see the outputs, but the code is hidden. One call is a query. Query complexity is how many calls an algorithm needs in the worst case.

Here is an everyday picture. Guessing a combination lock is a query problem. Each try of the handle is one query. You care about how many tries it takes, not how fast your hand moves. That is why theory counts queries instead of seconds. The count does not depend on which machine you use. The picture breaks in one way: a quantum computer can feed the oracle a blend of inputs in one call. A lock handle cannot do that.

There is a catch. Quantum gates must be reversible, which means you can always undo them. A random f is not. If f(x)=0, you cannot tell which x went in. The fix is to keep the input and write the answer onto a separate output qubit. We use XOR to do it. XOR is "exclusive or", written ⊕. Its rules are 0⊕0=0, 0⊕1=1, and 1⊕1=0. The quantum oracle turns the pair (x, y) into (x, y ⊕ f(x)). Do it twice and you are back where you started, so it can always be undone.

Take the simplest function, f(x)=x. Its oracle is one standard gate: CX, the controlled-NOT. It flips its target qubit only when its control qubit is 1. See CNOT and controlled operations.

A promise problem comes with a guarantee about the input. You are told ahead of time that f is one of a few allowed kinds. Your only job is to say which kind. The promise is what makes big quantum speedups possible. The algorithm uses a pattern it was promised is there.

Think of a friend who says, "This bag of 8 coins is either all fake or half fake." You do not need to find which coins are fake. You only need to pick between two stories.

Worked example 1: count the queries by hand. Take a function f on 3 bits. There are 2^3 = 8 inputs. Each input gives back one bit. The promise: f is either constant or balanced. Constant means the same output on all 8 inputs. Balanced means output 0 on exactly 4 inputs and 1 on the other 4. How many queries does a normal program need to be sure, in the worst case?

1. Ask about 4 different inputs. Worst case: all four answers are 0.
2. You still cannot decide. "Always 0" fits. But a balanced function fits too, if its four 0s happen to be the inputs you picked.
3. Ask about a 5th input. If it gives 0, you have five 0s. Balanced allows only four, so f is constant. If it gives 1, f is balanced.

So the worst case is 2^(3−1) + 1 = 4 + 1 = 5 queries. For n bits it is 2^(n−1) + 1. That doubles each time n goes up by one. The Deutsch–Jozsa algorithm solves the same problem with one quantum query, and it is always right. That gap, one query against a number that doubles, is a proved result in the query model. We start there in the next chapters.

No. Mixing these up is the most common way people oversell quantum computing. Query complexity counts oracle calls. Real time also depends on how long each call takes. It depends on how long each gate takes. And it depends on how many times errors force you to repeat the run.

Worked example 2: fewer queries, but slower. Say you search N = 1,000,000 items for one marked item. All the device timings below are made-up example figures. They are not measured from any named machine.

1. Normal computer: on average you check half the items. N/2 = 500,000 checks. At an example speed of 1 nanosecond per check, that is 500,000 ns = 0.5 milliseconds.
2. Quantum computer (Grover search): needs about (π/4)·√N queries. √1,000,000 = 1,000. Then (π/4)·1,000 ≈ 0.7854 × 1,000 ≈ 785 rounds.
3. Each Grover round is a whole block of gates: the oracle plus a "reflect" step. At an example 10 microseconds per round, the total is 785 × 10 µs = 7,850 µs = 7.85 milliseconds.
4. 7.85 ms ÷ 0.5 ms ≈ 15.7 times slower than the normal scan. That is true even though it used about 640 times fewer queries.

The quantum method only wins when N is huge. But a long circuit over a huge N is exactly what today's error rates do not allow, unless we have fault tolerance (error correction that keeps up with the errors). Honest counting like this is the topic of Grover's limits.

Since 2019, headlines about "quantum supremacy" (now usually called "quantum advantage") have been about random-circuit sampling. In these tests, the device runs a circuit that is scrambled on purpose. It outputs bitstrings from a spread of chances. Experts believe a normal computer would find it very costly to copy that spread with the same quality. Three honest points:

• The task was picked because it is hard to simulate. Nobody wants its output. The result is a pile of near-random bitstrings with no use to a business.
• These results are hardware-demonstrated: real, shown on a real device, and a true engineering milestone. But they are not practical-today uses. Also, the lead over normal computers has shrunk again and again as people found better ways to simulate.
• A real use needs every part of this chapter. It needs a problem someone has. It needs an oracle or input you can actually build. And it needs a total run time that beats the best normal method. No sampling test has that shape.

Think of a car built to set a speed record on a salt flat. The record is real. It does not mean the car can take you to school. QPU137 tracks the gap between a show of skill and a real use on the quantum advantage reality page. Keeping those groups apart is the point of this course.

The two-qubit query circuit above is about as easy as quantum programs get. Today's public devices run circuits like it all the time. What a perfect simulation hides is that every gate and every readout can go wrong.

Let us use example figures. These are made-up round numbers, not any company's specification. Say each two-qubit gate fails 1% of the time, and each qubit readout fails 1% of the time. Do the arithmetic:

1. The CX works with chance 0.99.
2. Both readouts work with chance 0.99 × 0.99 = 0.9801.
3. All of it works with chance about 0.99 × 0.9801 ≈ 0.970.

So about 97% of shots would show the ideal answer. The rest land on wrong bitstrings. That is why a "certain" result on paper becomes a tall bar with a few short bars on real hardware.

Real error rates vary a lot from device to device. Our sourced data tracks them. See two-qubit fidelity, readout fidelity, and the live QPU index.