Skip to content

Lesson 11: Quantum Oracles and the Phase Kick-Back Algorithm

11.1 Learning Outcomes

By the end of this hour a student will be able to:

  1. Distinguish the bit oracle \(U_f\) from the phase oracle \(O_f\) and convert between them.
  2. Derive the phase kick-back identity and explain its mechanism.
  3. Explain the role of the ancilla prepared in \(|-\rangle\).
  4. State the query complexity model and why it is the right framework for proving speed-ups.
  5. Recognise phase kick-back as the shared engine of Deutsch–Jozsa, Bernstein–Vazirani, Simon, Grover and phase estimation.

11.2 The Query (Oracle) Model

Definition (Oracle). An oracle is a black-box unitary implementing an unknown function \(f\). The algorithm may apply the oracle but may not inspect its internals.

Definition (Query complexity). The query complexity of a problem is the minimum number of oracle calls needed to solve it, ignoring all other gate costs.

Why this model? Query complexity is the setting in which provable, unconditional separations between classical and quantum computing exist. Statements like "Deutsch–Jozsa needs 1 quantum query versus \(2^{n-1}+1\) classical queries" are theorems, not conjectures. By contrast, Shor's advantage over classical factoring is only a conjectured separation, since no super-polynomial classical lower bound for factoring is known.

11.3 Two Kinds of Oracle

The bit oracle (XOR / standard oracle)

\[ U_f\,|x\rangle|y\rangle = |x\rangle\,|y\oplus f(x)\rangle \]

Introduced in L09. It writes the answer into an ancilla register by XOR, is self-inverse, and is built from Toffoli/CNOT gates. With \(y = 0\) it gives \(|x\rangle|f(x)\rangle\).

The phase oracle

\[ O_f\,|x\rangle = (-1)^{f(x)}\,|x\rangle \]

The oracle marks solutions with a minus sign and leaves the basis labels untouched. There is no ancilla in the final state, which is exactly what interference needs.

Why the phase oracle is the useful one. After \(O_f\), the register is \(\frac{1}{\sqrt{2^n}}\sum_x (-1)^{f(x)}|x\rangle\) — a superposition whose phases encode the entire truth table of \(f\). Applying \(H^{\otimes n}\) converts those phases into amplitudes that interfere. By contrast, the bit oracle leaves the answer entangled with an ancilla, and that entanglement destroys interference (see §5).

11.4 Phase Kick-Back

Theorem (Phase kick-back). Let \(f:\{0,1\}^n \to \{0,1\}\) and let the ancilla be prepared in

\[ |-\rangle = \frac{1}{\sqrt2}\big(|0\rangle - |1\rangle\big) . \]

Then

\[ \boxed{\ U_f\,\big(|x\rangle \otimes |-\rangle\big) = (-1)^{f(x)}\,|x\rangle\otimes|-\rangle\ } \]

Proof. Expand the ancilla and apply the definition of \(U_f\):

\[ U_f|x\rangle\frac{|0\rangle - |1\rangle}{\sqrt2} = \frac{1}{\sqrt2}\Big(|x\rangle|0\oplus f(x)\rangle - |x\rangle|1\oplus f(x)\rangle\Big) \]
\[ = \frac{1}{\sqrt2}|x\rangle\Big(|f(x)\rangle - |\overline{f(x)}\rangle\Big) \]

Now split into two cases.

Case \(f(x) = 0\):

\[ \frac{1}{\sqrt2}\big(|0\rangle - |1\rangle\big) = |-\rangle = (+1)|-\rangle \]

Case \(f(x) = 1\):

\[ \frac{1}{\sqrt2}\big(|1\rangle - |0\rangle\big) = -\frac{1}{\sqrt2}\big(|0\rangle-|1\rangle\big) = (-1)|-\rangle \]

Both cases are summarised by the factor \((-1)^{f(x)}\). \(\blacksquare\)

Reading the result

Three observations, each essential:

  1. The ancilla is unchanged. It exits in \(|-\rangle\), exactly as it entered. It is a catalyst: used but not consumed, and never measured.
  2. The phase appears on the input register, even though \(U_f\) nominally writes to the ancilla. The phase has been "kicked back" from target to control — hence the name.
  3. By linearity it applies to superpositions:
\[ U_f\left(\frac{1}{\sqrt{2^n}}\sum_x |x\rangle\right)|-\rangle = \left(\frac{1}{\sqrt{2^n}}\sum_x (-1)^{f(x)}|x\rangle\right)|-\rangle . \]

