Deutsch's Algorithm

Deutsch's algorithm is the smallest complete quantum program that beats every classical one, and its whole job is to answer a single yes-or-no question about a black box. You are handed a one-bit function $f:\{0,1\}\to\{0,1\}$ that you may only call, never inspect, and asked whether it is constant — the same on both inputs — or balanced — different on the two. Equivalently, compute the parity $f(0)\oplus f(1)$ , which is $0$ when $f$ is constant and $1$ when it is balanced. Cost is counted in oracle calls, and here the classical world is boxed in: parity is a joint property of both values, so a deterministic machine must evaluate $f(0)$ and $f(1)$ — two queries — before it can answer. David Deutsch showed in 1985 that a quantum computer needs exactly one. The trick is not that it "evaluates $f$ on both inputs at once" — that alone buys nothing, since reading the result gives one random value. The advantage lives entirely in interference. A Hadamard splits the input qubit across both branches; the oracle, fed an ancilla in $|-\rangle$ , stamps each branch with a phase $(-1)^{f(x)}$ by phase kickback; and a final Hadamard recombines the branches so the parity — a global property no single query can see — lands deterministically in the measured bit. Every ingredient here reappears, scaled up, in Deutsch–Jozsa, Bernstein–Vazirani, Simon, and the quantum Fourier transform behind Shor. It is the cleanest proof that quantum speedup is interference, not parallelism.

Key takeaways

Deutsch's algorithm decides whether an unknown one-bit function $f:\{0,1\}\to\{0,1\}$ is constant ( $f(0)=f(1)$ ) or balanced ( $f(0)\neq f(1)$ ) with a single query to a reversible oracle — half the classical deterministic cost of two.
The answer is the parity $f(0)\oplus f(1)$ : it equals $0$ for a constant function and $1$ for a balanced one.
The engine is phase kickback: feeding the oracle's target qubit the state $|-\rangle=\tfrac{1}{\sqrt2}(|0\rangle-|1\rangle)$ turns the bit-flip $|y\rangle\to|y\oplus f(x)\rangle$ into a pure phase $(-1)^{f(x)}$ on the control.
Hadamards create the superposition, the oracle imprints $(-1)^{f(x)}$ , and a final Hadamard interferes the two branches so the control collapses deterministically to $|f(0)\oplus f(1)\rangle$ .
The speedup is only a factor of two, but the circuit is the conceptual seed of Deutsch–Jozsa, Bernstein–Vazirani, Simon, and Shor — quantum advantage from interference, not from evaluating many inputs at once.
Key idea: prepare the control in $|+\rangle$ and the ancilla in $|-\rangle$ ; the XOR oracle kicks back $(-1)^{f(x)}$ onto the control, and a final Hadamard converts the relative sign $(-1)^{f(0)\oplus f(1)}$ into the measured bit — the parity, read in one query.

The core insight

Prepare the control qubit in an equal superposition and the target qubit in $|-\rangle=\tfrac{1}{\sqrt2}(|0\rangle-|1\rangle)$ . The XOR oracle $U_f:|x\rangle|y\rangle\to|x\rangle|y\oplus f(x)\rangle$ then kicks back a phase $(-1)^{f(x)}$ onto the control. A final Hadamard interferes the $x=0$ and $x=1$ branches so that the control collapses to $|f(0)\oplus f(1)\rangle$ — the parity, read out in one shot.

Where this lives today

