Deutsch-Jozsa Oracle Separation

Derivation

Deutsch-Jozsa Oracle Separation

D-411 Home PU-404 Threads chance · symmetry · waves Depends on Universality of CNOT with Single-Qubit Gates

Statement

For a Boolean function \( f:\{0,1\}^n \to \{0,1\} \) promised to be either constant (one output value on all inputs) or balanced (output \(0\) on exactly \(2^{n-1}\) inputs and \(1\) on the other \(2^{n-1}\)), a single evaluation of the reversible oracle \(U_f:\;|x\rangle|y\rangle \mapsto |x\rangle|y\oplus f(x)\rangle\), flanked by Hadamard walls and terminated by a computational-basis measurement, returns the all-zeros string \(0^n\) with probability \(1\) if and only if \(f\) is constant. Any deterministic classical algorithm certifying the same promise needs \(2^{n-1}+1\) queries in the worst case.

Why it matters

This is the first clean, unconditional separation between the exact quantum and exact classical query complexities of a total-promise problem: one quantum query versus an exponential number of classical ones. It is the ancestor of Simon's algorithm and, through it, of Shor's period-finding, because all three rest on the same mechanism — encode a global property of \(f\) into relative phases, then read it out with a Fourier transform over the group \((\mathbb{Z}_2)^n\).

Pedagogically it isolates the three levers of quantum advantage in their simplest form: uniform superposition (query all inputs at once), phase kickback (write \(f\) into phases without disturbing the ancilla), and interference (make the wrong answers cancel). No entanglement between query qubits is even required.

Assumptions

The oracle is a genuine unitary \(U_f\) implementing \(|x\rangle|y\rangle \mapsto |x\rangle|y\oplus f(x)\rangle\).If \(f\) were only available as a classical black box returning bits, the phase-kickback trick is unavailable and no quantum speedup survives; the reversibility (XOR-into-ancilla) form is what makes \(U_f\) unitary and hence physically realizable from the assumed universal gate set.

The promise holds: \(f\) is exactly constant or exactly balanced.For a general \(f\) the amplitude on \(0^n\) takes an intermediate value, the measurement is no longer deterministic, and the single-query certainty claim is false — the algorithm then only estimates a bias.

Hadamard gates and \(U_f\) act coherently, with no decoherence or gate error between preparation and measurement.Any dephasing on the query register degrades the interference so that "balanced" no longer forbids the \(0^n\) outcome with certainty; the separation becomes statistical rather than exact.

The ancilla is prepared in \(|1\rangle\) so that after its Hadamard it sits in the \(-1\) eigenstate \(|-\rangle\) of the bit-flip induced by \(f\).If the ancilla were left in \(|0\rangle\) (giving \(|+\rangle\)), the oracle would merely permute basis states of the ancilla instead of stamping a phase on the query register, and no phase information about \(f\) would reach the query qubits.

Derivation

\[ |\psi_0\rangle \;=\; |0\rangle^{\otimes n}\,\otimes\,|1\rangle . \]

Prepare \(n\) query qubits in \(|0\rangle\) and one ancilla in \(|1\rangle\); product state of independently initialized qubits. A

\[ |\psi_1\rangle \;=\; H^{\otimes n}|0\rangle^{\otimes n}\otimes H|1\rangle \;=\; \frac{1}{\sqrt{2^{\,n}}}\sum_{x\in\{0,1\}^n}|x\rangle \;\otimes\; |-\rangle , \qquad |-\rangle=\tfrac{1}{\sqrt2}\big(|0\rangle-|1\rangle\big). \]

Apply a Hadamard wall. Each \(H|0\rangle=|+\rangle\) and the tensor product of \(n\) of them is the uniform superposition over all \(2^n\) inputs; \(H|1\rangle=|-\rangle\). This is the Fourier transform over \((\mathbb{Z}_2)^n\) applied to the zero string. A

\[ U_f\,|x\rangle|-\rangle \;=\; \tfrac{1}{\sqrt2}\big(|x\rangle|0\oplus f(x)\rangle-|x\rangle|1\oplus f(x)\rangle\big) \;=\; (-1)^{f(x)}\,|x\rangle|-\rangle . \]

