Interference as Computation

Suppose someone hands you a function $f:\{0,1{\}}^n\to \{0,1\}$ as a sealed box: you may feed it inputs and read outputs, but you cannot look at its wiring. How many times must you use the box to learn some property of $f$? That count — the number of queries — is the cost we track in this chapter, and it is a genuinely different accounting from counting gates or seconds. It isolates one question: how much can be learned per evaluation of the unknown function?

A quantum computer cannot use a classical box; every operation between preparation and measurement must be unitary and reversible (Chapter 2). So the oracle is given to us as a reversible unitary on $n+1$ qubits — an $n$-bit input register and a one-qubit target (or ancilla) — that writes the answer by XOR:

XOR-ing rather than overwriting is what keeps $U_f$ invertible: apply it twice and the target returns to $y$, so $U_f^2=I$ and $U_f$ is its own inverse — manifestly unitary, a permutation of the computational basis. Feed the input register a superposition and, by linearity, one use of the box touches every value of $f$ at once:

This looks like magic and is not: the result is entangled, and reading it gives just one random $(x,f(x))$ pair, no better than one classical query (the Holevo ceiling of Chapter 1 is still in force). The superposition alone buys nothing. What we need is a way to make the $2^n$ branches interfere before we look — and for that we need the branches to carry signs, not just labels. That is the next section.

Here is the pivot the whole chapter turns on. Prepare the target not in $|0⟩$ but in $|-⟩=(|0⟩-|1⟩)/\sqrt{2}$, the state that $X$ flips by a sign: $X|-⟩=-|-⟩$. Since $U_f$ applies $X$ to the target exactly when $f(x)=1$, watch what happens on a basis input $|x⟩$:

The target comes out unchanged — still $|-⟩$ — but its eigenvalue $(-1{)}^{f(x)}$ has been kicked back onto the input register as a phase. The oracle, which physically writes bits, now acts on the inputs as the pure phase oracle

with the target left as an untouched spectator. This is not an approximation or a convention — it is an exact operator identity, and it is the first referee in the lab, checked to be exactly zero — the referee's tolerance is 0.0, not merely small — against an independent implementation of $D_f$. Both sides of it are drawn in Figure 6.1.

Now the branches carry signs. Run $D_f$ on the uniform superposition and the amplitudes are $\pm 1/\sqrt{2^n}$; a final Hadamard layer turns those signs into constructive and destructive interference. Toggle a function below and watch the signs appear and then interfere to a verdict:

Notice the pattern the explorer makes plain. The amplitude that lands back on $|0\cdots 0⟩$ is the average of the signs, $a_0=\frac{1}{2^n}{\sum }_x(-1{)}^{f(x)}$: it is $\pm 1$ when the signs all agree (a constant $f$) and exactly $0$ when they split evenly (a balanced $f$), because the plus and minus halves cancel term for term. That cancellation is the computation.

The observation of §6.2 is an algorithm. You are promised that $f$ is either constant (the same value on all $2^n$ inputs) or balanced (value 0 on exactly half the inputs, 1 on the other half). Which is it? The Deutsch–Jozsa circuit — in the deterministic one-query form built here, which is the 1998 refinement by Cleve, Ekert, Macchiavello and Mosca rather than either original — answers in a single query: put the ancilla in $|-⟩$, Hadamard every input qubit into the uniform superposition, query $U_f$ once, Hadamard the inputs again, and measure them.

The measured amplitude of outcome $y$ works out to

the Hadamard transform of the sign pattern. For $y=0$ this is the average of §6.2: a constant $f$ gives $a_0=\pm 1$, so $|0\cdots 0⟩$ occurs with probability exactly 1; a balanced $f$ gives $a_0=0$, so that outcome is impossible. One query, one bit of measurement, a certain answer. The lab confirms both determinisms over hundreds of random oracles across a range of register sizes (the panel in §6.6 reports the sweep it ran): the constant case lands on all-zeros with probability 1 to within its referee's tolerance of $5\times 10^{-15}$, and the balanced case lands there with probability below $10^{-33}$ — the residue of a cancellation between amplitudes of equal magnitude, and so quadratically smaller.

David Deutsch found the $n=1$ case in 1985: a single-bit $f$ is constant ($f(0)=f(1)$) or balanced ($f(0)\ne f(1)$), and he showed that a single quantum query can settle it where a classical machine plainly needs both evaluations — but only half the time. Deutsch's 1985 algorithm succeeds with probability $\frac{1}{2}$ and otherwise reports failure rather than a wrong answer, so you know to run it again: one query when it works, two on average. Deutsch and Jozsa generalized the problem to $n$ bits in 1992 and made the answer certain, at the price of two queries; the deterministic single-query circuit of Figure 6.2 — the one we build and referee here — is the 1998 refinement by Cleve, Ekert, Macchiavello and Mosca. The gap it exposes is dramatic: a deterministic classical algorithm must, in the worst case, check $2^{n-1}+1$ inputs before it can be sure — one more than half, since half-plus-one identical answers is the first count a balanced function cannot fake. The quantum machine needs one.

