The Deutsch Algorithm
Suppose you are handed a black box that computes some unknown one-bit Boolean function. You may feed it a bit and read out a bit, but you cannot look inside. The question "is this function constant or balanced?" seems to demand two separate queries. You would try input 0, try input 1, then compare. The Deutsch algorithm shows that a quantum computer answers this question with only one query to the box. It does this by exploiting superposition and interference rather than brute-force lookup. This might look like a toy puzzle, but it is the smallest possible demonstration of a real phenomenon. A quantum algorithm provably outsprints every classical algorithm on a well-defined task. It is historically the first example of quantum speedup, predating factoring and search algorithms by a decade. The function-property question it answers is global information about a function extracted without reading it pointwise. This is the prototype for an entire family of algorithms built on the same skeleton. The big picture is this: classical query algorithms extract information one bit of input at a time. Quantum query algorithms can query a superposition of all inputs at once. Then they use interference to make the answer bit land in a readable place. Meanwhile, the "which input" information cancels out. Deutsch's algorithm is the minimal instance where this trick works. It uses exactly one qubit for the input register and one for the output register. These are wired through the Quantum Oracles and Function Encoding construction and a single-qubit Hadamard transform. This article builds the algorithm from the oracle definition upward. It gives a precise statement of the problem, the circuit, and its state-vector trace. It explains why interference forces the correct answer with certainty. It also shows how the same idea scales — foreshadowed here — into the multi-bit The Deutsch-Jozsa Algorithm.
- Problem: decide if a hidden one-bit function `f : {0,1} → {0,1}` is constant or balanced, using the fewest oracle calls.
- Classically two queries are necessary and sufficient; quantumly one query suffices, with certainty.
- The trick: query the oracle in superposition, then use the phase-kickback effect to encode the global property in the phase of the query qubit.
- A final Hadamard on the query qubit converts that phase into a deterministically measurable bit.
- Correctness follows exactly from interference: the two branches of the superposition either reinforce or cancel depending on whether `f` is constant or balanced.
- The circuit is the seed for the general The Deutsch-Jozsa Algorithm, which generalizes to `n`-bit functions with the same one-query structure.
Querying a function oracle in superposition lets interference reveal a global property of the function — constant vs. balanced — in a single query, where every classical strategy needs at least two.
The idea
Fix the problem precisely. Let `f : {0,1} → {0,1}` be a Boolean function on one bit. There are exactly four such functions: ``` f(x) = 0 (constant) f(x) = 1 (constant) f(x) = x (balanced) f(x) = 1 - x = NOT x (balanced) ``` `f` is constant if `f(0) = f(1)`, and balanced if `f(0) ≠ f(1)` (for a one-bit domain, balanced just means it is a bijection). The task: given oracle access to `f`, determine which case holds — constant or balanced — with the fewest calls to the oracle. Classically this requires two queries in the worst case. Querying `f(0)` alone tells you nothing about `f(1)`; you must query both and compare. This is a "black box" argument: any single query reveals only one function value, and there exist constant and balanced functions agreeing on that one value (e.g., `f(0)=0` is consistent with the constant function `f≡0` and with the balanced function `f(x)=x`), so one query can never distinguish the two classes with certainty. Quantumly, the oracle is realized as a unitary `U_f` acting on two qubits — an input (query) qubit `|x⟩` and an output (target) qubit `|y⟩` — via the standard reversible encoding from Quantum Oracles and Function Encoding: ``` U_f |x⟩|y⟩ = |x⟩ |y ⊕ f(x)⟩ ``` This is unitary (hence a legal quantum gate) because XOR-ing `f(x)` twice restores the original `y`, making `U_f` its own inverse. The Deutsch algorithm prepares the input qubit in a superposition of `|0⟩` and `|1⟩`, prepares the output qubit in the special state `|-⟩ = (|0⟩ - |1⟩)/√2`, applies `U_f` once, and finishes with a Hadamard on the input qubit before measuring. The single call to `U_f` acts on a superposition covering both inputs simultaneously, and the resulting global phase pattern — not any individual value of `f` — is what gets measured.
How it works
The essential mechanism is phase kickback: when the target qubit is prepared as an eigenstate of the XOR-by-`f(x)` operation, applying `U_f` does not change the target qubit's state at all — it only multiplies the input branch by a phase `(-1)^{f(x)}`. This converts a value encoded in `f(x)` into a phase attached to `|x⟩`, which a Hadamard can then convert into an observable bit. Concretely, `|-⟩` is an eigenstate of the "flip by `b`" map: for any bit `b`, ``` X^b |-⟩ = (-1)^b |-⟩ ``` since flipping `|0⟩ - |1⟩` swaps the two terms and reintroduces the original state up to sign exactly when `b = 1`. Since `U_f|x⟩|-⟩ = |x⟩ (X^{f(x)}|-⟩) = (-1)^{f(x)} |x⟩|-⟩`, the oracle call turns into a controlled phase, with the target qubit untouched and reusable as an ancilla.
Step-by-step trace. Start with two qubits in `|0⟩|1⟩`. 1. Initialize: `|ψ₀⟩ = |0⟩|1⟩` 2. Hadamard both qubits: ``` |ψ₁⟩ = H|0⟩ ⊗ H|1⟩ = (|0⟩+|1⟩)/√2 ⊗ (|0⟩-|1⟩)/√2 ``` 3. Apply the oracle `U_f`. Using phase kickback, each term `|x⟩|-⟩` picks up a sign `(-1)^{f(x)}`: ``` |ψ₂⟩ = ( (-1)^{f(0)}|0⟩ + (-1)^{f(1)}|1⟩ ) / √2 ⊗ |-⟩ ``` 4. Hadamard the query qubit. Factor out the global phase `(-1)^{f(0)}`: ``` |ψ₂⟩ = (-1)^{f(0)} ( |0⟩ + (-1)^{f(0)⊕f(1)}|1⟩ ) / √2 ⊗ |-⟩ ``` Applying `H` to the query register: ``` if f(0) ⊕ f(1) = 0 (constant): H(|0⟩+|1⟩)/√2 = |0⟩ if f(0) ⊕ f(1) = 1 (balanced): H(|0⟩-|1⟩)/√2 = |1⟩ ``` 5. Measure the query qubit in the computational basis. Outcome `0` means constant; outcome `1` means balanced — deterministically, ignoring the irrelevant global phase. ```pseudocode // Deutsch's Algorithm // Input: black-box unitary U_f implementing |x>|y> -> |x>|y XOR f(x)> // Output: bit r, where r = 0 iff f is constant, r = 1 iff f is balanced procedure DEUTSCH(U_f): q0 <- |0> // query qubit q1 <- |1> // target qubit q0 <- H(q0) // (|0> + |1>) / sqrt(2) q1 <- H(q1) // (|0> - |1>) / sqrt(2) = |-> (q0, q1) <- U_f(q0, q1) // one oracle call: phase kickback // state becomes // (-1)^f(0)|0> + (-1)^f(1)|1> (up to |-> factor) q0 <- H(q0) // interferes the two branches r <- MEASURE(q0) // r = 0: constant, r = 1: balanced return r ```
Complexity & correctness
Query complexity. The algorithm makes exactly one call to `U_f`, regardless of which of the four functions is hidden inside it. This is optimal: any classical deterministic algorithm needs two queries in the worst case, since a single query result is consistent with both a constant and a balanced function (shown above by explicit example). Deutsch's algorithm therefore achieves a 2-to-1 query reduction, the smallest nontrivial quantum query speedup, and the ancestor of the exponential separations proven later for The Deutsch-Jozsa Algorithm.
Gate/time complexity. Besides the single oracle call, the circuit uses exactly three Hadamard gates (one on the target, two on the query line) and one measurement — all `O(1)` operations independent of any problem size, since the problem itself has a fixed size (one input bit). So total circuit depth is `O(1)`.
Space complexity. Two qubits, fixed. No ancilla scaling, since the domain of `f` has size 2.
Correctness proof sketch. The argument has two parts: the phase-kickback identity, and the fact that a Hadamard converts the resulting relative sign into a deterministic computational-basis outcome. Phase kickback. For any bit `b`, `X^b|-⟩ = (-1)^b |-⟩`, verified directly: `X^0|-⟩=|-⟩`, and `X^1|-⟩ = (|1⟩-|0⟩)/√2 = -|-⟩`. Since `U_f` acts as `X^{f(x)}` on the target register conditioned on the query register being `|x⟩`, linearity gives: ``` U_f ( |x⟩|-⟩ ) = |x⟩ ⊗ X^{f(x)}|-⟩ = (-1)^{f(x)} |x⟩|-⟩ ``` for each basis state `|x⟩`, and by linearity this extends correctly to the superposition `(|0⟩+|1⟩)/√2` fed into the query register. Interference. After the oracle call, the query register alone (tracing out the untouched `|-⟩` target) is: ``` |φ⟩ = ( (-1)^{f(0)}|0⟩ + (-1)^{f(1)}|1⟩ ) / √2 ``` There are only two cases up to the irrelevant global phase `(-1)^{f(0)}`:
- Constant (`f(0)=f(1)`): the relative sign is `+1`, so `|φ⟩ ∝ |0⟩+|1⟩`, and `H|φ⟩ = |0⟩` exactly.
- Balanced (`f(0)≠f(1)`): the relative sign is `-1`, so `|φ⟩ ∝ |0⟩-|1⟩`, and `H|φ⟩ = |1⟩` exactly.
Because `H` is its own inverse and maps `(|0⟩+|1⟩)/√2 ↦ |0⟩`, `(|0⟩-|1⟩)/√2 ↦ |1⟩` exactly (not approximately), the two cases land on orthogonal, deterministic measurement outcomes. There is no probability of error — the algorithm is exact, not merely "likely correct." This is the crux of why the speedup is genuine and not a randomized shortcut: the interference pattern is perfectly constructive in one case and perfectly destructive in the other.
Honest tradeoffs. The advantage is a constant-factor query saving (2 → 1), not an asymptotic one — Deutsch's problem has fixed size, so there is no "n" to speak of yet. The real asymptotic payoff appears only once the domain is generalized to `n` bits in The Deutsch-Jozsa Algorithm, where the classical worst case becomes exponential while the quantum algorithm remains a single query. Deutsch's algorithm's importance is conceptual and pedagogical: it isolates the interference mechanism in its purest, smallest form, uncluttered by asymptotics.
Worked example
Take `f(x) = x` (the identity function — balanced), and trace amplitudes explicitly with actual numbers instead of symbols.
| Step | State (unnormalized amplitudes shown as fractions of `1/2`) | Note | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Init | ` | 0⟩ | 1⟩` | target set to `1` | ||||||||||
| After H⊗H | `½[ | 00⟩ − | 01⟩ + | 10⟩ − | 11⟩ ]` | both qubits in superposition | ||||||||
| Apply `U_f`, `f(x)=x` | flip target iff query is `1`: ` | 10⟩→ | 11⟩`, ` | 11⟩→ | 10⟩` | oracle call happens here, once | ||||||||
| After oracle | `½[ | 00⟩ − | 01⟩ + | 11⟩ − | 10⟩ ]` = `½( | 0⟩− | 1⟩)⊗( | 0⟩− | 1⟩)` = `( | 0⟩− | 1⟩)/√2 ⊗ | −⟩` | query register is now ` | −⟩`, matching predicted sign flip since `f(0)=0, f(1)=1` differ |
| Apply H to query qubit | `H | −⟩ = | 1⟩` | exact, deterministic | ||||||||||
| Measure | `r = 1` | correctly reports balanced |
Now contrast with `f(x) = 0` (constant):
| Step | State | Note | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| Init | ` | 0⟩ | 1⟩` | ||||||||
| After H⊗H | `½[ | 00⟩ − | 01⟩ + | 10⟩ − | 11⟩ ]` | same as before, `f` not yet applied | |||||
| Apply `U_f`, `f(x)=0` | target never flips: state unchanged | oracle call, once | |||||||||
| After oracle | `½[ | 00⟩ − | 01⟩ + | 10⟩ − | 11⟩ ]` = `( | 0⟩+ | 1⟩)/√2 ⊗ | −⟩` | no relative sign between the ` | 0⟩` and ` | 1⟩` query terms |
| Apply H to query qubit | `H( | 0⟩+ | 1⟩)/√2 = | 0⟩` | exact | ||||||
| Measure | `r = 0` | correctly reports constant |
The only difference between the two runs is whether the oracle introduces a relative minus sign between the `|0⟩` and `|1⟩` branches of the query register — precisely the bit `f(0) ⊕ f(1)` — and the final Hadamard reads that sign out as a clean, error-free classical bit.
Common pitfalls & traps
| Pitfall | Why it happens | Fix | |||||
|---|---|---|---|---|---|---|---|
| Forgetting to initialize the target qubit to ` | -⟩` (using ` | 0⟩` instead) | Without ` | -⟩`, `U_f` writes `f(x)` into the target's computational-basis value instead of a phase, and no kickback occurs | Always prepare target as `H | 1⟩ = | -⟩` before the oracle call |
| Measuring the target qubit expecting to read `f(x)` | The whole point of phase kickback is that the target is left unchanged, in ` | -⟩`, carrying no readable information | Only measure the query qubit; the target is a disposable ancilla | ||||
| Treating the algorithm as probabilistic and averaging over repeated runs | Some learners assume all quantum algorithms are like Grover-style amplitude amplification with error | Deutsch's algorithm is exact: one shot suffices, since the final state is a computational basis state, not a mixed distribution | |||||
| Confusing "one query" with "one gate" | The oracle `U_f` may itself be a nontrivial multi-gate circuit depending on how `f` is implemented | Query complexity counts calls to `U_f` as a unit, separate from its internal gate cost | |||||
| Skipping normalization/phase bookkeeping and getting the wrong final bit | Sign errors in intermediate states are easy to make by hand | Track the relative phase between ` | 0⟩` and ` | 1⟩` terms explicitly at each step, as in the worked traces above |
Pioneers & history
David Deutsch introduced this algorithm in 1985 as part of the foundational paper that first formalized quantum Turing machines and asked whether quantum physics could outperform classical computation on a well-defined task. His original construction (with a probabilistic gap, later cleaned up by Richard Cleve, Artur Ekert, Chiara Macchiavello, and Michele Mosca into the deterministic single-query version presented here) is widely regarded as the first proof-of-concept quantum speedup, even though the problem itself is not practically important — its significance is that it exists at all.
Origins · 1 minDavid Elieser Deutsch and how this was discovered
Deutsch worked at the intersection of quantum mechanics and the theory of computation, motivated by foundational questions about the many-worlds interpretation and the physical limits of computability. His 1985 paper "Quantum theory, the Church-Turing principle and the universal quantum computer" defined a universal quantum computer model and gave the first algorithm — the one in this article — demonstrating a task solvable with fewer physical operations quantumly than classically. This work seeded an entire field, directly inspiring the generalization to many-bit functions and, eventually, Shor's and Grover's algorithms.
Where this matters
Deutsch's algorithm itself is not deployed in production systems — the problem it solves (a one-bit function's global parity) is too small to matter commercially. Its importance is structural: it is the minimal working example of the oracle + superposition + interference pattern that underlies essentially every quantum algorithm with a proven speedup. That pattern reappears directly in The Deutsch-Jozsa Algorithm (n-bit constant-vs-balanced, exponential classical-quantum separation), in the Bernstein-Vazirani algorithm (extracting a hidden bit string in one query), in Simon's algorithm (finding a hidden period via phase interference across many qubits), and ultimately in Shor's factoring algorithm, where the quantum Fourier transform generalizes the single Hadamard used here into an n-qubit interference engine. Every quantum programming framework that teaches the oracle model — from textbook circuit diagrams to real SDKs like Qiskit and Cirq — introduces this exact circuit first, because it is the smallest nontrivial demonstration that measurable interference, not raw parallelism, is the actual source of quantum computational advantage.
Ask the tutor: How does the phase-kickback trick change when the oracle acts on n query qubits instead of one, as in the Deutsch-Jozsa algorithm?
Why does the target qubit end up unchanged after the oracle call?
Because it is prepared in the state `|-⟩ = (|0⟩-|1⟩)/√2`, which is an eigenstate of the bit-flip operator `X`. Applying `X^{f(x)}` to `|-⟩` can only multiply it by the eigenvalue `(-1)^{f(x)}` — it cannot change which state it is, since `X|-⟩ = -|-⟩` and `X⁰|-⟩ = |-⟩` are both proportional to `|-⟩` itself. The oracle's action on the query-target pair `|x⟩|-⟩` therefore factors as `(-1)^{f(x)}|x⟩ ⊗ |-⟩`: the sign attaches to the query branch, and the target register is left in exactly the state it started in, ready to be discarded or reused.
Is the phase kickback trick specific to Deutsch's algorithm, or does it generalize?
It generalizes completely, and is one of the most reused primitives in quantum algorithm design. Any oracle of the form `|x⟩|y⟩ → |x⟩|y ⊕ f(x)⟩` applied to a target in an eigenstate of XOR — such as `|-⟩` — converts the oracle into a pure phase gate `|x⟩ → (-1)^{f(x)}|x⟩` on the query register alone. This exact mechanism scales directly to The Deutsch-Jozsa Algorithm, to Bernstein-Vazirani's hidden string extraction, and to the phase-estimation subroutines inside Shor's algorithm, all of which use a `|-⟩`-like ancilla to turn a classical function evaluation into a phase that later interference steps can read out.
Can Deutsch's algorithm ever give the wrong answer due to a bad random outcome?
No. Unlike algorithms such as Grover's search, which succeed with high probability rather than certainty, Deutsch's algorithm is fully deterministic given a perfect, noiseless oracle. The proof in the correctness section shows the post-interference state is exactly `|0⟩` when `f` is constant and exactly `|1⟩` when `f` is balanced — there is no superposition left to collapse randomly at measurement time. In a real noisy device, gate errors and decoherence can of course introduce mistakes, but that is a hardware limitation, not a flaw in the algorithm's logical structure.
Why is querying "in superposition" more powerful than querying twice classically?
A classical query returns one committed bit of information: you ask `f(0)`, you get back a definite value, and that branch of computation forgets about `f(1)` entirely. A quantum query applied to a superposition of `|0⟩` and `|1⟩` keeps both branches alive simultaneously inside one evolving state, each acquiring its own phase `(-1)^{f(x)}`. The subsequent Hadamard then combines both branches through interference, extracting a comparison between `f(0)` and `f(1)` — a global property — without ever separately reading either value. This is fundamentally different information extraction than sequential classical lookups.
Does this algorithm have any practical use, or is it purely educational?
It is essentially purely educational and historical; a one-bit function's constant-versus-balanced status has no independent computational value in applications. Its role is as the cleanest possible teaching example of how interference can extract a global function property in fewer queries than any classical strategy allows. Every subsequent algorithm relying on the oracle-plus-interference paradigm — the Deutsch-Jozsa algorithm, Simon's algorithm, and the quantum Fourier transform machinery in Shor's algorithm — builds directly on the mechanism first isolated here, which is why it remains the standard opening example in every course and text.
What role does the Hadamard gate play at each stage of the circuit?
The Hadamard gate plays two distinct roles. On the target qubit, a single Hadamard (applied to `|1⟩`) prepares the `|-⟩` eigenstate needed to trigger phase kickback — this is a setup role. On the query qubit, Hadamards bracket the oracle call: the first creates the superposition `(|0⟩+|1⟩)/√2` that lets the oracle be queried "at both inputs at once," and the second converts the relative phase produced by the oracle back into a distinguishable computational-basis state. This second Hadamard is the interference step — it is literally the Hadamard transform on one qubit acting as an interferometer between the two branches.
How does this connect to the Deutsch-Jozsa algorithm?
Deutsch-Jozsa is the direct n-qubit generalization: given `f : {0,1}^n → {0,1}` promised to be either constant or balanced, the same circuit skeleton — Hadamards, one oracle call, phase kickback via a `|-⟩` ancilla, Hadamards again, measurement — determines which case holds in a single query. The n=1 case reduces exactly to the algorithm in this article. The generalization is where the speedup becomes asymptotically dramatic: classically up to `2^{n-1}+1` queries are needed in the worst case, while the quantum algorithm still needs only one, making this small example the seed of a genuinely exponential separation.