Conclusion. One call to the bit oracle \(U_f\), with the ancilla in \(|-\rangle\), implements the phase oracle \(O_f\) on the whole superposition. This converts the entire truth table of \(f\) into a pattern of \(\pm\) signs in a single query.

Why |-⟩?

\(|-\rangle\) is the \(-1\) eigenvector of \(X\): \(X|-\rangle = -|-\rangle\). The oracle applies \(X^{f(x)}\) to the ancilla conditioned on \(x\), and applying \(X\) to its own eigenvector returns the eigenvalue as a phase.

General principle (this is the whole idea behind phase estimation, L19). If \(U|u\rangle = e^{i\theta}|u\rangle\) and we apply a controlled-\(U\) with the target in \(|u\rangle\):

\[ \mathrm{c}\text{-}U\,\big(|c\rangle|u\rangle\big) = e^{i\theta c}|c\rangle|u\rangle . \]

The eigenvalue phase is transferred to the control. Phase kick-back is the special case \(U = X\), \(\theta = \pi\).

The universal algorithm template

Every algorithm in Unit II has this shape:

Step 1  Prepare  |0>^n  |1>
Step 2  Apply    H^(x)n on the input register,  H on the ancilla   -> ancilla is |->
Step 3  Query    U_f once (or a few times)  -> phases (-1)^{f(x)} appear
Step 4  Interfere: apply H^(x)n (or QFT, or Grover diffusion)
Step 5  Measure the input register

Steps 3–4 are the heart: write phases, then convert phases into amplitudes.

11.5 The Minimal Phase Kick-Back Circuit

For \(n = 1\) the oracle for \(f(x) = x\) is simply a CNOT (control = input, target = ancilla). The ancilla is prepared in \(|-\rangle\) by applying \(X\) then \(H\) to \(|0\rangle\):

q0 (input)   : --[H]--------*---[H]---[M]--
                            |
q1 (ancilla) : --[X]--[H]--[X]-------------
                 \____ ____/
                      v
                prepares |->

Trace.

\[ |0\rangle|0\rangle \xrightarrow{X \text{ on } q_1} |0\rangle|1\rangle \xrightarrow{H\otimes H} |+\rangle|-\rangle \]
\[ \xrightarrow{\mathrm{CNOT}} \frac{1}{\sqrt2}\big((-1)^{0}|0\rangle + (-1)^{1}|1\rangle\big)|-\rangle = |-\rangle|-\rangle \]
\[ \xrightarrow{H \text{ on } q_0} |1\rangle|-\rangle \]

Measuring \(q_0\) gives 1 with certainty. The oracle "wrote" \(f(0)\oplus f(1) = 1\) into \(q_0\) using one query. This tiny circuit is already the Deutsch algorithm (L12).

11.6 Why the Ancilla Must Be |-⟩ (the Entanglement Trap)

Suppose a student prepares the ancilla in \(|0\rangle\) instead. Then

\[ U_f\left(\frac{1}{\sqrt{2^n}}\sum_x|x\rangle\right)|0\rangle = \frac{1}{\sqrt{2^n}}\sum_x |x\rangle|f(x)\rangle . \]

The input register is now entangled with the ancilla. Its reduced state is the mixture

\[ \rho_{\text{in}} = \frac{1}{2^n}\sum_x |x\rangle\langle x| = \frac{I}{2^n}, \]

which is maximally mixed — all coherence is gone. Applying \(H^{\otimes n}\) to a maximally mixed state does nothing useful, and the subsequent measurement is uniformly random.

The general rule. Any record of \(x\) left anywhere — in an ancilla, in a "garbage" register, in the environment — destroys the interference. This is why oracle implementations must uncompute their scratch qubits, and it is the same phenomenon as decoherence.

Preparing the ancilla in \(|-\rangle\) avoids this entirely: it factorises out of the state, so the input register stays pure and coherent.

11.7 Solved Problems

Problem 1 — Verifying kick-back for a constant function

Let \(f(x) = 1\) for all \(x \in \{0,1\}^2\). Compute \(U_f\left(\frac12\sum_x|x\rangle\right)|-\rangle\) and then apply \(H^{\otimes2}\) to the input register. What is measured?

Solution. By phase kick-back with \(f(x)=1\) for every \(x\):