Because it needs only two qubits, a handful of gates, and a deterministic answer, Deutsch's algorithm was one of the very first quantum programs run on real hardware and remains a standard "hello world" for a new processor. In 1998 Jones and Mosca implemented it on a liquid-state nuclear-magnetic-resonance computer using the two spins of a chloroform molecule, and the deterministic version has since been demonstrated on trapped ions — a single calcium ion at Innsbruck ran the Deutsch–Jozsa generalization in 2003 — as well as on photonic, nitrogen-vacancy, and superconducting platforms. On today's chips it is less a computation than a diagnostic: observing the correct deterministic outcome across all four oracles is a compact end-to-end test of state preparation, a two-qubit interaction, phase coherence, and readout. Conceptually the circuit has grown up into the hidden-subgroup problem: it is the smallest instance of Fourier sampling over $\mathbb{Z}_2$ , the same abstraction whose $\mathbb{Z}_2^n$ and $\mathbb{Z}_N$ cases give Bernstein–Vazirani, Simon, and — via the quantum Fourier transform — Shor's factoring algorithm. The open frontier it points to is quantum query complexity: how large a gap between quantum and classical query counts is possible, a question running from the modest factor of two here to the exponential and (for total functions) provably-bounded polynomial separations that occupy complexity theory now.

The physical picture

Think of the control qubit as a wave sent down a two-arm interferometer whose arms are the two inputs, $x=0$ and $x=1$ . The first Hadamard is the beam-splitter: equal amplitude into both arms. The oracle is a pair of phase plates, one per arm, each stamping its arm with $(-1)^{f(x)}$ . The second Hadamard recombines them. If both arms carry the same sign — constant $f$ — the branches interfere constructively at the $|0\rangle$ detector; if they carry opposite signs — balanced $f$ — they land at the $|1\rangle$ detector. One measurement reads which kind of function the box held. The first figure lays the circuit out gate by gate.

Figure

The Deutsch circuit: the control qubit starts in the zero-state and the ancilla in the one-state; a Hadamard layer builds the plus and minus states, the oracle U_f kicks back a phase (−1) to the power f(x), and a final Hadamard on the control makes it collapse to the single bit f(0)⊕f(1), read out in one query

Phase kickback is the conceptual heart, and it is worth stating plainly: the oracle is physically a controlled bit-flip on the ancilla, yet the ancilla never changes and is never measured. The reason is that $|-\rangle$ is an eigenstate of the flip $X$ with eigenvalue $-1$ , so flipping it does nothing but return that eigenvalue — a sign $(-1)^{f(x)}$ that "kicks back" onto the control register. The ancilla is a catalyst: it converts data (the value $f(x)$ ) into phase, and hands the phase to the qubit we care about while returning to $|-\rangle$ untouched. The second figure is the punchline — the deterministic measured bit for all four possible oracles.

Figure

Deterministic readout for all four one-bit oracles: the two constant functions leave the branch signs equal and the control lands on the zero-state with probability 1.00, while the two balanced functions flip the relative sign and send it to the one-state with probability 1.00; before the final Hadamard each branch carries amplitude ±1/√2 ≈ ±0.707

The reason the classical world cannot match this is about access, not cleverness. A single classical query returns one number, $f(x)$ , and the parity $f(0)\oplus f(1)$ is a nonlocal function of both values. The quantum query, applied to a superposition, encodes a coherent combination of both branches, and the final Hadamard discards the useless per-input information while keeping exactly the relative phase that is the parity.

The core equations

We start by naming the task precisely: the box hides one of four functions, and the algorithm must report a single output bit that distinguishes the two constant boxes from the two balanced ones.

f:\{0,1\}\to\{0,1\},\qquad \text{decide } f(0)\oplus f(1) \qquad (1)

where: $f$ — unknown one-bit Boolean function accessed only through the oracle; $f(0)\oplus f(1)$ — the parity bit, $0$ if $f$ is constant and $1$ if balanced. The reading: four functions but only two answers, so the algorithm computes a two-to-one property, not the full truth table. Because a quantum gate must be reversible, the function is supplied not as an irreversible map but as the reversible XOR oracle, which writes $f(x)$ into an ancilla register without destroying the input.

U_f\,|x\rangle|y\rangle = |x\rangle\,|y\oplus f(x)\rangle \qquad (2)