Phase kickback. For \(f(x)=0\) the ancilla returns to \(\tfrac{1}{\sqrt2}(|0\rangle-|1\rangle)=|-\rangle\); for \(f(x)=1\) it becomes \(\tfrac{1}{\sqrt2}(|1\rangle-|0\rangle)=-|-\rangle\). Thus \(|-\rangle\) is an eigenvector of the \(f\)-controlled bit flip with eigenvalue \((-1)^{f(x)}\), and the phase migrates onto the query register. B

\[ |\psi_2\rangle \;=\; U_f|\psi_1\rangle \;=\; \frac{1}{\sqrt{2^{\,n}}}\sum_{x}(-1)^{f(x)}\,|x\rangle \;\otimes\; |-\rangle . \]

Linearity of \(U_f\) applied term by term to Step 2, using Step 3. The ancilla factorizes out and is never touched again, so we drop it. A

\[ H^{\otimes n}|x\rangle \;=\; \frac{1}{\sqrt{2^{\,n}}}\sum_{z\in\{0,1\}^n}(-1)^{\,x\cdot z}\,|z\rangle , \qquad x\cdot z \equiv \bigoplus_{i=1}^{n}x_i z_i . \]

The single-qubit identity \(H|a\rangle=\tfrac{1}{\sqrt2}\sum_{b}(-1)^{ab}|b\rangle\) tensored over the \(n\) qubits; the product of signs \(\prod_i(-1)^{x_i z_i}\) collapses to \((-1)^{x\cdot z}\) with \(x\cdot z\) the mod-2 inner product. This is the character of \((\mathbb{Z}_2)^n\) labelled by \(x\). B

\[ |\psi_3\rangle \;=\; H^{\otimes n}|\psi_2\rangle \;=\; \sum_{z}\underbrace{\left[\frac{1}{2^{\,n}}\sum_{x}(-1)^{f(x)+x\cdot z}\right]}_{\displaystyle a_z}\,|z\rangle . \]

Substitute Step 5 into Step 4 and exchange the finite sums over \(x\) and \(z\). The bracket \(a_z\) is the amplitude of basis string \(z\) and is a Walsh–Hadamard transform of \((-1)^{f(x)}\). B

\[ a_{0^n} \;=\; \frac{1}{2^{\,n}}\sum_{x}(-1)^{f(x)} , \qquad P(0^n) \;=\; |a_{0^n}|^2 \;=\; \left|\frac{1}{2^{\,n}}\sum_{x}(-1)^{f(x)}\right|^2 . \]

Set \(z=0^n\), for which \(x\cdot z=0\) for every \(x\), then apply the Born rule. This is the interference term: all \(2^n\) paths arrive at \(0^n\) with equal weight and sign \((-1)^{f(x)}\). B

\[ f\ \text{constant}\;\Rightarrow\; a_{0^n}=\pm1,\;P(0^n)=1; \qquad f\ \text{balanced}\;\Rightarrow\; a_{0^n}=0,\;P(0^n)=0 . \]

If \(f\) is constant every sign is identical, so the \(2^n\) unit terms add to \(\pm2^n\) and \(|a_{0^n}|=1\); by normalization all other \(a_z=0\). If \(f\) is balanced there are equally many \(+1\) and \(-1\) terms, which cancel exactly. A

Result

\[ \boxed{\,P(\text{measure }0^n)\;=\;\left|\frac{1}{2^{\,n}}\sum_{x\in\{0,1\}^n}(-1)^{f(x)}\right|^2 \;=\;\begin{cases}1,& f\ \text{constant}\\[2pt]0,& f\ \text{balanced}\end{cases}}\, \]

Reading. After exactly one oracle call, measure the \(n\) query qubits. Observing the all-zeros string certifies "constant"; observing any nonzero string certifies "balanced". The answer is exact — there is no error probability — because the balanced case makes the \(0^n\) amplitude vanish identically by cancellation, not merely make it small. A deterministic classical prover needs \(2^{n-1}+1\) evaluations in the worst case (having seen \(2^{n-1}\) equal outputs, one more equal output forces "constant"; a single disagreement forces "balanced").

Units check. Every quantity is a pure number. Amplitudes \(a_z\) are dimensionless; the state is normalized, \(\sum_z|a_z|^2=1\) (constant: one term equal to \(1\); balanced: the missing \(0^n\) weight is redistributed over nonzero \(z\)). The probability \(P(0^n)\in[0,1]\) is dimensionless, and the query count \(2^{n-1}+1\) is a dimensionless integer.

Limiting cases