\[ U_f\left(\frac12\sum_x|x\rangle\right)|-\rangle = \left(\frac12\sum_x (-1)^1|x\rangle\right)|-\rangle = -\left(\frac12\sum_x|x\rangle\right)|-\rangle \]

The result is \(-|{+}{+}\rangle|-\rangle\) — the state is unchanged up to a global phase. A constant function contributes the same phase to every branch, and a uniform phase is unobservable.

Apply \(H^{\otimes2}\):

\[ H^{\otimes 2}\left(-|{+}{+}\rangle\right) = -|00\rangle . \]

Measuring gives \(\mathbf{00}\) with probability 1.

Insight. A constant \(f\) returns the register to \(|00\rangle\). This will be exactly the decision rule of Deutsch–Jozsa: all zeros ⟹ constant.

Problem 2 — Kick-back for a balanced function

Now let \(f(x_1x_2) = x_1\) (balanced: half the inputs give 0, half give 1). Repeat Problem 1.

Solution.

\[ \frac12\sum_x (-1)^{f(x)}|x\rangle = \frac12\Big[(-1)^0|00\rangle + (-1)^0|01\rangle + (-1)^1|10\rangle + (-1)^1|11\rangle\Big] \]
\[ = \frac12\big(|00\rangle + |01\rangle - |10\rangle - |11\rangle\big) \]

Factorise:

\[ = \frac{1}{\sqrt2}\big(|0\rangle - |1\rangle\big)\otimes\frac{1}{\sqrt2}\big(|0\rangle+|1\rangle\big) = |-\rangle\otimes|+\rangle \]

Apply \(H^{\otimes2}\): \(H|-\rangle = |1\rangle\) and \(H|+\rangle = |0\rangle\), so the state becomes

\[ |10\rangle . \]

Measuring gives \(\mathbf{10}\) with probability 1 — not \(00\).

Insight. Balanced \(f\) never returns \(00\). Comparing Problems 1 and 2 gives the complete Deutsch–Jozsa decision rule after one query, versus \(2^{n-1}+1 = 3\) classical queries for \(n=2\).

Problem 3 — Converting a bit oracle into a phase oracle by circuit

Show explicitly that the circuit "\(X\), \(H\) on the ancilla; \(U_f\); \(H\), \(X\) on the ancilla" implements the phase oracle \(O_f\) exactly, restoring the ancilla to \(|0\rangle\).

Solution. Start with \(|x\rangle|0\rangle\).

Step 1 — ancilla preparation. \(X\) then \(H\):

\[ |0\rangle \xrightarrow{X} |1\rangle \xrightarrow{H} |-\rangle \]

State: \(|x\rangle|-\rangle\).

Step 2 — oracle. Phase kick-back:

\[ U_f|x\rangle|-\rangle = (-1)^{f(x)}|x\rangle|-\rangle \]

Step 3 — ancilla restoration. \(H\) then \(X\):

\[ |-\rangle \xrightarrow{H} |1\rangle \xrightarrow{X} |0\rangle \]

Final state:

\[ (-1)^{f(x)}|x\rangle\otimes|0\rangle = \big(O_f|x\rangle\big)\otimes|0\rangle \ \checkmark \]

The ancilla is returned to \(|0\rangle\) and completely disentangled, so it can be reused. This "prepare–query–unprepare" sandwich is the standard idiom in Qiskit and Cirq for building a phase oracle from a Boolean circuit.

Problem 4 — Generalised kick-back with a controlled-U

Let \(U|u\rangle = e^{2\pi i\theta}|u\rangle\). Compute the output of the circuit: \(H\) on the control, controlled-\(U\), \(H\) on the control, with the target held in \(|u\rangle\). Find \(\Pr[0]\).

Solution.

\[ |0\rangle|u\rangle \xrightarrow{H} \frac{1}{\sqrt2}\big(|0\rangle + |1\rangle\big)|u\rangle \]

Apply controlled-\(U\) (acts only on the \(|1\rangle\) branch):

\[ \to \frac{1}{\sqrt2}\big(|0\rangle + e^{2\pi i\theta}|1\rangle\big)|u\rangle \]

The eigenvalue phase has moved onto the control; the target is untouched. Apply \(H\):

\[ \to \frac{1}{2}\Big[(1 + e^{2\pi i\theta})|0\rangle + (1 - e^{2\pi i\theta})|1\rangle\Big]|u\rangle \]
\[ \Pr[0] = \left|\frac{1+e^{2\pi i\theta}}{2}\right|^2 = \cos^2(\pi\theta), \qquad \Pr[1] = \sin^2(\pi\theta) \]