where: $x$ — input (control) register, the argument of $f$ ; $y$ — target/ancilla register recording the output; $\oplus$ — addition modulo $2$ (XOR); $U_f$ — a unitary that is its own inverse, since $f(x)\oplus f(x)=0$ . The reading: the input is preserved and the output is added into $y$ rather than overwriting it — the only reversible way to expose a function to a quantum circuit. The single-qubit Hadamard is the interferometer's beam-splitter; written as a matrix and as a sum it makes both the superposition and the hidden Fourier structure explicit.

H = \frac{1}{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix},\qquad H|x\rangle = \frac{1}{\sqrt2}\sum_{z\in\{0,1\}}(-1)^{xz}|z\rangle \qquad (3)

where: $H$ — the single-qubit Hadamard, with $H^2=I$ ; $(-1)^{xz}$ — the sign generated by the bit product, the $\mathbb{Z}_2$ Fourier kernel. The reading: $H$ turns a definite bit into an equal superposition and, run in reverse, turns a sign pattern back into a definite bit — the create-and-read symmetry the algorithm exploits at both ends. The pivotal identity is phase kickback: on the special ancilla state $|-\rangle$ , the bit-flip oracle stops flipping anything and becomes a pure phase on the control.

U_f\,|x\rangle|-\rangle = (-1)^{f(x)}\,|x\rangle|-\rangle \qquad (4)

where: $|-\rangle=\tfrac{1}{\sqrt2}(|0\rangle-|1\rangle)$ — the eigenstate of $X$ with eigenvalue $-1$ ; $(-1)^{f(x)}$ — the eigenvalue kicked back onto the control while the ancilla is left untouched. The reading: this one line makes a single query enough — it converts the oracle from a data-copier into a phase-stamper, and Derivation B proves it term by term. State preparation sets the interferometer up: the control is spread across both inputs and the ancilla is loaded into the kickback state.

|\psi_0\rangle = |0\rangle|1\rangle \;\xrightarrow{\,H\otimes H\,}\; |+\rangle|-\rangle = \tfrac{1}{\sqrt2}\big(|0\rangle+|1\rangle\big)|-\rangle \qquad (5)

where: $|+\rangle=\tfrac{1}{\sqrt2}(|0\rangle+|1\rangle)$ — equal superposition of both inputs; $|0\rangle|1\rangle$ — the initial two-qubit state, control $|0\rangle$ and ancilla $|1\rangle$ . The reading: the ancilla is initialized to $|1\rangle$ precisely so that its Hadamard yields $|-\rangle$ , the state kickback needs. One oracle call now stamps each branch of the control with its phase, and — this is the crucial bookkeeping — the ancilla factors cleanly out of the state.

|\psi_2\rangle = \Big[\tfrac{1}{\sqrt2}\sum_{x}(-1)^{f(x)}|x\rangle\Big]\,|-\rangle \qquad (6)

where: $\sum_x$ — sum over $x\in\{0,1\}$ , the two input branches; $(-1)^{f(x)}$ — the branch-dependent phase imprinted by kickback. The reading: the control now carries the entire function in its two signs, and the ancilla, unentangled, can be ignored for the rest of the circuit. The final Hadamard on the control converts the relative sign between the branches into a definite bit — the parity — leaving only an unobservable global phase.

(H\otimes I)|\psi_2\rangle = (-1)^{f(0)}\,|f(0)\oplus f(1)\rangle\,|-\rangle \qquad (7)

where: $|f(0)\oplus f(1)\rangle$ — the control qubit, deterministically encoding the answer; $(-1)^{f(0)}$ — a global phase, invisible to any measurement. The reading: the answer is now in the computational basis, so a single $Z$ -measurement reads it with certainty. Collecting the four cases, the outcome is deterministic, not statistical — the Born-rule probability is exactly $0$ or $1$ .

\Pr[\text{measure } 0]=\begin{cases}1 & f\text{ constant}\\[2pt]0 & f\text{ balanced}\end{cases} \qquad (8)

where: $\Pr[\cdot]$ — Born-rule probability. The reading: no averaging over repeated runs is needed — one query, one shot, one certain bit.