\(n=1\): reduces to Deutsch's original problem. One query decides \(f(0)\!=\!f(1)\) versus \(f(0)\!\neq\!f(1)\), versus two classical queries — a \(2\!\to\!1\) saving.
Constant \(f\equiv0\): no phase is stamped, the second Hadamard wall simply inverts the first, and the register returns to \(0^n\) — the "do nothing, measure zero" limit.
Linear \(f(x)=a\cdot x\) (a balanced function unless \(a=0\)): the measured string is \(z=a\) with certainty — this is the Bernstein–Vazirani limit, which recovers the whole hidden vector, not just one bit.
Large \(n\): quantum cost stays at one query while the classical worst case \(2^{n-1}+1\) grows exponentially — the separation widens without bound.

Breaks when

The promise is violated. For a generic \(f\) that is neither constant nor balanced, \(a_{0^n}\) lies strictly between \(0\) and \(1\) in magnitude; a single measurement no longer decides anything with certainty, and the algorithm reports only whether the "bias" \(\tfrac{1}{2^n}\sum_x(-1)^{f(x)}\) happened to be extreme.
Randomized classical algorithms are allowed. The exponential separation is against deterministic exact classical querying only. A classical algorithm that samples \(k\) random inputs errs with probability at most \(2^{-(k-1)}\) on the balanced case, so \(O(1)\) queries already give tiny bounded error — the true separation is exact-vs-exact, and it collapses to constant-factor if bounded error is permitted on both sides.
Decoherence or gate infidelity is present. Dephasing on the query register or an imperfect \(U_f\) makes the balanced-case cancellation incomplete, so \(P(0^n)>0\) even for balanced \(f\) and the answer is no longer certain; repetition and majority voting are then required, eroding the single-query claim.
The oracle is not given as a coherent unitary. If \(f\) is only a classical subroutine (measure input, compute, return bit), there is no superposition to query and the method offers nothing over classical evaluation.

Failure modes

Ancilla in the wrong state. Initializing the ancilla to \(|0\rangle\) instead of \(|1\rangle\) gives \(|+\rangle\), an eigenstate with eigenvalue \(+1\) regardless of \(f\); the phase kickback dies and every run measures \(0^n\).
Forgetting the final Hadamard wall. Without the second \(H^{\otimes n}\) the state is a superposition with phases \((-1)^{f(x)}\) but uniform magnitudes; a computational-basis measurement returns a uniformly random \(x\) that carries no information about constant-vs-balanced.
Claiming an exponential advantage over all classical algorithms. The exponential gap is only against deterministic algorithms; randomized classical solves the promise with \(O(1)\) queries and small error.
Miscounting classical queries as \(2^n\) or \(2^{n-1}\). The correct worst case is \(2^{n-1}+1\): after \(2^{n-1}\) agreeing outputs one is still undecided, and one more query settles it.
Reading a nonzero outcome as "the value of the hidden string" in general. Only for linear \(f(x)=a\cdot x\) does the outcome equal a meaningful vector (Bernstein–Vazirani); for a generic balanced \(f\) the particular nonzero \(z\) obtained is not itself informative beyond "not constant".
Assuming entanglement across query qubits is needed. Throughout the ideal run the query register is an unentangled product of single-qubit states; the resource being exploited is interference, not entanglement.

Discussion

The engine of the algorithm is destructive interference enforced by symmetry. Every one of the \(2^n\) computational paths reaches the \(0^n\) detector with equal amplitude magnitude \(2^{-n}\) and a sign \((-1)^{f(x)}\) that is precisely the global property we care about. A constant \(f\) makes all signs agree, so the paths interfere constructively and pile up entirely on \(0^n\) (the wave picture: \(2^n\) wavelets in phase). A balanced \(f\) supplies equally many opposite signs, and the wavelets cancel at \(0^n\) exactly — the same cancellation that a diffraction grating produces at a dark fringe. The certainty of the result is the certainty of a node in an interference pattern.

The two Hadamard walls are the discrete Fourier transform over the abelian group \((\mathbb{Z}_2)^n\) and its inverse; the characters \((-1)^{x\cdot z}\) are its irreducible representations. Read this way, Deutsch–Jozsa asks whether the "zero-frequency" Fourier coefficient of \((-1)^{f(x)}\) is maximal (constant) or null (balanced). Simon's algorithm replaces the target group structure with a hidden subgroup of \((\mathbb{Z}_2)^n\), and Shor's replaces it with a hidden subgroup of \(\mathbb{Z}\) via the QFT over \(\mathbb{Z}_N\) — Deutsch–Jozsa is the \((\mathbb{Z}_2)^n\) base case of the hidden-subgroup framework.

