The Deutsch–Jozsa Algorithm

Deutsch–Jozsa tells whether a hidden function is constant or balanced with one quantum query. A normal program that must be certain needs up to 2^(n−1)+1 queries. It was the first proved gap between quantum and normal computers. Its key trick, called phase kickback, also drives Bernstein–Vazirani, Grover, and the phase estimation inside Shor.

What question does Deutsch–Jozsa answer?

Why start here? Deutsch–Jozsa is the smallest algorithm that shows a real, proved quantum gap. Every idea in it comes back later in the course.

Someone hands you a hidden function f. It is an oracle: an API you can call but not look inside. It takes n input bits and gives back one output bit. You are promised it is one of two kinds:

Constant: the same output for every input.
Balanced: output 0 for exactly half the inputs, and 1 for the other half.

Your job is to say which kind, using as few calls as you can. Each call is a query.

Think of a sealed box with a light and a switch. Either the light ignores the switch (constant), or it follows the switch half the time (balanced). You want to know which box you have, not how the wires look.

This chapter builds the smallest version, n = 1. Here f takes one bit and gives one bit. There are exactly four such functions. Two are constant: f(x)=0 and f(x)=1. Two are balanced: f(x)=x (it gives back its input) and f(x)=NOT x. If oracles are new to you, chapter 1 explains queries from scratch.