Derivation ASingle-query determination of the parity

The goal is to follow the two-qubit state all the way through the circuit $H^{\otimes2}\to U_f\to (H\otimes I)\to$ measure, and to prove that the control qubit ends up in the exact computational-basis state $|f(0)\oplus f(1)\rangle$ regardless of which of the four oracles was hidden in the box. The strategy is to keep the ancilla factored out at every step using phase kickback, so the entire computation reduces to tracking two amplitudes on a single qubit, and then to pull out a global phase so the final Hadamard acts on a recognizable input. This is the calculation that turns "one query suffices" from a claim into an identity.

Step 3. Apply the oracle and use kickback, $U_f|x\rangle|-\rangle=(-1)^{f(x)}|x\rangle|-\rangle$ , giving $|\psi_2\rangle=\big[\tfrac{1}{\sqrt2}\sum_x(-1)^{f(x)}|x\rangle\big]|-\rangle$ . Why: because the ancilla is unchanged it factors out completely, so from here the problem is purely about the two signs on the control — the whole function has been compressed into a phase pattern.

Step 4. Pull out the global phase: $\tfrac{1}{\sqrt2}\sum_x(-1)^{f(x)}|x\rangle=(-1)^{f(0)}\tfrac{1}{\sqrt2}\big(|0\rangle+(-1)^{f(0)\oplus f(1)}|1\rangle\big)$ . Why: factoring $(-1)^{f(0)}$ isolates the only physically meaningful quantity — the relative sign $(-1)^{f(0)\oplus f(1)}$ between the branches, which is exactly the parity.

Step 5. Apply the final Hadamard, using $H\tfrac{1}{\sqrt2}(|0\rangle+(-1)^{a}|1\rangle)=|a\rangle$ with $a=f(0)\oplus f(1)$ , since $H|+\rangle=|0\rangle$ and $H|-\rangle=|1\rangle$ . Why: this is the recombining beam-splitter — it maps the relative sign into a definite computational-basis state, converting phase into a readable bit.

Step 6. Measure the control: the result is $a=f(0)\oplus f(1)$ , obtained with a single oracle call — $0$ for a constant $f$ , $1$ for a balanced $f$ . Why: the state is already an eigenstate of $Z$ , so the measurement is deterministic; the ignored ancilla remained in $|-\rangle$ throughout. *Substituting all four functions reproduces the four-case table of the second figure; the ancilla stays in $|-\rangle$ at every step, confirming a single query is sufficient and deterministic.*

Go deeper · Derivation B · 1 minWhy the bit oracle becomes a phase oracle on the minus-state

Derivation BWhy the bit oracle becomes a phase oracle on the minus-state

The aim is to prove the phase-kickback identity $U_f|x\rangle|-\rangle=(-1)^{f(x)}|x\rangle|-\rangle$ directly from the definition of the XOR oracle, without appealing to eigenvalue intuition, so that the single most important line in the algorithm rests on nothing but the modular arithmetic of the ancilla. The plan is to write $|-\rangle$ as a difference of computational-basis states, let the oracle act on each term, and then examine the two possible values of $f(x)$ separately, showing both collapse into one sign. This is the step that upgrades "the oracle stamps a phase" from a slogan into an algebraic fact.

Step 1. Expand the ancilla and distribute the oracle: $U_f|x\rangle|-\rangle=\tfrac{1}{\sqrt2}\big(|x\rangle|0\oplus f(x)\rangle-|x\rangle|1\oplus f(x)\rangle\big)$ . Why: the oracle acts linearly on the ancilla's two components, so its effect is fixed once we know how it moves $|0\rangle$ and $|1\rangle$ under XOR with $f(x)$ .

Step 2. Collect the ancilla factor: $=\tfrac{1}{\sqrt2}\,|x\rangle\big(|f(x)\rangle-|1\oplus f(x)\rangle\big)$ , since $0\oplus f(x)=f(x)$ . Why: writing the two ancilla labels in terms of $f(x)$ sets up a clean case split on the single bit $f(x)$ , which is all that can vary.