The sharpest lesson is what the separation is not. Because the promise makes the problem trivial for randomized classical algorithms, Deutsch–Jozsa gives no evidence for quantum advantage in the practically relevant bounded-error setting; that separation had to wait for Simon (exponential, bounded-error, relative to an oracle) and its recursive descendants. What Deutsch–Jozsa does prove, unconditionally, is that exact quantum query complexity can be exponentially below exact classical query complexity — a statement about the deterministic model that no complexity assumption can weaken, since it is a counting fact about interference. It also demonstrates, via the Bernstein–Vazirani special case, that one query can extract \(n\) bits of a linear function, saturating the Holevo-respecting bound because those \(n\) bits are classical structure rather than an arbitrary quantum message.

Common misconceptions. (i) "It shows quantum computers are exponentially faster than classical." Only against deterministic classical query algorithms; randomized classical is efficient. (ii) "The superposition evaluates \(f\) on all inputs and we read them all out." We never learn individual values \(f(x)\); a measurement yields one string, and only the collective phase pattern survives interference. (iii) "Entanglement powers the speedup." The ideal run keeps the query qubits in a product state; interference over a superposition is the resource here.

Worked examples

\[ n=1,\qquad f(x)=x \quad(\text{so } f(0)=0,\ f(1)=1:\ \text{balanced}). \]

Deutsch's problem with the identity oracle; expect a nonzero (here, \(1\)) outcome. Symbols first, then trace the state. A

Hadamard wall on \(|0\rangle|1\rangle\). A

\[ |\psi_2\rangle=\tfrac{1}{\sqrt2}\big((-1)^{0}|0\rangle+(-1)^{1}|1\rangle\big)|-\rangle=\tfrac{1}{\sqrt2}\big(|0\rangle-|1\rangle\big)|-\rangle=|-\rangle|-\rangle. \]

Phase kickback stamps \((-1)^{f(x)}\); the query register is now exactly \(|-\rangle\). A

\[ H|-\rangle=|1\rangle \;\Rightarrow\; P(\text{outcome}=1)=1. \]

Final Hadamard; measure. A

\[ \boxed{\text{Measured } 1 \neq 0 \ \Rightarrow\ f \text{ is balanced},\quad \text{using one query (classical needs 2).}} \]

Reading. A single call decides Deutsch's problem with certainty. Units check. Probability \(1\), dimensionless; state normalized throughout.

\[ n=2,\qquad f(x_1x_2)=x_1\oplus x_2 \quad(f(00)=0,\ f(01)=1,\ f(10)=1,\ f(11)=0:\ \text{balanced}). \]

A balanced 2-bit function; note \(f(x)=x\cdot(11)\) is linear, so expect the hidden string \(z=11\). B

\[ |\psi_2\rangle=\tfrac12\sum_{x}(-1)^{f(x)}|x\rangle=\tfrac12\big(|00\rangle-|01\rangle-|10\rangle+|11\rangle\big)\ (\otimes\,|-\rangle). \]

Apply phase kickback term by term over the four inputs. A

\[ a_z=\frac14\sum_{x}(-1)^{f(x)+x\cdot z}=\frac14\sum_{x}(-1)^{x\cdot(11\oplus z)}=\delta_{z,11}. \]

Character orthogonality on \((\mathbb{Z}_2)^2\): the sum is \(4\) when \(11\oplus z=00\) and \(0\) otherwise. B

\[ |\psi_3\rangle=|11\rangle \;\Rightarrow\; P(11)=1,\quad P(00)=0. \]

Only \(z=11\) survives; measurement is deterministic. A

\[ \boxed{\text{Measured } 11\neq 00 \Rightarrow f \text{ balanced; the outcome } 11 \text{ is exactly the hidden string } a.} \]

Reading. One query both certifies "balanced" and, because \(f\) is linear, reveals \(a=11\) (Bernstein–Vazirani). A deterministic classical solver would need up to \(2^{2-1}+1=3\) queries. Units check. \(\sum_z|a_z|^2=|a_{11}|^2=1\); all probabilities dimensionless.

Problems

