Deutsch's Algorithm

In 1985, David Deutsch asked a question that nobody had seriously asked before: can a quantum computer actually do something a classical computer cannot? Not in principle, not as a thought experiment — in actual fact, with a specific problem and a specific number of operations.

At the time, the idea of a quantum computer was barely a decade old. Richard Feynman had argued in 1982 that quantum systems are hard to simulate classically, and maybe a quantum machine could simulate them more efficiently. David Deutsch had formalised the notion of a universal quantum Turing machine in 1985. But nobody had shown, concretely, a task on which a quantum algorithm provably beat every classical one. The field had a promise and no demonstration.

Deutsch's own answer, published in the same 1985 paper that defined the quantum Turing machine, is a toy problem. It is so small that the "speedup" — one query instead of two — feels almost like a joke. But the circuit that achieves it introduces every idea that would later power Shor's factoring and Grover's search: superposition on the input register, oracle access to an unknown function, phase kickback as the mechanism, and Hadamard interference as the readout. Every algorithm in Parts 8 through 10 of this track is a descendant of this one. If you want to understand the ancestral move of quantum computing, you begin here.

The problem — constant or balanced

You are given a Boolean function on one bit: f: \{0,1\} \to \{0,1\}. There are exactly four such functions, and you can list them all:

A function is constant if f(0) = f(1) — it returns the same value for every input. It is balanced if f(0) \neq f(1) — half of the inputs map to 0 and the other half to 1. With only one input bit, the two classes are the two "constant" functions and the two "balanced" functions.