Step 3. Split on $f(x)$ : if $f(x)=0$ the ancilla is $|0\rangle-|1\rangle=\sqrt2\,|-\rangle$ ; if $f(x)=1$ it is $|1\rangle-|0\rangle=-\sqrt2\,|-\rangle$ . Why: XOR-ing by $1$ swaps the two kets of $|-\rangle$ , and swapping the terms of an antisymmetric combination is the same as multiplying by $-1$ — the geometric origin of the sign.

Step 4. Merge the cases: both read $(-1)^{f(x)}\,|x\rangle|-\rangle$ , so $U_f|x\rangle|-\rangle=(-1)^{f(x)}|x\rangle|-\rangle$ with the ancilla returned to $|-\rangle$ . Why: the two branches of the case split unify into one exponent $(-1)^{f(x)}$ , which is exactly the phase-oracle form the algorithm consumes in Derivation A. *For $f(x)=0$ the identity gives $+1$ and for $f(x)=1$ it gives $-1$ , matching direct evaluation; the ancilla is an eigenvector of the oracle with those eigenvalues, so it never entangles with the control.*

Go deeper · Derivation C · 1 minThe classical deterministic lower bound of two queries

Derivation CThe classical deterministic lower bound of two queries

The purpose is to prove that no classical deterministic algorithm can decide constant-versus-balanced with a single query, so the quantum single-query result is a genuine separation rather than an artifact of a weak baseline. The method is an adversary argument: suppose an algorithm makes only one query, observe that one value of $f$ is thereby left entirely unconstrained, and exhibit two functions consistent with the observation that have opposite parities — forcing any one-query rule to be wrong on at least one. This pins the classical cost at exactly two.

Step 1. A single classical query at input $x_1$ returns exactly one value, $f(x_1)=b$ , and nothing else. Why: a classical oracle is a lookup — it reveals the value at the queried point only, with no access to the other input.

Step 2. Run the adversary: the unqueried value $f(\bar x_1)$ is still free to be $b$ (making $f$ constant) or $\bar b$ (making $f$ balanced), and both are fully consistent with the one observation. Why: since the algorithm never touched $\bar x_1$ , an adversary is free to fix that value after seeing the query, choosing whichever answer defeats the algorithm.

Step 3. Conclude that the parity is undetermined: $f(0)\oplus f(1)\in\{0,1\}$ are both possible, so any deterministic output based on $b$ alone is wrong in one of the two worlds. Why: a fixed rule mapping the single observed bit to an answer cannot be correct for two inputs demanding opposite answers.

Step 4. Therefore at least two queries are required classically, whereas the quantum circuit needs one — the factor-two separation $Q^{\det}_{\text{classical}}=2$ , $Q_{\text{quantum}}=1$ , the first known quantum advantage. Why: a second query resolves $f(\bar x_1)$ and hence the parity, so two is both necessary and sufficient classically. *The adversary construction exhibits, for any queried point and observed bit, one constant and one balanced completion, so one classical query provably cannot decide the parity.*

Limiting cases

The four possible functions and their outcomes make the determinism completely explicit — every case funnels into one of just two measured bits.

Case	Result	Meaning
Constant $f\equiv 0$	$f(0)=f(1)=0\;\Rightarrow\; f(0)\oplus f(1)=0$	branch signs $(+,+)$ ; control returns $\vert 0\rangle$ deterministically — reports constant
Constant $f\equiv 1$	$f(0)=f(1)=1\;\Rightarrow\; f(0)\oplus f(1)=0$	branch signs $(-,-)$ differ only by a global sign; control still returns $\vert 0\rangle$ — reports constant
Balanced (identity) $f(x)=x$	$f(0)\oplus f(1)=1$	branch signs $(+,-)$ ; control returns $\vert 1\rangle$ — reports balanced
Balanced (NOT) $f(x)=1\oplus x$	$f(0)\oplus f(1)=1$	branch signs $(-,+)$ ; control returns $\vert 1\rangle$ — reports balanced