The very same circuit, pointed at a different promise, does something that feels even more like getting information for free. Suppose $f$ is the dot product with a hidden string $s\in \{0,1{\}}^n$,

Classically, each query reveals one bit about $s$: query the unit strings $e_i$ and read off $s_i=f(e_i)$ one at a time — $n$ queries for $n$ bits, and you cannot do better. Run Deutsch–Jozsa instead. After the kickback the input register is

because $(-1{)}^{s\cdot x}$ is precisely the sign pattern the Hadamard transform puts on $|s⟩$. A second Hadamard layer is $H^{\otimes n}$ again, and $(H^{\otimes n}{)}^2=I$, so the register collapses to exactly $|s⟩$: measuring hands you the whole hidden string, all $n$ bits, from a single query. The lab runs this over hundreds of random hidden strings $s$, at every register size up to the largest the panel in §6.6 reports, and recovers $s$ exactly — probability 1, every trial, no exceptions.

It is worth pausing on why this is not a paradox. The single query still obeys Holevo — you measure once and get $n$ bits out of an $n$-qubit register, which is allowed. What was beaten is the classical query count, and only because the quantum query, via kickback, extracts a global parity of $f$ rather than a single value. The oracle was always willing to tell you $s$ in one shot; the classical interface just could not ask the right question.

Time for the honest ledger, because the folklore here is bad. Three caveats turn “exponential speedup” into something precise and much narrower.

It is query complexity, not time. We counted calls to the black box. That is a real and provable resource — the Deutsch–Jozsa gap of $1$ versus $2^{n-1}+1$ is a theorem, not a conjecture — but it says nothing directly about wall-clock time on ordinary inputs, where the function is a circuit you can inspect, not a sealed box.

They are promise problems. Deutsch–Jozsa only works because you are promised $f$ is constant or balanced; feed it a function that is neither and the verdict is meaningless (the explorer in §6.2 shows this directly). Real inputs rarely come with such promises.

The deterministic gap partly evaporates under randomness. A classical algorithm allowed to guess can solve Deutsch–Jozsa with a handful of random queries and tiny error probability: sample a few inputs, and a balanced function almost certainly shows both values. The clean $2^{n-1}+1$ is a deterministic, exact worst case. Bernstein–Vazirani is sturdier — it beats randomized classical query complexity too — but even there the separation is polynomial ($n$ versus $1$), not exponential.

So what is genuinely bought? A mechanism. These algorithms are the first proof that arranging amplitudes to interfere lets a single measurement report a global property of a function that no single evaluation reveals. That is not yet a proof that $\mathsf{BQP}⊋\mathsf{P}$ — nobody has one — but it is the exact device that, aimed at periodicity instead of parity, becomes Shor's factoring algorithm in Chapter 7, where the speedup is over the best known classical time, on a problem the world's cryptography depends on. Toys first, then the real thing.

The lab builds a fresh state-vector simulator (the Chapter 2 engine in miniature) and adds the one new object of this chapter: the oracle. The honest XOR oracle is a permutation of amplitudes; the phase oracle it becomes under kickback is a sign flip. Two independent implementations — which the first referee then forces to agree:

1impl State {
2    // …
3
4    /// The honest XOR oracle U_f: |x>|y> -> |x>|y XOR f(x)>, input in bits
5    /// 0..n_in, ancilla in bit n_in. Implemented as the permutation it is —
6    /// swap the ancilla-0 and ancilla-1 amplitudes of every x with f(x)=1. This
7    /// is a genuine unitary; no phases are put in by hand.
8    fn apply_xor_oracle(&mut self, f: &[u8], n_in: usize) {
9        let anc = 1usize << n_in;
10        for x in 0..(1usize << n_in) {
11            if f[x] == 1 {
12                self.amps.swap(x, x | anc);
13            }
14        }
15    }
16
17    /// The phase oracle D = diag((-1)^{f(x)}) on n_in qubits — the object phase
18    /// kickback is supposed to produce. An INDEPENDENT code path (no ancilla, no
19    /// XOR, just a sign flip) used only to referee the kickback identity.
20    fn apply_phase_oracle(&mut self, f: &[u8]) {
21        for x in 0..self.dim() {
22            if f[x] == 1 {
23                self.amps[x] = -self.amps[x];
24            }
25        }
26    }
27}

The phase-kickback referee builds $|\psi ⟩|-⟩$ for random $|\psi ⟩$, applies the honest $U_f$ one way and the phase oracle $D_f$ the other, and demands they match — the identity (6.3) verified, not assumed:

1fn main() -> Result<(), Box<dyn Error>> {
2    // …
3
4    // --- Referee 1: phase kickback identity -------------------------------
5    // For random input states |psi> and random oracles f, the honest XOR oracle
6    // acting on |psi>|-> equals the phase oracle diag((-1)^{f(x)}) acting on
7    // |psi>, tensored with an untouched |->. Two independent code paths.
8    let inv_sqrt2 = 1.0 / 2.0_f64.sqrt();
9    let mut worst_kick: f64 = 0.0;
10    for _ in 0..400 {
11        let n_in = rng.gen_range(1..=6);
12        let dim = 1usize << n_in;
13        // random input amplitudes (normalization is irrelevant to a linear id.)
14        let psi: Vec<C> = (0..dim)
15            .map(|_| c(rng.gen::<f64>() * 2.0 - 1.0, rng.gen::<f64>() * 2.0 - 1.0))
16            .collect();
17        let f: Vec<u8> = (0..dim).map(|_| rng.gen_range(0..2u8)).collect();
18
19        // Path A: build |psi>|-> explicitly, apply the honest permutation U_f.
20        let anc = 1usize << n_in;
21        let mut full = State { n: n_in + 1, amps: vec![c(0.0, 0.0); dim * 2] };
22        for x in 0..dim {
23            full.amps[x] = psi[x] * inv_sqrt2; // ancilla |0> branch
24            full.amps[x | anc] = -psi[x] * inv_sqrt2; // ancilla |1> branch of |->
25        }
26        full.apply_xor_oracle(&f, n_in);
27
28        // Path B: apply the phase oracle to |psi> directly, tensor with |->.
29        let mut inp = State { n: n_in, amps: psi.clone() };
30        inp.apply_phase_oracle(&f);
31        let mut expect = vec![c(0.0, 0.0); dim * 2];
32        for x in 0..dim {
33            expect[x] = inp.amps[x] * inv_sqrt2;
34            expect[x | anc] = -inp.amps[x] * inv_sqrt2;
35        }
36
37        for i in 0..dim * 2 {
38            worst_kick = worst_kick.max((full.amps[i] - expect[i]).norm());
39        }
40    }
41    assert!(worst_kick.is_finite()); // FINITE before small
42    // …
43}

Deutsch–Jozsa is then just the circuit of Figure 6.2, read off as the all-zeros probability. Bernstein–Vazirani reuses it verbatim, only reading the recovered string instead of a yes/no:

1/// The Deutsch–Jozsa circuit on n_in input qubits + 1 ancilla. Returns the
2/// probability that measuring the whole input register yields |0...0>.
3///   ancilla: X then H  (-> |->)      inputs: H on each  (-> uniform)
4///   one query U_f                    inputs: H on each   measure inputs
5fn dj_all_zero_prob(f: &[u8], n_in: usize) -> f64 {
6    let n_total = n_in + 1;
7    let mut s = State::basis(n_total, 0);
8    s.apply_1q(&g_x(), n_in); // ancilla |0> -> |1>
9    s.apply_1q(&g_h(), n_in); // -> |->
10    for q in 0..n_in {
11        s.apply_1q(&g_h(), q);
12    }
13    s.apply_xor_oracle(f, n_in);
14    for q in 0..n_in {
15        s.apply_1q(&g_h(), q);
16    }
17    // Input register = all zeros means the input bits are 0; the ancilla can be
18    // either value, so sum the two amplitudes at index 0 and index (ancilla=1).
19    let anc = 1usize << n_in;
20    s.amps[0].norm_sqr() + s.amps[anc].norm_sqr()
21}

The referees — four independent physics checks, with Deutsch–Jozsa and Bernstein–Vazirani each refereeing two quantities — run and write their results to JSON, which the panel below reads live, names, values and tolerances alike; nothing here is hardcoded. Phase kickback holds exactly (tolerance 0.0, because the two code paths do no arithmetic that could round differently); Deutsch–Jozsa is deterministic to $5\times 10^{-15}$ (constant) and $10^{-33}$ (balanced); Bernstein–Vazirani recovers $s$ exactly in every trial; and the classical bound $2^{n-1}+1$ is proven by brute force at the small sizes the panel names. The proof enumerates all $\left(\genfrac{}{}{0ex}{}{2^n}{2^{n-1}}\right)$ balanced truth tables once, then for every one of the $\left(\genfrac{}{}{0ex}{}{2^n}{2^{n-1}}\right)$ possible query sets of size $2^{n-1}$ it searches that list for a balanced function consistent with all-zero answers on the set. One always exists, so a constant and a balanced verdict both survive and no deterministic strategy, however clever or adaptive, can decide in $2^{n-1}$ queries. The other direction is read off the same enumeration: no balanced function can hide past query $2^{n-1}+1$, and the worst one hides for exactly $2^{n-1}$ — so the bound is tight, not merely respected. Every function in the enumeration is then decided by the simulator in a single query. For larger $n$ the formula is quoted, not proven:

Run it yourself with cargo run --release in Rust-QML/ch06-oracles. The simulator ends with ALL REFEREES PASSED. Keep the phase-kickback trick in view: Chapter 7 points the same interference at the structure of periodic functions, and that is where the toys turn into Shor.