Check. At \(\theta = 1/2\) (i.e. \(U = X\), \(|u\rangle = |-\rangle\), eigenvalue \(-1\)): \(\Pr[0] = \cos^2(\pi/2) = 0\), so the measurement gives 1 with certainty — reproducing the minimal circuit of §4 ✓.

This is the Hadamard test, and it is precisely the building block of quantum phase estimation (L19), which in turn drives Shor's algorithm and HHL.

Problem 5 — What goes wrong with the wrong ancilla

Repeat Problem 2 (\(f(x_1x_2) = x_1\)) but with the ancilla prepared in \(|0\rangle\). Compute the reduced state of the input register and the measurement statistics after \(H^{\otimes2}\).

Solution.

\[ U_f\left(\frac12\sum_x|x\rangle\right)|0\rangle = \frac12\Big[|00\rangle|0\rangle + |01\rangle|0\rangle + |10\rangle|1\rangle + |11\rangle|1\rangle\Big] \]

The input register is entangled with the ancilla. Trace out the ancilla:

\[ \rho_{\text{in}} = \frac14\Big[\big(|00\rangle+|01\rangle\big)\big(\langle00|+\langle01|\big) + \big(|10\rangle+|11\rangle\big)\big(\langle10|+\langle11|\big)\Big] \]

This is a mixture of \(|0\rangle|+\rangle\) and \(|1\rangle|+\rangle\) — the coherence between the \(x_1=0\) and \(x_1=1\) blocks has been destroyed.

Apply \(H^{\otimes2}\) to each branch:

  • \(|0\rangle|+\rangle \to |+\rangle|0\rangle \to\) measuring gives \(00\) or \(10\), each w.p. ½.
  • \(|1\rangle|+\rangle \to |-\rangle|0\rangle \to\) measuring gives \(00\) or \(10\), each w.p. ½.

Result: \(\Pr[00] = \Pr[10] = \frac12\).

Compare with Problem 2, where the answer was \(10\) with certainty. Seeing \(00\) would wrongly indicate "constant". The algorithm is broken.

Diagnosis. The ancilla acted as a which-path detector. Once the environment (here, the ancilla) records which branch was taken, interference is impossible — the same physics as the double-slit experiment losing its fringes when the slit is monitored.

11.8 Practice Problems

  1. Verify phase kick-back explicitly for \(n=1\), \(f(0)=1\), \(f(1)=0\).
  2. Show \(O_f^2 = I\) for any Boolean \(f\).
  3. For \(f(x_1x_2) = x_1\oplus x_2\), compute \(\frac12\sum_x(-1)^{f(x)}|x\rangle\) and apply \(H^{\otimes2}\). [Ans: \(|11\rangle\)]
  4. In Problem 4, what value of \(\theta\) makes \(\Pr[0] = \Pr[1] = \frac12\)? [Ans: \(\theta = 1/4\) or \(3/4\)]
  5. Explain why the ancilla in phase kick-back is never measured.
  6. If a circuit leaves a garbage qubit entangled with \(x\), describe two ways to fix it.
  7. Give the query complexity of determining \(f(0)\oplus f(1)\) classically and quantumly. [Ans: 2 and 1]

11.9 Summary

  • The query model measures oracle calls; it is where provable quantum–classical separations live.
  • Bit oracle: \(U_f|x\rangle|y\rangle = |x\rangle|y\oplus f(x)\rangle\). Phase oracle: \(O_f|x\rangle = (-1)^{f(x)}|x\rangle\).
  • Phase kick-back: \(U_f|x\rangle|-\rangle = (-1)^{f(x)}|x\rangle|-\rangle\) — one bit-oracle query implements the phase oracle on an entire superposition, leaving the ancilla untouched.
  • The generalised version transfers an eigenvalue \(e^{i\theta}\) of \(U\) onto a control qubit; this is the Hadamard test and the seed of phase estimation.
  • The ancilla must be \(|-\rangle\): an ancilla in \(|0\rangle\) entangles with the input, destroys coherence, and randomises the output. Uncompute all garbage.
  • Universal template: superpose → kick back phases → interfere → measure.

Next lesson: L12 — The Deutsch algorithm.

Practise now: unit2-algorithms-lab.html → Oracle Explorer: pick any \(f\), choose the ancilla state, and watch the phase pattern and final measurement histogram side by side.