Common trapThe speedup is not "evaluating f on both inputs at once"

The most common misreading is that the power comes from quantum parallelism — the fact that after the oracle the control "contains both function values." It does, in the state $\tfrac{1}{\sqrt2}\sum_x(-1)^{f(x)}|x\rangle$ , but a measurement there yields $0$ or $1$ with equal probability and tells you nothing about $f$ — no better than one classical query. The advantage comes entirely from the final Hadamard, which interferes the branches so the parity becomes deterministically measurable. Two further traps: the deterministic answer requires the ancilla in $|-\rangle$ — with it in $|0\rangle$ the oracle merely copies $f(x)$ in, entangles it with the control, and destroys the interference; and the separation is only a factor of two, not exponential — the exponential gaps belong to the scaled-up successors, above all Simon's algorithm.

Worked examples

1 · Running the balanced oracle f(x) = x end to end (fully worked)

The box hides the identity function $f(x)=x$ , so $f(0)=0$ and $f(1)=1$ . Track the two-qubit state through the whole circuit with explicit amplitudes and confirm the measurement returns $1$ (balanced).

Step 1. Initialize and split. Start from $|0\rangle|1\rangle$ and apply $H\otimes H$ : the control becomes $|+\rangle=\tfrac{1}{\sqrt2}(|0\rangle+|1\rangle)$ with each branch at amplitude $1/\sqrt2\approx\mathbf{0.707}$ , and the ancilla becomes $|-\rangle$ . The state is $\tfrac{1}{\sqrt2}(|0\rangle+|1\rangle)|-\rangle$ .

Step 2. Apply the oracle by kickback. The branch phases are $(-1)^{f(0)}=(-1)^0=+1$ and $(-1)^{f(1)}=(-1)^1=-1$ , so the control becomes $\tfrac{1}{\sqrt2}\big(+|0\rangle-|1\rangle\big)=|-\rangle$ , with amplitudes $+0.707$ and $-0.707$ . The oracle flipped only the $x=1$ branch's sign — the balanced signature $(+,-)$ .

Step 4. Measure. $\Pr[\text{outcome }1]=|1|^2=\mathbf{1.00}$ and $\Pr[\text{outcome }0]=0$ . The algorithm reports $f(0)\oplus f(1)=1$ , balanced, with certainty — from a single call to $U_f$ .

2 · The constant oracle f ≡ 1 and the harmless global phase

Now the box hides $f\equiv 1$ , so $f(0)=f(1)=1$ . Show the control returns $0$ (constant) and that the overall minus sign it picks up is undetectable.

Step 1. After $H\otimes H$ the control is again $\tfrac{1}{\sqrt2}(|0\rangle+|1\rangle)$ . Both branch phases are now $(-1)^1=-1$ , so the oracle gives $\tfrac{1}{\sqrt2}(-|0\rangle-|1\rangle)=-|+\rangle$ — branch signs $(-,-)$ , an overall factor of $-1$ on the state $|+\rangle$ .

Step 2. Apply the final Hadamard: $H(-|+\rangle)=-H|+\rangle=-|0\rangle$ . The control is $-|0\rangle$ , so $\Pr[\text{outcome }0]=|-1|^2=\mathbf{1.00}$ . The reported bit is $f(0)\oplus f(1)=0$ , constant — correct.

Step 3. The prefactor $-1$ is a global phase: it multiplies the entire state and cancels in the Born rule, $|-1|^2=1$ . It is exactly the $(-1)^{f(0)}$ of equation (7). Constant $f\equiv 0$ and constant $f\equiv 1$ therefore give the same measured answer $0$ despite differing by this invisible sign — the algorithm distinguishes only the parity, never $f(0)$ itself.

Physics of the portrait