The question Deutsch poses: given oracle access to one of these four functions (you don't know which), decide whether it is constant or balanced. You don't have to name the specific function — only its type.

Specifically, the access you have is the standard oracle from the previous chapter:

Each application of U_f is one query. Your resource is the number of queries you use. Your goal is to answer "constant or balanced?" using as few as possible.

The classical answer — you need 2 queries

Before meeting the quantum algorithm, get the classical bound pinned down. The claim is that no classical algorithm can answer "constant or balanced?" with fewer than 2 queries.

Suppose you only use 1 query. You pick an input — either 0 or 1 — and you learn f at that point. Say you queried f(0) and got the result b \in \{0, 1\}.

That one bit of information cannot distinguish the two cases. Concretely: if your query returned f(0) = 0, the function could be either constant-0 (in which case f(1) = 0 too) or identity (in which case f(1) = 1). Both are consistent with the single observation. You have no way to tell which class f is in.

Symmetric reasoning applies if you queried f(1) first. Any one query leaves exactly two of the four possible functions alive, and those two always lie in opposite classes — one constant, one balanced. Thus one query is provably insufficient, classically.

Two queries are clearly sufficient: query f(0), query f(1), compare them. If they match, f is constant; if they differ, f is balanced. So the classical query complexity is exactly 2. That is the bar Deutsch wants to beat.

The quantum answer — 1 query suffices

The algorithm Deutsch designed uses exactly one application of U_f. Here is the full circuit.

In five gates (two Hs, the oracle U_f, one more H, plus a measurement), the circuit answers the question. The heart of the matter is what happens inside the U_f stage — the magic trick called phase kickback, which converts a bit flip on the target register into a sign flip on the input register. Everything else is standard Hadamard interference.

Walking the circuit step by step

Let's compute the state at each stage of the circuit. Name the states |\psi_0\rangle, |\psi_1\rangle, |\psi_2\rangle, |\psi_3\rangle at the four labelled points in the figure.

Stage 0 — initial state.

Why the target starts in |1\rangle and not |0\rangle: this is the critical setup choice that makes phase kickback work. When the target is first Hadamarded, |1\rangle becomes |-\rangle = \tfrac{1}{\sqrt{2}}(|0\rangle - |1\rangle) — the minus-sign state. Applying the oracle to |x\rangle|-\rangle pulls out a factor of (-1)^{f(x)} in front. If you started the target at |0\rangle, you would get |+\rangle after the Hadamard and the oracle would just flip the target 50% of the time without kicking any phase back. The initial |1\rangle is the non-negotiable ingredient.

Stage 1 — after the two Hadamards.

Why Hadamard both: the input register needs to be in superposition so U_f can query both f(0) and f(1) in one go; the target register needs to be in |-\rangle so the phase kickback trick fires. Two Hadamards, both essential.

Expanding the tensor product gives

Stage 2 — after the oracle. Apply U_f|x\rangle|y\rangle = |x\rangle|y \oplus f(x)\rangle to each term. The rule for the |-\rangle target is the clean one:

Let's unpack the target. If f(x) = 0, then |0 \oplus 0\rangle - |1 \oplus 0\rangle = |0\rangle - |1\rangle = \sqrt{2}|-\rangle. If f(x) = 1, then |0 \oplus 1\rangle - |1 \oplus 1\rangle = |1\rangle - |0\rangle = -(|0\rangle - |1\rangle) = -\sqrt{2}|-\rangle. So in both cases

Substituting back:

Why this is "phase kickback": the factor (-1)^{f(x)} appears in front of the whole state, but notice that the target register |-\rangle is unchanged. The action of U_f — which was supposed to flip the target by f(x) — has instead been "kicked back" to the input register as a phase. The target was just a catalyst; the information about f(x) ends up on the input qubit as a sign.

Applying this to |\psi_1\rangle = \tfrac{1}{\sqrt{2}}(|0\rangle + |1\rangle)|-\rangle:

So now the input register holds a superposition of |0\rangle and |1\rangle with signs determined by f(0) and f(1). The target qubit is still in |-\rangle, as if nothing happened to it. (Physically it did — the oracle acted on it — but the net effect is a phase on the input.)

Factor out the common sign (-1)^{f(0)} to get a form that depends only on f(1) - f(0) — the "difference" between the two function values:

(The overall (-1)^{f(0)} out front is a global phase — it has no physical consequence and will disappear in the final probabilities.) The relative sign inside is (-1)^{f(0) \oplus f(1)}, which depends only on whether f(0) = f(1) or not:

• If f is constant: f(0) \oplus f(1) = 0, so the relative sign is +1, giving |+\rangle.
• If f is balanced: f(0) \oplus f(1) = 1, so the relative sign is -1, giving |-\rangle.

In compact notation:

where \pm is a global sign we can drop.

Stage 3 — after the final Hadamard on the input. Apply H to the input register.

So

Measurement. Measure the input qubit in the computational basis. If f is constant, you get 0 with certainty. If f is balanced, you get 1 with certainty. The outcome is a deterministic answer to the original question:

One query to U_f, one bit of output, exact answer. The classical lower bound was 2 queries. Deutsch's algorithm solves the problem with half as many queries as any classical algorithm can.

Why this works — the conceptual summary

The quantum algorithm does not learn f(0) or f(1) individually. Those values are gone by the time you measure — in fact, the state |\psi_3\rangle above has no memory of either f(0) or f(1) on their own (except as an unobservable global phase). What the algorithm extracts is the XOR f(0) \oplus f(1) — the single bit that says "are f(0) and f(1) equal or not?"

This is the fundamental difference. A classical algorithm must learn f at both points to compute the XOR; there is no classical way to measure a function's "output XOR" without measuring both outputs. A quantum algorithm can query U_f on a superposition and let interference combine the two outputs into their XOR, without ever committing to a specific value of f at a specific point.

Summarised as a slogan: classical queries extract function values; quantum queries can extract relationships between function values. The relationship f(0) \oplus f(1) is a global property of f — it involves both input points — and the oracle model lets quantum algorithms compute global properties with fewer queries than classical algorithms can. Every large-scale quantum speedup later in the curriculum (Deutsch-Jozsa, Bernstein-Vazirani, Simon, Shor) is a generalisation of this same trick.

Worked examples — trace the circuit for specific functions

Common confusions

• "One query vs two queries — who cares, it's only 2x." The absolute speedup is tiny; the proof-of-concept value is enormous. Before Deutsch's algorithm, it was a plausible conjecture that every problem solvable by a quantum computer was also efficiently solvable by a classical computer. Deutsch showed that conjecture was false on a specific problem with a specific quantitative gap. This is the foundation that made Shor's algorithm even a meaningful goal ten years later.

• "Deutsch's algorithm scales to n bits." It does not. Deutsch's algorithm is strictly for functions f: \{0,1\} \to \{0,1\}. The n-bit generalisation — given f: \{0,1\}^n \to \{0,1\} promised constant or balanced, decide which — is Deutsch-Jozsa (1992), covered in a later chapter. Deutsch-Jozsa shows an exponential query gap: O(1) quantum vs \Omega(2^{n-1}) classical in the deterministic model.

• "The speedup comes from parallelism — the oracle tries both inputs at once." Half-right. The oracle does act on a superposition of both inputs, but measurement still yields only one bit. What matters is that the oracle creates a phase relationship between the |0\rangle and |1\rangle terms of the input register — a global property that Hadamard interference then reads out. Without the phase kickback, acting on a superposition alone would not give a one-query solution.

• "Phase kickback is a separate trick from what U_f does." Not quite — phase kickback is a consequence of U_f's definition. The rule |x\rangle|y\rangle \mapsto |x\rangle|y \oplus f(x)\rangle, evaluated on a |-\rangle target, automatically produces the factor (-1)^{f(x)} on the input register. No extra gates are needed. The "trick" is knowing to prepare the target in |-\rangle in the first place.

• "If you start with the target in |0\rangle, Deutsch's algorithm still works." It does not. If the target starts at |0\rangle, the first Hadamard gives |+\rangle rather than |-\rangle, and the oracle produces U_f|x\rangle|+\rangle = |x\rangle|+\rangle regardless of f(x) — no phase kickback. The final state after the last Hadamard would be |0\rangle|+\rangle independent of f, and measurement would tell you nothing. The initial |1\rangle on the target is essential.

• "f constant means the circuit is trivial." The oracle for constant-0 is the identity, true; the oracle for constant-1 flips the target every time, which is the I \otimes X gate. But the algorithm as a whole is not trivial — it still runs all five gates, and the outcome of the measurement is meaningful even though the oracle did little. The non-trivial-ness comes from the post-processing (the final Hadamard and measurement), which does the same work regardless of which specific f was inside the box.

Going deeper

Information-theoretically — measuring XOR, not components

Here is the cleanest framing of why 1 quantum query beats 2 classical queries.

The problem "is f constant or balanced?" is equivalent to the problem "compute f(0) \oplus f(1)". If the answer is 0, the function is constant; if 1, balanced. A classical algorithm cannot compute f(0) \oplus f(1) from fewer than 2 queries because a single query gives one bit, and f(0) \oplus f(1) depends on two bits that a single query cannot fix simultaneously. Formally, any classical oracle-access algorithm making k queries produces an output that is a function of k bits (the oracle answers); computing f(0) \oplus f(1) deterministically from k bits requires those k bits to cover both f(0) and f(1), which forces k \geq 2.

A quantum algorithm is not restricted to extracting bit values. By querying in superposition and using phase kickback, it can extract parities (XOR combinations) with one query. Deutsch's algorithm specifically computes the parity f(0) \oplus f(1) — a two-input linear function of the output bits — using one oracle call. This is the first example of a general pattern: quantum queries can compute parities of oracle outputs in one shot, even when the individual outputs are unknown. Bernstein-Vazirani later cashes this pattern in at scale, learning an n-bit hidden string from one query.

Historical context — 1985

A few things about 1985 are worth holding onto.

First, the field of quantum computing did not exist as a recognised discipline. Feynman's 1982 paper had suggested quantum-based simulators for quantum physics; Deutsch's 1985 paper did two things: (a) it defined the quantum Turing machine as a computational model, and (b) it gave the first non-trivial algorithm in that model. The paper — "Quantum theory, the Church-Turing principle and the universal quantum computer" [1] — is readable and landmark.

Second, the problem itself is contrived. Deutsch is not solving anything you would care about in a practical sense — you would not build a quantum computer just to decide whether a 1-bit function is constant or balanced. The problem is designed to be the simplest possible instance where a quantum advantage can be demonstrated cleanly. The real payoff came in 1992 when Deutsch and Jozsa generalised the argument to n-bit functions, showing an exponential classical-quantum query gap. Bernstein and Vazirani (1993), Simon (1994), and Shor (1994) followed in rapid succession, each generalising the core ideas further.

Third, Deutsch's original 1985 algorithm was slightly different from the modern textbook version. The original used a probabilistic (not deterministic) version that only gave the right answer half the time. The clean deterministic version above is due to Cleve, Ekert, Macchiavello, and Mosca (1998), who cleaned up several of the early algorithms including Deutsch and Grover.

The generalisation to n bits — preview

The obvious question: what if f is a function on n bits instead of one? If f: \{0,1\}^n \to \{0,1\} is promised to be either constant (same value on every input) or balanced (equal number of 0s and 1s in its output), can you still distinguish the two classes with one quantum query?

Yes — and this is the Deutsch-Jozsa algorithm, which comes two chapters later. The circuit is a direct generalisation: Hadamard on every input qubit, Hadamard on the target qubit (initialised to |1\rangle), one oracle query, Hadamard on every input qubit, measure. One query suffices. Classically, in the worst case, you need 2^{n-1} + 1 queries (a little more than half the inputs) to be sure, so the query gap is exponential.

The phase-kickback argument is the same: the oracle acts on |-\rangle in the target to deposit a phase (-1)^{f(x)} on each term of the input superposition, and the final Hadamard layer interferes those phases to produce a deterministic outcome (all |0\rangle^n if constant, otherwise some non-zero string). Every subsequent algorithm you meet — Bernstein-Vazirani, Simon, Grover, Shor — builds on this same skeleton: Hadamard layer → oracle → Hadamard (or more general) unitary → measurement.

Why this chapter is load-bearing

Deutsch's algorithm is the smallest instance of every idea that makes quantum computing work.

• Superposition of inputs — the input register is |+\rangle, not |0\rangle, when the oracle fires.
• Phase kickback — the oracle's effect is a phase on the input, not a flip on the target.
• Interference — the final Hadamard combines the phase pattern into a deterministic outcome.
• Global property computation — the output is f(0) \oplus f(1), a relationship between f at two points, not a value of f at one point.

Every algorithm later in the track does these four moves at a bigger scale. Grover replaces f(0) \oplus f(1) with "is there an x with f(x) = 1?" — a different global property, but still computed by interference on a phase-marked register. Shor replaces the XOR with the period of a modular exponentiation function — yet another global property, unreachable classically. The machinery is the same.

Indian CS and quantum theory

Deutsch's algorithm is standard material in every Indian theoretical computer science programme that touches quantum. Courses at IIT Madras, IIT Bombay, IISc Bangalore, CMI Chennai, and TIFR (Mumbai) introduce it early as the archetypal quantum algorithm, before moving on to Deutsch-Jozsa and the later algorithms. The algorithm's small size makes it amenable to pen-and-paper analysis, and students are typically expected to work through the constant/balanced case by hand (as you did in the worked examples) before tackling the n-bit generalisation.

Alongside this, India has a strong tradition in mathematical theory of quantum information — Ambainis-style adversary bounds, characters of finite groups for hidden subgroup problems, and the combinatorial identities underlying phase estimation all attract theoretical attention at these institutes. Deutsch's algorithm's role is as the first rung: the smallest example of a quantum speedup, which students of all these sub-fields master on the way to the harder material.

Where this leads next

• Phase kickback — the full chapter on the mechanism that makes Deutsch's algorithm work. Once you see how it operates, every later quantum algorithm becomes a phase-kickback story.
• Deutsch-Jozsa algorithm — the n-bit generalisation. Same circuit shape, exponential query advantage.
• Bernstein-Vazirani algorithm — learn an unknown n-bit string from a linear oracle in one query instead of n.
• Simon's algorithm — the exponential quantum-classical query gap that directly inspired Shor's factoring algorithm.
• Quantum Fourier transform — what generalises Hadamard from \mathbb{Z}_2 to \mathbb{Z}_n. The next step up the abstraction ladder.
• Grover's algorithm — the quadratic speedup on unstructured search, using amplitude amplification rather than phase kickback as the final step.

References

1. David Deutsch, Quantum theory, the Church-Turing principle and the universal quantum computer (1985), Proceedings of the Royal Society A — DOI:10.1098/rspa.1985.0070. The original paper.
2. Cleve, Ekert, Macchiavello, Mosca, Quantum algorithms revisited (1998) — arXiv:quant-ph/9708016. The modern deterministic reformulation of Deutsch's algorithm.
3. Nielsen and Chuang, Quantum Computation and Quantum Information (2010), §1.4.3 and §1.4.4 — Cambridge University Press.
4. John Preskill, Lecture Notes on Quantum Computation, Chapter 6 — theory.caltech.edu/~preskill/ph229.
5. Wikipedia, Deutsch–Jozsa algorithm — includes the single-bit Deutsch case and the n-bit generalisation.
6. Qiskit Textbook, Deutsch-Jozsa Algorithm — hands-on implementation in Qiskit, runnable on IBM's quantum hardware.