The Deutsch Problem

You now know two things from earlier in this module: oracles package a function inside a reversible black box, and Boolean functions over one bit can be either constant (same output for every input) or balanced (different outputs for each input). The Deutsch problem is the simplest question you can ask about such a function when you can only call the oracle.

The setup

A function $f : \{0, 1\} \to \{0, 1\}$ is hidden inside an oracle. You cannot look at the implementation; you can only evaluate the function. There are exactly four possible functions on one bit:

| Function | $f(0)$ | $f(1)$ | Type | |----------|--------|--------|------| | $f_0$ (zero) | 0 | 0 | constant | | $f_1$ (one) | 1 | 1 | constant | | $f_2$ (identity) | 0 | 1 | balanced | | $f_3$ (negation) | 1 | 0 | balanced |

The question is not "which of the four functions is it?" but the coarser question: is $f$ constant or balanced?

The classical lower bound

Classically, one query is not enough. After learning $f(0)$ , you still cannot determine the class of $f$ : whichever value $f(0)$ returns, both a constant and a balanced function remain consistent with that result, so the constant-vs-balanced question is still undecided. You need two queries — evaluate $f$ at both inputs and compare — to decide with certainty. This is the baseline that Deutsch's algorithm will beat.

What Deutsch's algorithm promises

Deutsch showed in 1985 that a quantum computer can answer this question with only one oracle call. It does so by exploiting two features you have already seen:

Superposition — a single oracle call can be applied to a superposition of inputs, so the oracle "sees" both $|0\rangle$ and $|1\rangle$ at once.
Phase kickback — when the ancilla qubit is prepared in the $|-\rangle$ state, the oracle encodes $f(x)$ as a $\pm 1$ phase rather than a bit flip, allowing interference to separate the constant and balanced cases.

The final measurement collapses the register onto a state whose outcome reveals the global property of $f$ in one shot. The exact circuit and the state-vector arithmetic come in the next lesson.

Why this matters

The Deutsch problem is deliberately tiny — one bit of input, two possible answers — but it establishes the pattern for every query-complexity speedup that follows. Deutsch–Jozsa generalises it to $n$ bits. Bernstein–Vazirani, Simon's algorithm, and Grover's search all use the same skeleton: put qubits in superposition, call a phase oracle once (or a few times), interfere, and measure a global property.

Understanding the problem statement precisely — what is given, what is asked, and what counts as a query — is the first step before understanding why the quantum circuit works.