Deutsch's algorithm is a one-page circuit, but it carries an outsized idea: that the laws of physics, not the axioms of Turing, set the true limits of computation. That thesis, and the algorithm that first made it concrete, belong to one person.

Origins · 1 minDavid Deutsch and how this was discovered

David Deutsch

1953– · the physicist who founded quantum computation and wrote its first algorithm

David Deutsch, born in Haifa in 1953 and long based at the Clarendon Laboratory in Oxford, is the founder of the quantum theory of computation. In a landmark 1985 paper — Quantum theory, the Church–Turing principle and the universal quantum computer — he argued that the Church–Turing thesis should be grounded in physics rather than mathematics, defined the universal quantum computer as the machine that can simulate any physical process, and, to prove such a machine could outperform its classical counterpart, exhibited the single-query algorithm that now bears his name. His motivation was famously interpretational: a committed proponent of the Everett "many-worlds" picture, Deutsch saw quantum computation as tangible evidence for the reality of the parallel branches whose interference the algorithm exploits. With Richard Jozsa in 1992 he generalized the result to $n$ bits with an exponential separation, and he helped build the language of quantum logic gates and networks circuit diagrams still use. Beyond algorithms he formulated constructor theory and reached a wide audience through The Fabric of Reality (1997) and The Beginning of Infinity (2011). A Fellow of the Royal Society, he shared the 2023 Breakthrough Prize in Fundamental Physics with Bennett, Brassard, and Shor for foundational work in quantum information.

History

1985

— Deutsch defines the universal quantum computer and gives the first quantum algorithm, in its original probabilistic form

1992

— Deutsch and Jozsa generalize to n bits with a deterministic exponential query separation

1993

— Bernstein and Vazirani formalize quantum query complexity and recursive Fourier sampling

1994

— Simon's algorithm delivers a provable exponential oracle separation, inspiring Shor

1998

— Cleve, Ekert, Macchiavello, and Mosca give the clean deterministic single-query version, and Jones and Mosca run it on an NMR quantum computer

Going further

Texts. Nielsen & Chuang, Quantum Computation and Quantum Information, §1.4.3–1.4.4 (Deutsch and Deutsch–Jozsa) and §5 (Fourier context) · Preskill, Lecture Notes on Quantum Computation, Ch. 6 · Watrous, The Theory of Quantum Information and lecture notes on query algorithms · Wilde, Quantum Information Theory, Ch. 3 (oracle and query model) · Kitaev, Shen & Vyalyi, Classical and Quantum Computation, §8 · Mermin, Quantum Computer Science, Ch. 2. The full state evolution is $|0\rangle|1\rangle\to|+\rangle|-\rangle\to[\tfrac{1}{\sqrt2}\sum_x(-1)^{f(x)}|x\rangle]|-\rangle\to(-1)^{f(0)}|f(0)\oplus f(1)\rangle|-\rangle$ , and substituting all four oracles confirms the four-case table. The phase-kickback identity $U_f|x\rangle|-\rangle=(-1)^{f(x)}|x\rangle|-\rangle$ and the classical two-query adversary bound are standard results. The deterministic ancilla-in- $|-\rangle$ formulation is due to Cleve, Ekert, Macchiavello & Mosca, Proc. R. Soc. Lond. A 454, 339 (1998); the original probabilistic algorithm appears in Deutsch, Proc. R. Soc. Lond. A 400, 97 (1985). The Hadamard conventions satisfy $H|\pm\rangle=|0/1\rangle$ . The first hardware demonstration is Jones & Mosca, J. Chem. Phys. 109, 1648 (1998). The only numerical constants used are the branch amplitudes $\pm1/\sqrt2\approx\pm0.707$ and the deterministic measurement probabilities $0$ and $1$ .

Prerequisites. Quantum Parallelism and the Oracle Model · Hadamard gate and single-qubit states · Tensor products and computational basis. Leads to. Deutsch–Jozsa Algorithm · Bernstein–Vazirani Algorithm · Simon's Algorithm · Quantum Fourier Transform.

