Constant vs Balanced Functions

The Deutsch–Jozsa algorithm is one of the earliest demonstrations that a quantum computer can answer a specific question with exponentially fewer queries than any classical algorithm. Before we can appreciate what the algorithm does, we need to be precise about the kind of function it reasons about.

Boolean functions with a single-bit output

A Boolean function on $n$ bits is any map $f : \{0,1\}^n \to \{0,1\}$ . It takes an $n$ -bit string as input and outputs a single bit. The Deutsch–Jozsa problem restricts attention to functions with a particular structure, so we need two definitions.

Constant function. A function $f$ is constant if it returns the same output for every input:

$f(x) = 0 \text{ for all } x \in \{0,1\}^n, \quad\text{or}\quad f(x) = 1 \text{ for all } x \in \{0,1\}^n.$

There are exactly two constant functions on $n$ bits — the all-zeros function and the all-ones function.

Balanced function. A function $f$ is balanced if exactly half of all inputs map to $0$ and the other half map to $1$ . Because there are $2^n$ possible inputs, a balanced function outputs $0$ on exactly $2^{n-1}$ of them and $1$ on the remaining $2^{n-1}$ .

Why this classification matters

Classically, determining whether an unknown $f$ is constant or balanced requires querying $f$ on at least $2^{n-1}+1$ inputs in the worst case. You must see just over half of all outputs before you can be certain: if the first $2^{n-1}$ queries all return $0$ , the function could still be balanced (the other half might all be $1$ ) or constant (all outputs are $0$ ). Only the next query settles it. For large $n$ this is an exponential number of queries.

The Deutsch–Jozsa algorithm, by contrast, answers the question with a single quantum query regardless of $n$ . The separation is as stark as possible: one query versus exponentially many. This is possible because the algorithm uses a quantum-mechanical encoding of $f$ (called an oracle) that allows all $2^n$ inputs to be queried simultaneously through superposition, then uses interference to read out a global property — constant or balanced — in one shot.

Concrete small examples

For $n = 2$ the four possible inputs are $00$ , $01$ , $10$ , and $11$ .

| Function | $f(00)$ | $f(01)$ | $f(10)$ | $f(11)$ | Type | |----------|---------|---------|---------|---------|------| | $f_A$ | 0 | 0 | 0 | 0 | constant | | $f_B$ | 1 | 1 | 1 | 1 | constant | | $f_C$ | 0 | 0 | 1 | 1 | balanced | | $f_D$ | 0 | 1 | 0 | 1 | balanced |

$f_C$ and $f_D$ each output $0$ on exactly two of the four inputs and $1$ on the other two, so both are balanced. The Deutsch–Jozsa algorithm can distinguish the top two rows from the bottom two with a single oracle call, no matter how large the table grows.

From classification to algorithm

The module that follows shows how to encode $f$ as a quantum oracle — a unitary gate $U_f$ that computes $f$ reversibly — and then how to run the Deutsch–Jozsa circuit. The circuit's output is deterministically $|00\cdots0\rangle$ when $f$ is constant and anything else when $f$ is balanced, giving a one-shot answer to a question that classically demands exponentially many queries.