(A) For \(n=1\) and the constant function \(f\equiv1\), trace the state through the circuit and give the measurement outcome and its probability.
Solution
Start \(|0\rangle|1\rangle\); after the Hadamard wall \(|+\rangle|-\rangle\). Phase kickback: \(f(0)=f(1)=1\), so \(\tfrac{1}{\sqrt2}((-1)^1|0\rangle+(-1)^1|1\rangle)|-\rangle=-|+\rangle|-\rangle\). Final Hadamard: \(H|+\rangle=|0\rangle\), giving \(-|0\rangle|-\rangle\). Measurement yields \(0\) with probability \(|-1|^2=1\). The global sign \(-1\) is unobservable. Outcome \(0 \Rightarrow\) constant, correct.
(A/B) For \(n=3\), how many evaluations does a deterministic classical algorithm need in the worst case, and how many does the quantum algorithm need?
Solution
Classical worst case \(2^{n-1}+1=2^{2}+1=5\): after \(2^{n-1}=4\) agreeing outputs the function is still undecided (a balanced function can agree on up to \(2^{n-1}\) inputs), so a 5th, agreeing query is required to force "constant"; any earlier disagreement proves "balanced" immediately. Quantum: \(1\) query. Ratio \(5:1\) at \(n=3\), growing as \((2^{n-1}+1):1\).
(B) For \(n=2\) and the constant function \(f\equiv0\), compute all four amplitudes \(a_z\) after the final Hadamard and verify the measurement result.
Solution
With \(f\equiv0\), \(a_z=\tfrac14\sum_x(-1)^{0+x\cdot z}=\tfrac14\sum_x(-1)^{x\cdot z}\). For \(z=00\) all terms are \(+1\): \(a_{00}=\tfrac14\cdot4=1\). For any \(z\neq00\) the character sum vanishes: \(a_{01}=a_{10}=a_{11}=0\). Hence \(|\psi_3\rangle=|00\rangle\), measurement \(00\) with probability \(1 \Rightarrow\) constant. Check \(\sum_z|a_z|^2=1\).
(B/C) Show that for a linear oracle \(f(x)=a\cdot x\) with fixed \(a\in\{0,1\}^n\), the Deutsch–Jozsa circuit outputs \(z=a\) with certainty. What outcome corresponds to \(a=0^n\)?
Solution
Amplitude \(a_z=\tfrac{1}{2^n}\sum_x(-1)^{a\cdot x + x\cdot z}=\tfrac{1}{2^n}\sum_x(-1)^{x\cdot(a\oplus z)}\). By character orthogonality on \((\mathbb{Z}_2)^n\) this equals \(1\) if \(a\oplus z=0^n\) (i.e. \(z=a\)) and \(0\) otherwise. So the measurement returns \(a\) deterministically — the Bernstein–Vazirani result, extracting all \(n\) bits of \(a\) in one query. For \(a=0^n\), \(f\equiv0\) is constant and the outcome is \(0^n\), consistent with the constant verdict. Every nonzero \(a\) gives a balanced \(f\) and a nonzero outcome.
(C) Prove that \(P(0^n)=0\) for every balanced \(f\) at arbitrary \(n\), and show that a single ancilla bit-flip error (ancilla decoheres to a classical mixture of \(|0\rangle,|1\rangle\)) destroys the certainty.
Solution
Balanced means \(|\{x:f(x)=0\}|=|\{x:f(x)=1\}|=2^{n-1}\). Then \(a_{0^n}=\tfrac{1}{2^n}\sum_x(-1)^{f(x)}=\tfrac{1}{2^n}\big(2^{n-1}(+1)+2^{n-1}(-1)\big)=0\), independent of which particular inputs map to which value; hence \(P(0^n)=0\) exactly. Now suppose the ancilla is dephased into an incoherent mixture \(\tfrac12|0\rangle\langle0|+\tfrac12|1\rangle\langle1|\) before the oracle. Then it is no longer in the \(-1\) eigenstate \(|-\rangle\): the branch \(|+\rangle\)-like component receives eigenvalue \(+1\) for all \(x\), stamping no \(f\)-dependent phase, so its contribution flows entirely to \(0^n\). Averaging over the mixture gives \(P(0^n)=\tfrac12\cdot0+\tfrac12\cdot1=\tfrac12>0\) even for balanced \(f\). The "balanced never yields \(0^n\)" guarantee is gone, and the promise can no longer be decided from a single shot — one must repeat and threshold, forfeiting the exact single-query separation.