Ask the tutor: ask me to run any of the four oracles through the circuit amplitude by amplitude, prove the phase-kickback identity, or show exactly how Deutsch's one-qubit trick scales up into Deutsch–Jozsa and Simon's algorithm.

Is Deutsch's algorithm actually useful for anything practical?

Not directly — deciding whether a one-bit function is constant or balanced is a toy problem, and its speedup is a factor of two, not the exponential gap that makes Shor's algorithm threatening. Its value is conceptual. Every mechanism it isolates — building a superposition with Hadamards, imprinting a phase by kickback, and reading out a global property by interference — is the exact skeleton of the algorithms that are powerful: Deutsch–Jozsa, Bernstein–Vazirani, Simon, and, through the quantum Fourier transform, Shor. Learning Deutsch's circuit is learning the grammar those algorithms are written in, with the distracting machinery stripped away.

Why must the ancilla be in the minus-state rather than the zero-state?

Because $|-\rangle$ is an eigenstate of the bit-flip $X$ with eigenvalue $-1$ , so the oracle's controlled flip cannot actually change it — instead it returns the eigenvalue $(-1)^{f(x)}$ , which "kicks back" onto the control as a phase. That phase is the whole point: it is what the final Hadamard later converts into the answer. If you instead prepared the ancilla in $|0\rangle$ , the oracle would copy $f(x)$ into it, entangling the ancilla with the control. Measuring the control would then give a random input value and no relative phase — exactly the useless "parallelism only" outcome, no better than one classical query.

What exactly is phase kickback?

Phase kickback is the phenomenon by which a controlled operation deposits a phase on its control register instead of visibly changing its target. It happens whenever the target is an eigenstate of the operation being controlled. Here the controlled operation is the bit-flip $X^{f(x)}$ , and the target $|-\rangle$ is an eigenstate of $X$ with eigenvalue $-1$ , so applying it multiplies the state by $(-1)^{f(x)}$ while leaving $|-\rangle$ intact. The same trick, with the eigenvalue $e^{2\pi i\varphi}$ of a general unitary instead of a sign, is the engine of quantum phase estimation and hence Shor's order-finding routine — Deutsch's circuit is its minimal case.

If the state after the oracle contains both values of f, why can't I just measure it?

Because those values are stored in the relative phase between the two branches, and a computational-basis measurement is blind to phase. After the oracle the control is $\tfrac{1}{\sqrt2}\sum_x(-1)^{f(x)}|x\rangle$ ; both branches have magnitude $1/\sqrt2$ , so measuring gives $0$ or $1$ with probability one-half each, learning nothing about the signs. The information is real but hidden. The final Hadamard rotates that phase difference into a population difference — a definite bit — which is why the power sits in the interference step, not the superposition the oracle produced.

Is the quantum speedup here exponential, like in Shor's algorithm?

No — it is only a factor of two: one quantum query against two classical deterministic queries. That modesty is important to state honestly, because Deutsch's algorithm is often oversold. The exponential separations appear only in the scaled-up descendants. Deutsch–Jozsa beats deterministic classical algorithms exponentially (though a randomized classical algorithm solves it with a few queries), and Simon's algorithm gives a genuine, provable exponential gap even against randomized classical machines — the result that directly inspired Shor. Deutsch's circuit is the conceptual seed of all of them, but its own advantage is a constant factor, valuable as a proof of principle rather than as a computational win.

Does the two constant functions giving the same answer mean information is lost?

Yes, deliberately — that is the design, not a flaw. The algorithm computes a single bit, the parity $f(0)\oplus f(1)$ , which by definition cannot distinguish $f\equiv 0$ from $f\equiv 1$ : both are constant, both have parity $0$ . The output carries a global phase $(-1)^{f(0)}$ that does differ between them, but a global phase is physically undetectable, so the measurement reports $0$ for both. To learn $f(0)$ itself you would need another query. Deutsch's algorithm trades away individual values in exchange for extracting the one joint property it was asked about in a single call.