Chapter 19: Quantum Oracles

"Query complexity says the oracle is free. The oracle costs twenty-seven thousand T gates."

Overview

Part IV changes the subject. Parts I–III were about how to run circuits; from here the question is what to run.

Nearly every quantum algorithm with a proven speedup — Deutsch–Jozsa, Bernstein–Vazirani, Simon's, Grover's — is stated in terms of an oracle: a black box implementing some classical function $f(x)$, which you are allowed to query. The algorithm's advantage is measured in how many queries it needs.

This chapter builds oracles, derives the trick that makes them useful, and then prices them.

The trick is phase kickback. A reversible circuit computing $f$ into a scratch qubit becomes, when that scratch qubit is prepared in $|-\rangle$, a circuit that writes $f(x)$ into the phase:

$$U_f\left(|x\rangle \otimes |-\rangle\right) = (-1)^{f(x)}\,|x\rangle \otimes |-\rangle$$

Verified in §19.3 to give an amplitude ratio of exactly $+1$ where $f(x)=0$ and exactly $-1$ where $f(x)=1$. Every algorithm in Part IV depends on this.

And the price is the chapter's honest content. Query complexity treats an oracle as a single unit-cost operation. Decompose a realistic one into Clifford+T and:

    n inputs      CX      T gates    depth
           2       6            7       11
           4      36        2,605    4,788
           8     264       26,978   43,413

An 8-input oracle costs nearly twenty-seven thousand T gates — and Chapter 15 §15.8 measured what a T gate costs under error correction. "One query" is an abstraction that hides essentially the entire computation.

There is also a way out, and it is dramatic:

    n = 8    without ancillas:  26,978 T gates
             with 6 ancillas:        55 T gates       491x fewer

Six extra qubits buy a 491× reduction in T count. §19.6 measures the trade across sizes.

In this chapter, you will learn to:

• Build a boolean oracle from a classical predicate.
• Derive and verify phase kickback.
• Understand why uncomputation is mandatory.
• Measure an oracle's true cost in Clifford+T.
• Trade ancillas against T count.
• Read query complexity honestly.

Learning Paths

How to read this chapter by track. - 🔰 Beginner — §19.2, §19.3, §19.5. Phase kickback is the idea everything else needs. - 🔬 Researcher — §19.6 and §19.7; the gap between query complexity and gate cost is where a lot of over-claiming lives. - 🤖 Quantum ML — §19.5 on uncomputation; ancilla hygiene breaks variational circuits quietly. - 🏗️ Quantum Engineer — §19.6's ancilla trade is the single highest-leverage decision here. - 🔐 Security — all of it; Chapter 21's search and Chapter 23's factoring both rest on this chapter.

19.1 What an Oracle Is

An oracle is a reversible circuit implementing a classical function, treated as a black box.

The complication is that classical functions are usually not reversible — $f(x) = 1$ if $x = 3$ throws away information, and quantum operations must be unitary. The standard fix is to keep the input and record the answer separately:

$$U_f : |x\rangle|y\rangle \;\longrightarrow\; |x\rangle\,|y \oplus f(x)\rangle$$

XOR is its own inverse, so $U_f^2 = I$ and the operation is reversible. This is the boolean oracle (or bit oracle).

Building one from a predicate is mechanical. For $f(x) = 1$ iff $x = m$:

def bit_oracle(n, marked):
    qc = QuantumCircuit(n + 1)
    bits = format(marked, f"0{n}b")[::-1]     # little-endian
    for i, b in enumerate(bits):
        if b == "0":
            qc.x(i)                            # flip zeros to ones
    qc.mcx(list(range(n)), n)                  # fires only when all inputs are 1
    for i, b in enumerate(bits):
        if b == "0":
            qc.x(i)                            # undo
    return qc

The X sandwich is the whole technique. A multi-controlled X fires when every control is 1, so flip the bits that should be 0, apply it, and flip them back. The pattern generalizes to any predicate expressible as a conjunction, and composing conjunctions gives you arbitrary boolean functions.

⚠️ Common Pitfall — the second X layer is not optional.

Omitting it leaves the input register in a different basis state than it started in, so the oracle no longer computes $|x\rangle|y \oplus f(x)\rangle$ — it computes $|x'\rangle|y \oplus f(x)\rangle$ for some permuted $x'$.

In a Deutsch–Jozsa or Grover circuit this does not error. It quietly marks the wrong state, and the algorithm returns a confident wrong answer — Chapter 14 §14.5's failure mode arriving by a different route.

Reversibility Is a Constraint on the Programmer, Not on the Hardware

The definition above looks like bookkeeping — keep the input, XOR the answer, done. It is not bookkeeping. It is a restriction on which implementations of $f$ are available to you, and the restriction bites hardest on exactly the techniques that make classical code fast.

A classical predicate is usually written to avoid work. It returns early when a constraint fails. It short-circuits an && when the left side is false. It indexes a hash table instead of scanning. It overwrites a temporary once the value is no longer needed. Every one of those is an irreversible step, because each one destroys the information needed to run the computation backwards.

Three consequences follow, and they compound.

Every branch is computed. A reversible circuit has no control flow. if (a) { x } else { y } becomes: compute $x$, compute $y$, and use $a$ as a control to select between them — so you pay for both arms, every time, on every input in the superposition. A predicate with $k$ independent early exits does $k$ times more work reversibly than it does classically, and the saving those early exits were designed to produce is exactly what disappears.

Every intermediate value is stored. Classically, a temporary is written, read, and overwritten. Reversibly, overwriting is what you cannot do. A computation with $g$ intermediate results needs $g$ ancilla qubits held live until they are uncomputed — and §19.4 shows what happens if they are not.

Nothing is thrown away until it is un-derived. This is the standard trick, due to Bennett: compute $f$ into ancillas, copy the answer out with a CNOT (copying a classical bit is reversible), then run the entire computation backwards to erase everything else. The circuit is roughly twice as long as the forward computation and produces exactly one bit of output with no garbage.

So a reversible oracle is not a translation of a classical checker. It is a different program with the same input–output behaviour, typically several times larger, and §19.5 prices what "several times larger" means when the currency is T gates. Case Study 1 walks a team through discovering this after committing to a project.

19.2 The Bit Oracle in Action

With the scratch qubit in $|0\rangle$ and the input in uniform superposition:

  state: [0.5, 0.5, 0.5, 0, 0, 0, 0, 0.5]

Reading the nonzero entries: three terms have the scratch qubit at 0, and one term — the marked one — has moved to a basis state with the scratch qubit at 1.

The oracle worked, and it is useless like this. The information is in the scratch register, which means measuring it collapses the superposition and gives you one random $x$ along with $f(x)$ — no better than evaluating $f$ classically on a random input.

The whole difficulty of quantum algorithms is here. Computing $f$ on a superposition is trivial. Extracting anything useful about $f$ requires the answers to interfere, and information sitting in a separate register does not interfere with anything.

What "Useless" Means Precisely

"No better than a classical random query" is worth making exact, because the arithmetic is short and it fixes the intuition.

Start from the uniform superposition over $N = 2^n$ inputs with the scratch in $|0\rangle$, and apply the bit oracle for a single marked state $m$:

$$U_f\,\frac{1}{\sqrt N}\sum_x |x\rangle|0\rangle = \frac{1}{\sqrt N}\!\!\sum_{x \neq m}\!|x\rangle|0\rangle \;+\; \frac{1}{\sqrt N}|m\rangle|1\rangle$$

Now measure the scratch qubit. It reads 1 with probability $1/N$, and when it does the input register collapses to exactly $|m\rangle$ — you have found the answer. It reads 0 with probability $1 - 1/N$, and the input register collapses to a uniform superposition over the $N-1$ states you have just ruled out, which is one bit of information about a set you cannot address.

Success probability $1/N$ per query is precisely the classical random-guessing rate. The quantum circuit evaluated $f$ on all $N$ inputs simultaneously and the measurement gave back exactly one sample, because a measurement returns one outcome. That is the whole cost of putting the answer in a register.

⚛️ The Physics Underneath — §19.2's "useless" state and §19.4's "bug" are the same state.

The circuit above at $n = 2$, $m = 3$, is h(0); h(1); ccx(0,1,2) — because the marked string is 11, the X sandwich is empty and the oracle reduces to a bare Toffoli. That is character for character the circuit §19.4 uses to demonstrate a dirty ancilla, and its input-register entropy is the 0.8113 measured there.

Same state, two readings. In §19.2 the entanglement between input and scratch is the oracle working — that is where $f(x)$ was written. In §19.4 it is a bug — the scratch was supposed to be returned. Nothing in the state distinguishes them. Whether entanglement with an auxiliary register is the result or the defect is a fact about your intent, and no measurement of the circuit can recover it.

This is why phase kickback matters structurally rather than as a convenience: it produces a state with no entanglement to interpret, so the question does not arise.

19.3 Phase Kickback

The fix is to prepare the scratch qubit in $|-\rangle = (|0\rangle - |1\rangle)/\sqrt2$ instead of $|0\rangle$.

$$X|-\rangle = -|-\rangle$$

$|-\rangle$ is an eigenvector of $X$ with eigenvalue $-1$. So when the oracle applies $X$ to the scratch qubit — which it does exactly when $f(x) = 1$ — the state picks up a factor of $-1$, and the scratch qubit is left unchanged:

$$U_f\left(|x\rangle|-\rangle\right) = |x\rangle\,\frac{|0 \oplus f(x)\rangle - |1 \oplus f(x)\rangle}{\sqrt2} = (-1)^{f(x)}|x\rangle|-\rangle$$

Verified, marking $x = 3$ and checking the amplitude ratio for each input:

   x=0 (f=0):  amplitude ratio = +1.000
   x=1 (f=0):  amplitude ratio = +1.000
   x=2 (f=0):  amplitude ratio = +1.000
   x=3 (f=1):  amplitude ratio = -1.000

And on the uniform superposition:

  input-register amplitudes: [+0.354, +0.354, +0.354, -0.354]

The marked term has a minus sign, and nothing else changed. The scratch qubit is unentangled and can be discarded or reused.

📐 Math Aside — deriving kickback from the definition, with no eigenvector shortcut.

The eigenvector argument above is correct and it is also slightly circular-feeling: it asserts that the oracle "applies $X$ when $f(x) = 1$," which is true but is not what the definition says. Here is the derivation from the defining equation alone.

The oracle is defined by $U_f|x\rangle|y\rangle = |x\rangle|y \oplus f(x)\rangle$, and it is linear. Expand $|-\rangle$ and push $U_f$ through:

$$U_f\big(|x\rangle|-\rangle\big) > = \tfrac{1}{\sqrt2}\Big(U_f|x\rangle|0\rangle - U_f|x\rangle|1\rangle\Big) > = |x\rangle \otimes \tfrac{1}{\sqrt2}\Big(|f(x)\rangle - |1 \oplus f(x)\rangle\Big)$$

Now split on the two possible values of $f(x)$, which is legitimate because $f$ is boolean:

$$f(x) = 0:\quad \tfrac{1}{\sqrt2}\big(|0\rangle - |1\rangle\big) = +|-\rangle$$ $$f(x) = 1:\quad \tfrac{1}{\sqrt2}\big(|1\rangle - |0\rangle\big) = -|-\rangle$$

Both cases are $(-1)^{f(x)}|-\rangle$, so $U_f(|x\rangle|-\rangle) = (-1)^{f(x)}|x\rangle|-\rangle$. The scratch register comes out in the state it went in. That is the property that matters: it is not merely unchanged in probability, it is unchanged as a vector, so it factors out of the tensor product completely and carries no entanglement.

And this immediately says why $|+\rangle$ is the wrong choice. Run the same two lines with $|+\rangle = (|0\rangle + |1\rangle)/\sqrt2$:

$$U_f\big(|x\rangle|+\rangle\big) > = |x\rangle \otimes \tfrac{1}{\sqrt2}\Big(|f(x)\rangle + |1 \oplus f(x)\rangle\Big) = |x\rangle|+\rangle$$

for both values of $f(x)$, because addition is commutative where subtraction is not. The eigenvalue is $+1$, and an eigenvalue of $+1$ carries no information. The oracle runs, costs every one of §19.5's T gates, and does nothing at all.

⚠️ Common Pitfall — preparing the scratch with h alone instead of x then h.

This is the single most common way to get an algorithm that runs, terminates, produces a valid probability distribution, and is wrong. qc.h(n) puts the scratch in $|+\rangle$; qc.x(n); qc.h(n) puts it in $|-\rangle$. One missing X is the difference between a $-1$ phase on the marked state and no phase on anything.

The symptom is specific and recognizable once you have seen it: Grover's algorithm returns the uniform distribution regardless of iteration count, and Deutsch–Jozsa returns all zeros for constant and balanced functions. Both look like "the algorithm did nothing," which is exactly what happened — the diffusion operator reflected about a state with no marked component to amplify.

The check is one line on a simulator: apply the oracle to $|x\rangle|-\rangle$ for a marked $x$ and assert the amplitude ratio is $-1$, not $+1$. That is §19.3's verification table, run as a test — which is what phase_signs() in the checkpoint below does.

Kickback Is Phase Estimation With One Bit

The derivation generalizes, and the generalization is the whole of Chapter 22.

Nothing in the argument used the fact that the scratch was a single qubit or that the operation was $X$. Suppose the oracle applies some unitary $V$ to the scratch register conditioned on $f(x) = 1$, and the scratch is prepared in an eigenvector $|u\rangle$ with $V|u\rangle = e^{i\varphi}|u\rangle$. Then by the same two lines:

$$|x\rangle|u\rangle \;\longrightarrow\; e^{i\varphi f(x)}\,|x\rangle|u\rangle$$

The phase $\varphi$ lands on the input register and the eigenvector is untouched. For a bit oracle, $V = X$, $|u\rangle = |-\rangle$, and $\varphi = \pi$ — one bit of phase, either $0$ or $\pi$. Chapter 22 §22.4 runs the same construction with $t$ control qubits and a general $V$, reading $\varphi$ to $t$ bits of precision. Phase kickback is the $t = 1$ case, and Chapter 22's measurement that phase estimation is exact for dyadic phases is the same exactness §19.3's table shows as $\pm 1.000$ rather than $\pm 0.999$.

Preparing the Scratch Costs Two Gates and Zero T

Given §19.5's accounting, it is worth stating what the bit-to-phase conversion adds.

  |->  preparation      x, h        2 gates,  0 T
  |->  restoration      h, x        2 gates,  0 T
  extra qubits                      1

$X$ and $H$ are both Clifford. The conversion that makes an oracle useful adds four Clifford gates and one qubit, and costs nothing in the currency that dominates fault-tolerant computation. Every number in §19.5 and §19.6 is therefore a cost of the bit oracle; the phase oracle is the same number.

That is a small point with a large consequence for reading algorithm papers. When a paper writes $O_f$ and prices it, it is pricing the reversible implementation of $f$. The quantum-mechanical part of the trick — the part that looks magical — is free. The classical part is what costs 27,000 T gates.

🧪 Run It — three experiments on kickback, all on a statevector simulator, all under a minute.

1. Break it on purpose. Take example-01-bit-and-phase-oracles.py and delete the qc2.x(2) line so the scratch is prepared in $|+\rangle$. Print the input-register amplitudes. You should get [+0.354, +0.354, +0.354, +0.354] where §19.3 measured [+0.354, +0.354, +0.354, -0.354] — the oracle ran and changed nothing. Then confirm the amplitude-ratio table reads +1.000 on all four rows, including the marked one. This is the pitfall above, and seeing it once is worth more than reading about it three times.

2. Mark two states instead of one. Compose two bit oracles for different marked strings on the same scratch qubit and check the sign pattern. Predict the answer first: the phases multiply, so marking $m_1$ and $m_2$ gives $-1$ on each of them and $+1$ elsewhere — but marking the same state twice gives $(-1)^2 = +1$ and cancels. An oracle applied twice is the identity, which is the $U_f^2 = I$ from §19.1 showing up as a property of the phases.

3. Check that the scratch really factors out. After the oracle, compute partial_trace(Statevector(qc), [0, 1]) and take its entropy. §19.4's dirty ancilla gives 0.8113; the kickback scratch should give 0.0000 to machine precision. That assertion is scratch_is_clean() in the checkpoint, and it is the only automatic check that distinguishes a bit oracle from a phase oracle.

⚛️ The Physics Underneath — why this is more than a trick.

The scratch qubit has been used as an eigenvector. Applying an operator to its own eigenvector does not change the state; it multiplies by the eigenvalue. So the "computation" leaves no trace in the register that did it — the eigenvalue is kicked back onto the control register instead.

This is the same mechanism as quantum phase estimation (Chapter 22), where a register of control qubits accumulates the eigenvalue phases of a unitary. Phase kickback is phase estimation with one bit of precision, and the family resemblance is exact rather than metaphorical.

And it is why quantum algorithms are about phases. Amplitudes interfere; register contents do not. §19.2's bit oracle put the answer somewhere it could not interfere. Kickback moves it somewhere it can — which is the entire reason the technique exists.

The phase oracle is what algorithms actually use:

$$O_f : |x\rangle \;\longrightarrow\; (-1)^{f(x)}|x\rangle$$

You almost never build it directly. You build the reversible bit oracle — mechanical, from any classical predicate — and prepare the scratch qubit in $|-\rangle$.

19.4 Uncomputation

Oracles need scratch space. A predicate more complex than a single conjunction requires intermediate results, and those live in ancilla qubits.

Ancillas must be returned to $|0\rangle$. This is not tidiness. Measured:

qc = QuantumCircuit(3)
qc.h([0, 1])
qc.ccx(0, 1, 2)          # compute into the ancilla

  entropy of the input register: 0.8113

The input register is now entangled with the ancilla, so on its own it is a mixed state. And a mixed state does not interfere — Chapter 4 §4.7's classical impostor, arriving as a consequence of sloppy bookkeeping rather than noise.

qc.ccx(0, 1, 2)          # UNCOMPUTE

  entropy of the input register: 0.0000

Pure again. The interference the algorithm depends on is restored.

📐 Math Aside — 0.8113 is not an arbitrary number. It is $H_2(1/4)$, exactly.

After h([0,1]); ccx(0,1,2) the state is

$$|\Psi\rangle = \tfrac12\big(|00\rangle + |01\rangle + |10\rangle\big)|0\rangle_a > \;+\; \tfrac12\,|11\rangle|1\rangle_a$$

The two branches carry different ancilla values, so they are orthogonal in the ancilla. Tracing the ancilla out therefore leaves a mixture of exactly two orthonormal input states — the normalized unmarked superposition and the marked state — weighted by their branch norms:

$$\rho_{\text{in}} = \tfrac34\,|a\rangle\langle a| \;+\; \tfrac14\,|b\rangle\langle b|, > \qquad |a\rangle = \tfrac{|00\rangle+|01\rangle+|10\rangle}{\sqrt3},\quad |b\rangle = |11\rangle$$

The eigenvalues are $3/4$ and $1/4$, so the von Neumann entropy is the binary entropy of the marked fraction:

$$S = -\tfrac34\log_2\tfrac34 - \tfrac14\log_2\tfrac14 = 0.311278 + 0.5 = 0.811278$$

Checked against Qiskit's entropy(partial_trace(...)):

text measured (Qiskit) 0.8112781245 H2(1/4) closed form 0.8112781245 difference 3.331e-16

The general statement is $S = H_2(M/N)$ for $M$ marked states out of $N = 2^n$. That formula is doing more work than it looks like — §19.4's closing subsection uses it to show that this diagnostic gets quieter as the register gets bigger, which is the opposite of what you want from a test.

Why Uncomputation and Not Measurement

The obvious alternative is to measure the ancilla and reset it. It is one instruction, it definitely returns the ancilla to $|0\rangle$, and it looks like it should be cheaper than running the whole computation backwards.

It does not work, and the reason is the derivation above.

Measuring the ancilla in the computational basis projects onto one of the two branches. With probability $3/4$ you read 0 and the input register collapses to $(|00\rangle+|01\rangle+|10\rangle)/\sqrt3$; with probability $1/4$ you read 1 and it collapses to $|11\rangle$. Either way the uniform superposition over four states is gone, and the interference the algorithm was built around has nothing left to interfere.

Averaged over the two outcomes — which is what you get if you throw the measurement result away — the input register is the same mixed state $\rho_{\text{in}}$ you had before measuring. Measuring a register you then discard is the same quantum channel as tracing it out. So the measurement changes nothing at all.

Measured, on the same circuit, same seed, 4,096 shots:

  strategy       counts                                            P(00)
  ----------------------------------------------------------------------
  uncompute      {'00': 4096}                                     1.0000
  reset          {'00': 2539, '01': 506, '10': 515, '11': 536}    0.6199
  measure        {'00': 2539, '01': 506, '10': 515, '11': 536}    0.6199
  nothing        {'00': 2539, '01': 506, '10': 515, '11': 536}    0.6199

reset, measure, and doing nothing at all produce bit-for-bit identical counts. Not merely similar distributions — the same integers, because the three circuits induce the same channel on the qubits that matter. qc.reset(2) is a measurement plus a conditional X, and the conditional X acts on a qubit that is no longer correlated with anything you keep.

Uncomputation is different in kind, not in degree. $\mathrm{CCX}$ is unitary and its own inverse, so applying it a second time returns the global state to a product — the entanglement is undone rather than averaged over. The operation succeeds precisely because no record was ever made. A measurement writes a classical bit somewhere, and no gate erases a classical bit; a unitary writes nothing, and every unitary has an inverse.

That gives the condition under which the pattern is valid, and it is worth stating as a rule:

An ancilla can be uncomputed if and only if its value is a deterministic function of registers you still hold. If $a = g(x)$ and $x$ is untouched, running the circuit that computed $a$ again XORs $g(x)$ into it a second time, and $g(x) \oplus g(x) = 0$.

The corollary is a stack discipline. An ancilla whose value depends on a second ancilla cannot be uncomputed after that second ancilla has already been cleared — the information needed to reverse it is gone. Ancillas must be released in the reverse of the order they were allocated, which is why production reversible-circuit compilers manage ancilla lifetimes with an explicit stack and why §19.6's V-chain uncomputes its cascade backwards rather than forwards.

What it costs an actual algorithm. Take a circuit where two H layers should cancel exactly, so every shot returns 00 — and run it on a noiseless simulator:

  variant                  counts                                          P(00)
  with uncomputation       {'00': 4096}                                   1.0000
  WITHOUT uncomputation    {'00': 2539, '01': 506, '10': 515, '11': 536}  0.6199

Perfect interference becomes 62%. Nothing errored, nothing warned, and there is no noise anywhere in the simulation.

📊 What the Numbers Say — 0.6199 is a 4,096-shot estimate of $5/8$, and the exact value is derivable.

The circuit has no noise and no approximation, so its output distribution is a closed form. Write the post-oracle state with the uniform superposition added and subtracted:

$$\tfrac{1}{\sqrt N}\!\!\sum_{x \neq m}\!|x\rangle|0\rangle + \tfrac{1}{\sqrt N}|m\rangle|1\rangle > \;=\; \Big(\tfrac{1}{\sqrt N}\sum_x |x\rangle - \tfrac{1}{\sqrt N}|m\rangle\Big)|0\rangle > + \tfrac{1}{\sqrt N}|m\rangle|1\rangle$$

Now apply $H^{\otimes n}$. It maps the uniform superposition to $|0^n\rangle$ exactly, and it maps $\tfrac{1}{\sqrt N}|m\rangle$ to $\tfrac1N\sum_y(-1)^{m\cdot y}|y\rangle$, which contributes $1/N$ to $|0^n\rangle$. So the amplitude on $|0^n\rangle$ is $1 - 1/N$ in the ancilla-0 branch and $1/N$ in the ancilla-1 branch, and the branches do not interfere:

$$P(0^n) = \Big(1 - \tfrac1N\Big)^2 + \tfrac1{N^2}$$

At $n = 2$: $(3/4)^2 + (1/4)^2 = 10/16 = \mathbf{0.625}$. Verified against the statevector at $n = 2\dots6$, agreeing to $10^{-14}$.

So the measured 0.6199 is a sample, and the true value is 0.6250. The gap is shot noise and it is the size it should be: with $p = 0.625$ and 4,096 shots the standard error is $\sqrt{p(1-p)/N} = 0.00756$, and the deviation $0.625 - 0.6199 = 0.0051$ is 0.68 standard errors. In counts: 2,560 expected, 2,539 observed, $\sigma = \sqrt{960} = 31.0$. The other three outcomes are exactly $1/8$ each, or 512 counts, against measured 506, 515, and 536 — deviations of 0.28, 0.14, and 1.13 $\sigma$ with $\sigma = \sqrt{448} = 21.2$.

Nothing here is a discrepancy. But the habit matters: Chapter 27 measured a false-failure rate of 1.0% from 2 events in 200 runs that was really 0.150% at 2,000 runs, and the fix in both cases is to ask whether the digits you are quoting are digits the sample can support. Quote 0.62, or quote $5/8$ and say the run gave 0.6199. Do not quote 0.6199 as though it were the answer.

🐛 Debug This — a dirty ancilla looks exactly like decoherence.

An algorithm that leaves ancillas entangled produces a mixed input register, and the symptoms are washed-out interference, reduced contrast, and a result that degrades as you add qubits.

Which is indistinguishable from noise, and will be diagnosed as noise, because that is what it looks like.

Chapter 12 §12.7 step 2 settles it in one line: does it fail in noiseless simulation too? A dirty ancilla fails identically with all noise removed. Decoherence does not.

This is the fifth distinct bug in this book that a noiseless simulation catches immediately and that gets investigated as physics first.

📉 Noise Report — "it looks like noise" is not a figure of speech. Here is the noise it looks like.

Take the correct circuit — uncomputation included, no bug at all — and run it under a depolarizing model on Aer: two-qubit error $p$ on cx, single-qubit error $p/10$, 4,096 shots, basis [cx, u, id], seed 1234.

```text 2q depol p P(00) P(01) P(10) P(11)

---

     0.000    1.0000    0.0000    0.0000    0.0000
     0.010    0.9094    0.0281    0.0361    0.0264
     0.050    0.6421    0.1189    0.1272    0.1118
     0.100    0.4561    0.1787    0.1924    0.1729
     0.200    0.3079    0.2300    0.2341    0.2280
     0.500    0.2612    0.2507    0.2351    0.2529

```

And here is the buggy circuit on a completely noiseless simulator, printed on the same four columns:

text noiseless 0.6199 0.1235 0.1257 0.1309

The dirty-ancilla row and the $p = 0.050$ row are the same distribution to within shot noise. A fidelity number, a total-variation distance, a success probability — none of them separate these two circuits, because on these four outcomes there is nothing to separate.

And the required noise level is not exotic. Chapter 30 measured quoted two-qubit error rates spanning 0.00750 to 0.07205 on a single chip — a factor of 9.6 — and Chapter 39 found cz errors from $1.79\times10^{-3}$ up to 1.00 on dead links. (A simulator's depolarizing parameter and a vendor's reported gate error are not the same quantity, so this is an order-of-magnitude comparison, not an identity.) The point stands: a plausible bad link produces the same picture as the bug, so "our fidelity is consistent with the reported device errors" is not evidence that the circuit is correct.

The separation is free and takes one line: set the noise model to None. The buggy circuit is unchanged; the correct one snaps to {'00': 4096}.

Where the Entropy Diagnostic Goes Quiet

Entropy is the right diagnostic and it has a scaling problem worth knowing about before you rely on it in a test suite.

From the Math Aside, the input-register entropy after computing a single-marked predicate into an ancilla is $H_2(1/N)$ with $N = 2^n$. Measured, alongside the closed forms:

    n      N   entropy (measured)     H2(1/N)   P(all-0) exact
  --------------------------------------------------------------
    2      4             0.811278    0.811278         0.625000
    3      8             0.543564    0.543564         0.781250
    4     16             0.337290    0.337290         0.882812
    6     64             0.116115    0.116115         0.969238
    8    256             0.036875    0.036875         0.992218
   10   1024             0.011174    0.011174         0.998049

The signature weakens monotonically as the register grows. At $n = 2$ the bug costs 37.5 percentage points of success probability and shows up as 0.81 bits of entropy. At $n = 10$ the same structural bug costs 0.2 points and 0.011 bits.

This is the book's recurring failure mode in a new place: a measurement that cannot detect the thing being asked about. Part V documents six instances; this is a seventh shape, and it is worse than most because the diagnostic is correct — 0.011 bits really is the entropy — while being useless as an alarm. A tolerance of atol=1e-2 on an entropy assertion passes a broken 10-qubit oracle.

Three practical consequences:

Test small. An ancilla-hygiene test at $n = 2$ or $n = 3$ has an enormous signal; the same test at $n = 12$ has almost none. The bug is structural, so it does not need a big instance to appear — test the property where the property is loud. This inverts the usual instinct to test at realistic scale.

Assert exactly, not approximately. scratch_is_clean() compares the ancilla's reduced state to $|0\rangle\langle 0|$ at atol=1e-9, which is a machine-precision test that does not care about $N$. An entropy threshold does. Prefer the former.

Do not read a small entropy as a small problem. The damage to an algorithm is not the entropy; it is what the residual entanglement does over many iterations. Chapter 21's Grover applies its oracle $\lfloor\pi\sqrt N/4\rfloor$ times — 804 iterations for the 20-bit search — and a defect worth 0.011 bits per call is not worth 0.011 bits after 804 of them.

The standard pattern — compute, use, uncompute:

   |x> --[ compute ]-- ... -- [ uncompute ]--
   |0> --[   f(x)  ]--(use)-- [   f(x)†   ]-- |0>

The cost is roughly double, and it is not optional. §19.6 shows the alternative is worse.

19.5 What an Oracle Actually Costs

Query complexity counts oracle invocations. This section counts gates.

Decomposed into Clifford+T, a multi-controlled X on $n$ controls:

    n      CX        T     depth      T/n
    2       6        7        11      3.5
    3      14    1,905     3,923    635.0
    4      36    2,605     4,788    651.2
    5      84    5,745    11,685  1,149.0
    6     136   12,002    22,553  2,000.3
    8     264   26,978    43,413  3,372.2
   10     464   30,816    49,044  3,081.6

Twenty-seven thousand T gates for an 8-input oracle. Chapter 15 §15.8 measured that a single T gate takes a machine from 450 to 2,882 physical qubits, and that ten T gates put 98.6% of the machine into magic-state factories.

🗝️ Version Note — the T count you measure depends on the basis you ask for, and it is easy to measure a number that means nothing.

Transpiling the same MCXGate into a basis that includes rz gives:

text n CX t+tdg rz 2 6 7 0 3 14 0 15 <- ZERO T gates? 4 36 16 27 8 264 74 213

A 3-controlled X with zero T gates is not a discovery. The synthesizer emitted general rz rotations, and rz gates are not free — under error correction they must themselves be synthesized into Clifford+T at a precision-dependent cost.

Chapter 15's estimator prices them separately, and the difference is enormous:

text tCount=16, rotationCount= 0 -> 65,636 physical qubits tCount=16, rotationCount= 10 -> 475,956 physical qubits 7.2x tCount=16, rotationCount=100 -> 4,558,356 physical qubits 69x

One hundred arbitrary rotations cost 69× more than none, at a fixed T count.

To measure a meaningful T count, exclude rz from the basis and force genuine Clifford+T synthesis. That is what the table above does, and it is why its numbers are three orders of magnitude larger than the naive ones.

⚙️ Under the Transpiler — where the 26,978 T gates physically are.

The two tables above are the same circuit measured two ways, so the difference between them is accounted for exactly. Put the columns side by side:

```text n rz t (rz basis) T (Clifford+T) T per rz

---

2      0              7                7          -
3     15              0            1,905      127.0
4     27             16            2,605       95.9
6     95             42           12,002      125.9
8    213             74           26,978      126.3

10 241 286 30,816 126.7 12 269 578 34,608 126.5 ```

The last column is flat at roughly 126. The honest T count is not a different decomposition of the gate; it is the same decomposition with each surviving rotation replaced by its Clifford+T synthesis. At $n = 8$: $74 + 213 \times 126.3 = 26{,}976$, against a measured 26,978.

The per-rotation cost is measurable directly. One rz transpiled alone into Clifford+T at Qiskit 2.5.1's default precision:

text rz(pi/2) -> 0 T gates {'s': 1} Clifford rz(pi/4) -> 1 T gate {'t': 1} is a T rz(pi/8) -> 127 T gates {'h':128, 't':127, 's':66} rz(pi/16) -> 123 T gates rz(1.0) -> 124 T gates rz(0.1) -> 124 T gates

An arbitrary single-qubit rotation costs about 125 T gates, and the angle barely matters. Only the special angles are cheap: $\pi/2$ is $S$ and free, $\pi/4$ is literally one $T$. Everything else pays the full synthesis price, which is why §19.5's rz trap is a trap rather than a rounding error — each "one gate" you did not count is 125 gates you did not count.

This also explains the $n = 4$ outlier at 95.9. Some of that circuit's rotations land on Clifford or $T$ angles and synthesize for free, which drags the average down. The flat 126 at $n \geq 6$ is what you get once the angles are generic.

Optimization Levels Cannot Rescue It

The reflex on seeing 26,978 is to reach for the transpiler's optimization levels. Measured, same Clifford+T basis, seed_transpiler=7:

    n      opt=0      opt=1      opt=2      opt=3
  ----------------------------------------------
    4      2,605      2,605      2,605      2,605
    6     12,002     11,998     11,991     11,991
    8     26,978     26,950     26,687     26,687

The most aggressive setting saves 1.1%. Chapter 28 measured that optimization levels 2 and 3 differ on 14 of 40 circuit-seed pairs — they do real work on real circuits. They do almost nothing here, because the cost is not redundancy the peephole passes can find. It is rotation synthesis, and a synthesized rotation is already minimal.

Contrast the same sweep on the ancilla-available circuit of §19.6:

    n    opt=0    opt=1    opt=2    opt=3
  ----------------------------------------
    4       23       23       23       23
    6       39       39       39       39
    8       55       55       55       55

Identical at every level, and 491× smaller. That is the shape of the whole chapter in two tables: the cheap decomposition is a structural choice, not an optimization, and no amount of tuning the optimizer substitutes for making it.

📊 What the Numbers Say — the no-ancilla curve is not exponential, and extrapolating it is unsafe in both directions.

§19.5's table stops at $n = 10$ and the word "exponential-ish" appears in §19.6. Extending the measurement makes the shape clearer and less tidy:

```text n T increment T/n

---

2         7            -      3.5
3     1,905       +1,898    635.0
4     2,605         +700    651.2
6    12,002       +6,257  2,000.3
8    26,978       +9,328  3,372.2
9    28,848       +1,870  3,205.3

10 30,816 +1,968 3,081.6 11 32,692 +1,876 2,972.0 12 34,608 +1,916 2,884.0 13 44,497 +9,889 3,423.0 14 46,445 +1,948 3,317.5 ```

Three things are visible and none of them is a clean exponential.

The $n=2 \to n=3$ step is a factor of 272, and it is not growth — it is the synthesizer switching from an exact small-case decomposition (a Toffoli, 7 T gates) to a general construction that emits arbitrary rotations. The first data point and the rest are not on the same curve.

From $n = 9$ to $n = 12$ the increment is essentially constant at about 1,900 T gates per control — 14 additional rz rotations at ~126 T each, and the rz count increases by exactly 14 per step across that range. In that window the cost is linear, and the $T/n$ column consequently falls, from 3,372.2 at $n = 8$ to 2,884.0 at $n = 12$.

And then $n = 13$ jumps by 9,889. The curve is piecewise: long linear stretches punctuated by steps where the synthesis strategy changes. A reader who fits a line to $n = 9\dots12$ predicts about 36,500 at $n = 13$ against a measured 44,497 — 18% low. A reader who fits an exponential to $n = 2\dots6$ predicts something astronomical and is wrong by far more.

The correct reading is the one the chapter actually needs, and it survives all of this: at every $n$ measured, the no-ancilla cost is between two and four orders of magnitude above the ancilla-assisted cost. The argument was never about the asymptotics. It is about the numbers at the sizes anyone builds.

🔀 In Another Framework — the same trap, and one framework that reports the oracle as a single gate.

PennyLane 0.45.1. qml.specs() on a 9-wire circuit containing one MultiControlledX:

text num_gates = 1 depth = 1 gate_types = {'MultiControlledX': 1}

That is query complexity implemented as a resource counter. It is not wrong — the circuit does contain one gate — and it is the number a benchmark script would collect. Forcing the decomposition tells a different story:

text n=4 96 ops RZ 21, RY 14, CNOT 28, Toffoli 8, T 8, Adjoint(T) 6, ... n=6 184 ops RZ 33, RY 22, CNOT 36, Toffoli 48, T 8, Adjoint(T) 6, ... n=8 320 ops RZ 45, RY 30, CNOT 44, Toffoli 120, T 8, Adjoint(T) 6, ...

Fourteen T gates at every size, and 75 arbitrary rotations at $n = 8$. Read the T column and you conclude an 8-controlled X costs 14 T gates. §19.5's trap, in a different framework, with a different API, and the same wrong answer.

Cirq 1.7.0. cirq.X(q[8]).controlled_by(*q[:8]) builds a CCCCCCCCX as one operation in one moment. cirq.decompose expands it to 3,345 operations, of which:

text Y**0.5 840 CZ 748 Ry 464 Y**-0.5 748 T 185 T**-1 139

324 T-family gates and 464 un-synthesized Ry rotations. Cirq has no Clifford+T-only target gateset that forces those rotations to resolve, so the honest number is not directly available; what is available is a T count that omits the expensive part.

The lesson is framework-independent and the trap is framework-independent. Ask for a gateset that contains no continuous rotations, or the count you get is a count of the gates that happened to be cheap.

19.6 Ancillas: The Trade Worth Making

The 27,000-T-gate figure assumes no ancilla qubits. Allowing them changes everything:

    n  |  no ancillas: CX        T  |  v-chain: CX     T   ancillas
    4  |               36    2,605  |           18    23          2
    6  |              136   12,002  |           30    39          4
    8  |              264   26,978  |           42    55          6
   10  |              464   30,816  |           54    71          8

At $n = 8$: 26,978 T gates without ancillas, 55 with six of them. A 491× reduction.

And the CX count drops 6.3× as well, from 264 to 42.

The mechanism is a V-chain: instead of synthesizing one enormous $n$-controlled gate, build a cascade of Toffolis that accumulate the AND of the controls into ancillas, apply a single controlled operation, then uncompute the cascade. Each Toffoli costs 7 T gates (Chapter 15's project checkpoint asserts this), and you need $O(n)$ of them — linear instead of exponential-ish.

📐 Math Aside — why ancillas help this much.

Without ancillas, an $n$-controlled gate must be decomposed using only the $n+1$ qubits available, and the known constructions have gate counts growing far faster than linearly — you are repeatedly recomputing partial products because there is nowhere to store them.

With ancillas you compute the conjunction once, in a chain:

$$a_1 = x_1 \wedge x_2,\quad a_2 = a_1 \wedge x_3,\quad \dots,\quad a_{n-1} = a_{n-2} \wedge x_n$$

That is $n-1$ Toffolis to compute, one controlled operation, and $n-1$ to uncompute — which is §19.4's pattern, now doing real work rather than housekeeping.

This is the classical space–time trade, and it is the same shape as Chapter 15 §15.8's T-factory saturation: beyond a point, more space buys less time. Here, six qubits buy a 491× reduction, which is about as favourable as the trade ever gets.

🗝️ Version Note — you do not have to ask for this, and the way you used to ask is deprecated.

The mode="v-chain" argument to mcx() is deprecated as of Qiskit 2.1 and slated for removal in 3.0:

text DeprecationWarning: QuantumCircuit.mcx()'s argument `mode` is deprecated as of Qiskit 2.1. Instead, add a generic MCXGate and specify the synthesis method via the `hls_config` in transpilation.

And the replacement is better than the thing it replaces. Add a plain MCXGate and simply give the circuit spare qubits — HighLevelSynthesis finds the cheap decomposition on its own:

text n = 6, MCXGate in a 7-qubit circuit (no room) 12,002 T gates n = 6, MCXGate in a 12-qubit circuit (5 spare) 39 T gates

Identical to the explicit synth_mcx_n_clean_m15 result. The transpiler was always willing to do this; it just had nowhere to put the ancillas.

So the practical rule is not "call the v-chain API" but "leave the transpiler room." A circuit sized exactly to its logical qubits silently forgoes a 491× reduction — which is a strange and important thing to know about the tool.

If you need a specific synthesis, qiskit.synthesis.synth_mcx_n_clean_m15 (clean ancillas) and synth_mcx_n_dirty_i15 (dirty ancillas, slightly more expensive — 46 versus 39 T gates at $n=6$) are the supported entry points. Verified against Qiskit 2.5.1.

📐 Math Aside — the V-chain cost is exactly $8n - 9$, and the derivation corrects the chapter's own estimate.

The mechanism paragraph above says a Toffoli costs 7 T gates and you need $O(n)$ of them, which predicts $14(n-1)$ — 98 T gates at $n = 8$ against a measured 55. example-04-ancilla-tradeoff.py notes the gap and attributes it to "overhead." It is not overhead. It is a saving, and it has an exact size.

Measure the two building blocks separately, in the same Clifford+T basis:

text ccx (Toffoli) CX = 6 T = 7 depth = 11 rccx (relative-phase) CX = 3 T = 4 depth = 9

A relative-phase Toffoli computes the same AND but leaves a state-dependent phase behind, and it costs 4 T gates instead of 7. The V-chain can use them almost everywhere, because every intermediate ancilla is uncomputed by the inverse of the gate that computed it — whatever phase the forward pass introduced, the backward pass removes. Only the apex gate produces a result that is used rather than reversed, so only the apex needs to be a true Toffoli.

With $n$ controls and $n-2$ ancillas the structure is $n-2$ relative-phase Toffolis forward, one full Toffoli, and $n-2$ relative-phase Toffolis back:

$$T = 2(n-2)\cdot 4 + 7 = 8n - 9, \qquad \mathrm{CX} = 2(n-2)\cdot 3 + 6 = 6(n-1)$$

Checked against the transpiler at every size from 3 to 12:

```text n predicted T measured T predicted CX measured CX

---

3            15           15             12            12
4            23           23             18            18
6            39           39             30            30
8            55           55             42            42

10 71 71 54 54 12 87 87 66 66 ```

Exact at every point, with no fitted constant. Depth is also exactly linear — $14(n-1)$, verified from $n = 3$ to $n = 16$ — though that one does not follow from summing the pieces, because the transpiler overlaps gates that act on disjoint qubits.

The naive estimate overshoots by $(14n-14) - (8n-9) = 6n - 5$, which is 43 at $n = 8$: exactly $98 - 55$. The relative-phase Toffoli is worth a factor of $14/8 = 1.75$ asymptotically, and it is available only because of uncomputation — §19.4's discipline paying for itself a second time.

491× Is a Value at $n = 8$, Not a Trend

The headline number deserves the same scepticism the chapter applies to everyone else's. Extend the comparison across sizes:

    n   no ancilla T   v-chain T     ratio
  ------------------------------------------
    3          1,905          15      127x
    4          2,605          23      113x
    5          5,745          31      185x
    6         12,002          39      308x
    7         17,650          47      376x
    8         26,978          55      491x
    9         28,848          63      458x
   10         30,816          71      434x
   11         32,692          79      414x
   12         34,608          87      398x
   13         44,497          95      468x
   14         46,445         103      451x

491× is the maximum of the measured range, and the curve is not monotonic. It rises to $n = 8$, falls to 398× at $n = 12$, and jumps back to 468× at $n = 13$ — because the numerator is the piecewise curve of §19.5 and the denominator is the clean line $8n - 9$. The ratio inherits every step and plateau in the no-ancilla synthesis.

§19.6's phrase "about as favourable as the trade ever gets" turns out to be literally accurate, and that was not known when it was written. The honest form of the claim is: at $n = 8$, six ancillas reduce the T count by 491×; across $n = 3$ to $14$ the reduction ranges from 113× to 491× and never falls below two orders of magnitude. The two-orders-of-magnitude statement is the one that is safe to carry forward, and it is more than enough to decide the design.

💰 Cost and Queue — what 491× fewer T gates buys, and what it does not.

Feed both variants to Chapter 15's resource estimator. Inputs are the measured T counts and the circuit widths each construction actually uses — 9 qubits without ancillas, 15 with — with rotationCount = 0 so the T count is the whole story:

```text variant T physical algorithm factories %fact runtime

---

no ancillas 26,978 300,600 12,600 288,000 95.8% 161.874 ms v-chain 55 81,444 10,164 71,280 87.5% 0.246 ms

runtime ratio 657x physical-qubit ratio 3.69x ```

Three numbers and they do not agree with each other. The T count fell 491×. The estimated runtime fell 657× — more than the T count, because a shorter T-sequence also needs fewer logical cycles. And the physical qubit count fell only 3.69×.

The space saving is the disappointing one, and the reason is structural. 87.5% of the smaller machine is still magic-state factories. You cannot distil with less than one factory, and one factory is large. Chapter 21 §21.6 found 90.6% for a 16-bit Grover search; every estimate in this family lands between 87% and 96%. The floor is set by the existence of distillation, not by how much of it you need.

This is the book's standing observation in its sharpest form: every remedy is denominated in the currency of the disease. A 491× reduction in T gates buys 657× in time and 3.7× in space, because the thing you removed was time-like. If your constraint is qubit count rather than runtime, the ancilla trade helps you far less than the headline suggests — and the headline is a T count, which is neither.

One caveat on reading the table: the two rows have different numQubits inputs, so this is a comparison of two designs, not of one design under two settings. That is the right comparison for the decision at hand, and it is not a controlled experiment on a single variable.

The Dirty-Ancilla Variant Costs Exactly One Toffoli

The V-chain above assumes the ancillas start in $|0\rangle$. Often they do not — they are qubits holding other live data that you are borrowing. Qiskit exposes both:

    n   synth_mcx_n_clean_m15   synth_mcx_n_dirty_i15   difference
  ----------------------------------------------------------------
    4                      23                      30           +7
    6                      39                      46           +7
    8                      55                      62           +7
   10                      71                      78           +7

Exactly seven T gates more, at every size — one additional full Toffoli. Not a percentage, not a scaling penalty, a constant. Both constructions use the same 15 qubits at $n = 8$.

So "I do not have clean ancillas" is not a reason to fall back to the no-ancilla synthesis. At $n = 8$ the choice is 55, 62, or 26,978. The interesting decision is between borrowed and none; the decision between borrowed and clean is a rounding error.

🗝️ Version Note — there is no such thing as "the no-ancilla cost," and Qiskit 2.5.1 ships four synthesis routines that disagree.

qiskit.synthesis exposes synth_mcx_n_clean_m15, synth_mcx_n_dirty_i15, synth_mcx_noaux_v24, and synth_mcx_gray_code — all present and importable in this environment. The first two are the V-chain constructions above. The third is an explicit no-ancilla synthesis, and it does not agree with what HighLevelSynthesis picks by default:

```text n default (no room) synth_mcx_noaux_v24 difference

---

4               2,605                 2,605         same
6              12,002                13,872         +16%
8              26,978                18,864         -30%

10 30,816 20,194 -34% ```

At $n = 6$ the explicit routine is worse; at $n = 10$ it is a third cheaper. Both are correct circuits for the same gate on the same number of qubits.

This tightens §19.5's warning by one notch. The trap there was which basis you measure in; this one is which synthesis ran, and the default is chosen for you by a transpiler pass on the basis of circuit width. A T count for a multi-controlled X is not a property of the gate. It is a property of the gate, the basis, the available width, and the Qiskit version — four things, of which most published numbers specify one.

Also new enough to be worth naming: qiskit.circuit.library.PhaseOracle is present in 2.5.1 and compiles boolean expression strings — PhaseOracle("(a & b) | (c & ~d)") — directly into a phase oracle, no X sandwich required. It is the right starting point for §19.7's Case 2, and it is subject to every cost caveat in this chapter.

When the Trade Reverses

The 491× is a fault-tolerance number. It assumes T gates are the currency, which Chapter 15 §15.8 established for anything running under error correction. On hardware you can use today, none of that is true, and the calculation has to be redone.

On the gate-count axis, the trade does not reverse. The V-chain uses 42 CX at $n = 8$ against 264 — a 6.3× reduction on the metric that actually dominates NISQ fidelity. There is no regime in these measurements where the no-ancilla construction is cheaper in two-qubit gates.

On the qubit axis it can. The V-chain widens the circuit from 9 qubits to 15, and width is not free on a real device:

• Chapter 30 measured quoted two-qubit error rates on one chip ranging from 0.00750 to 0.07205 — a factor of 9.6. Six more qubits means six more draws from that distribution.
• Chapter 29 measured a hardware-aware transpilation at optimization level 1 scoring 0.9116 against a layout-naive level 3 at 0.7720, and a hand-picked chain at 0.6790 against a calibration-picked one at 0.9764. Layout choice is worth more than optimization level.
• Chapter 39 ran the same 14-qubit layout problem across 24 seeds and got fidelities from 0.5755 to 0.7911 — a 2.03× spread in error — with two-qubit gate counts from 49 to 112. The same test on 4 qubits produced exactly zero variation.

That last measurement is the one that matters here. Widening an oracle from 9 qubits to 15 moves it out of the regime where layout is irrelevant and into the regime where it is the dominant term. The 6.3× reduction in CX is real and probably wins, but probably is the honest word, and the experiment that settles it is a layout sweep on your device, not an argument.

The rule that survives both regimes: allocate the ancillas, then measure. Under error correction the answer is 491×; on hardware today the answer is a fidelity number you have to go and get.

🧱 Project Checkpoint — vqelab/oracles.py: building and pricing them.

Part IV's project thread starts here, and it builds on everything Part II and III produced.

bit_oracle(n, predicate) constructs a boolean oracle from a Python predicate by enumerating the marked set — honest about being exponential in $n$, and correct, which is what you want for testing against.

phase_oracle(bit_oracle) wraps one in the $|-\rangle$ preparation, returning the phase oracle algorithms actually consume, and asserts the scratch qubit is unentangled afterwards — because §19.4's failure is invisible otherwise.

oracle_cost(circuit) returns the honest Clifford+T cost, excluding rz from the basis so the T count means something, and reports the rotation count separately with a warning when it is nonzero — §19.5's trap, encoded.

compare_ancilla_strategies(n) measures the trade in §19.6's table for your own $n$.

Its tests assert: the oracle marks exactly the intended state; phase kickback produces exactly $-1$ on marked inputs and $+1$ elsewhere; an un-uncomputed ancilla leaves the input register mixed (nonzero entropy); and the ancilla strategy reduces the T count by more than 10× at $n = 6$.

19.7 What Query Complexity Promises

The honest section.

Query complexity is a real and rigorous model. Statements like "Grover's algorithm needs $O(\sqrt N)$ queries where any classical algorithm needs $\Omega(N)$" are theorems, and the lower bounds are proved, not conjectured. That is genuinely more than most quantum speedup claims can say.

And it measures one thing while people hear another.

🔬 Honest Assessment — three gaps between "one query" and "one operation."

The oracle is not free. §19.5 measured 26,978 T gates for an 8-input marked-state oracle, and a realistic predicate is more complex than "is $x$ equal to 3." A quadratic reduction in the number of queries is worth having only if each query is not itself the dominant cost — and Chapter 15's resource estimates say that for anything fault-tolerant, T gates are the cost.

The oracle must exist. Query complexity assumes a black box implementing $f$. Building that box requires a reversible circuit for $f$, which means every classical intermediate value needs ancilla space and uncomputation (§19.4). For a database search — the canonical Grover example — you would need a circuit that recognizes the target, which means the data must be in the circuit, not in a database. Chapter 21 §21.7 returns to this, and it is the reason "Grover searches a database" is misleading.

The speedup is over a restricted classical model. The classical lower bound is over algorithms that can only query the oracle. A classical algorithm that can inspect $f$'s structure — read the source code, exploit sparsity, use a hash index — is not bound by it at all. Query complexity compares two black-box algorithms, and real classical algorithms are rarely black-box.

None of this makes the theorems wrong. It makes them narrower than the headline. The correct reading of "quadratic speedup in query complexity" is: if the oracle is cheap, if it can be built, and if the classical competitor is genuinely restricted to queries, then this is faster. Three conditions, each of which fails for some real problems.

Chapter 20 measures the algorithms; Chapter 21 measures the gap for Grover specifically; Chapter 23 shows what it looks like when a speedup is exponential and the conditions do hold.

When Is an Oracle Actually Available?

"The oracle must exist" is the second gap, and it is the one people find hardest to take seriously, because in a paper the oracle always exists. It is worth separating into three cases, because they have genuinely different answers.

Case 1: the oracle is the problem statement. Deutsch–Jozsa, Bernstein–Vazirani, and Simon's algorithm (Chapter 20) do not ask you to build anything. You are handed a black box and asked a question about it — is $f$ constant or balanced, what is the hidden string, what is the period. The construction cost is zero because it is not yours.

These are the only problems in Part IV where query complexity is the correct accounting, and it is not a coincidence that they are also the only ones with no application. The promise that makes them exactly solvable — the function is guaranteed constant or balanced, the function is guaranteed to be a parity — is a guarantee nobody hands you about a real function. Chapter 20 §20.5 measures what happens when the promise is violated, and the answer is that the algorithm returns a confident wrong answer with no indication that anything went wrong.

Case 2: you have a formula and must compile it. Grover applied to SAT, graph colouring, or a constraint system. You genuinely possess a description of $f$ — a CNF formula, a set of constraints — and compiling it to a reversible circuit is a real, finite, computable-in-advance task. Qiskit will do it for you:

  PhaseOracle("(a & b) | (c & ~d)")     4 variables

    in a  4-qubit circuit (no room)     1,912 T gates
    in a 10-qubit circuit (6 spare)        22 T gates      87x

Four variables, two clauses, and one of the smallest non-trivial boolean expressions there is — 1,912 T gates when the circuit is sized to the expression. Case Study 2's lesson reappears unchanged in the high-level API: the same expression costs 22 T gates given room to work.

Case 2 is the interesting case, and it is where the arithmetic has to be done rather than assumed.

Case 3: you have data, not a function. This is "search a database," and it is the case that does not work. There is no formula to compile — there are $N$ rows. Building an oracle that recognizes the target means getting all $N$ rows into the circuit, and that is $\Omega(N)$ work: the exact cost the $\sqrt N$ was supposed to avoid, paid in full before the first query.

Chapter 21 §21.7 is where this is settled, and the conclusion is that Grover does not search a database. It searches the domain of a function you already have.

📐 Math Aside — the amortization inequality, which decides all three cases in one line.

Let $C$ be the one-time cost of constructing the oracle and $c$ the cost of one query. Grover makes $\Theta(\sqrt N)$ queries, so the quantum total is $C + c\sqrt N$ against a classical $N$ evaluations of a cheap function. The speedup requires

$$C + c\sqrt N \;\ll\; N$$

Two conditions, and each case above fails or passes a different one.

Case 1 sets $C = 0$ by assumption and $c = 1$ by fiat. The inequality holds trivially, which is exactly why the model was built this way — and exactly why it proves nothing about anything else.

Case 2 has $C$ small (a compile, done once) and $c$ large. The binding condition is $c \ll \sqrt N$. So expensive oracles hurt and large $N$ helps, and both scale — which is Case Study 1's crossover argument, and it is why a 20-bit search at ~3,000 T gates per query ($c \approx 3000$, $\sqrt N \approx 1000$) fails: $c > \sqrt N$, so the quantum side loses before the comparison to classical even begins.

Case 3 has $C = \Omega(N)$. The first term alone violates the inequality regardless of $c$, $N$, or how good the hardware gets. No improvement in query cost or in hardware fixes a construction cost that is linear in the search space, which is why this case is not a quantitative disappointment but a structural impossibility.

The inequality also names the honest question to ask any speedup claim: which of $C$ and $c$ did you measure, and in what units? Case Study 1's team measured neither, and had the right theorem.

Why the Construction Cost Is Missing From the Papers

It is worth being fair about the omission, because it is not carelessness and it is not marketing.

Query complexity was built to prove lower bounds. A statement like "any classical algorithm needs $\Omega(N)$ queries" quantifies over every algorithm in a class, and it is provable precisely because the model abstracts implementation away. Reasoning about arbitrary circuits is intractable; reasoning about how many times a black box is consulted is not. The abstraction is what makes the theorem possible.

And the same abstraction that makes the lower bound provable makes the upper bound misleading. Grover's $O(\sqrt N)$ is stated in the same units as the $\Omega(N)$ it is compared against, and it has to be — the comparison is only meaningful if both sides count the same thing. The free-oracle assumption is not an oversight in the upper bound; it is inherited from the lower bound, and you cannot drop it on one side only.

What goes wrong happens later, when the two numbers leave the paper. $10^6$ versus $10^3$ is quoted as though the left side were CPU operations and the right side were something comparable, and it is not: Chapter 20's 📊 What the Numbers Say makes the same point about a 562-trillion column, and Case Study 1 watches a team make the substitution in a planning meeting.

"Compared to what?" is the standing question, and here it has a precise form: compared to a classical algorithm restricted to the same black box, counting the same unit, with the box's construction charged to neither side. That is a fair comparison and it is not the comparison anyone is interested in.

📐 Math Aside — Clifford+T, and why one gate out of the set gets its own column.

Two facts explain why every cost table in this chapter counts T gates and ignores everything else.

A circuit of Clifford gates alone has no quantum advantage — by theorem. The Clifford group is generated by $H$, $S$, and CNOT, and the Gottesman–Knill theorem says a circuit built only from those, acting on a computational-basis input with computational-basis measurements, is simulable classically in polynomial time. Chapter 11's stabilizer simulator is that theorem as a piece of software. So whatever makes a quantum computation hard to reproduce classically lives entirely in the non-Clifford gates, and $T = \mathrm{diag}(1, e^{i\pi/4})$ is the standard cheapest one. $\{H, S, \mathrm{CNOT}, T\}$ is universal.

And under error correction the two halves of that set cost wildly different amounts. Many Clifford operations are transversal in a topological code, and some — the Pauli corrections and $S$ — need not be physically applied at all: they can be tracked in software as a frame and folded into the interpretation of later measurements. A Clifford gate can literally cost zero physical operations. No 2D topological code makes a universal gate set transversal, so $T$ cannot be had that way. It is supplied by consuming a magic state, and magic states must be distilled from many noisy copies in a dedicated factory.

Chapter 15 §15.8 measured what that costs: one T gate takes a machine from 450 to 2,882 physical qubits — a 6.4× cliff for a single gate — and ten T gates put 98.6% of the machine into factories. §19.6's estimates land in the same place: 95.8% of a 300,600-qubit machine, 87.5% of an 81,444-qubit one.

So "T count" is not a proxy for cost under error correction. It is very nearly the cost. Which is also why §19.5's rz trap is fatal rather than untidy: an arbitrary rotation is ~125 T gates, so at $n = 8$ the rotation-basis measurement reports 74 T gates against a true 26,978. It omits 99.7% of the bill and reports the remainder with confidence.

19.8 Summary

An oracle is a reversible circuit implementing a classical function. Since classical functions discard information, the standard construction keeps the input and XORs the answer into a scratch qubit: $U_f|x\rangle|y\rangle = |x\rangle|y \oplus f(x)\rangle$, which is its own inverse.

Building one from a predicate is mechanical: an X sandwich around a multi-controlled X, since MCX fires only when all controls are 1. The second X layer is not optional — omitting it marks the wrong state without raising an error.

★ Phase kickback is the essential trick. With the scratch qubit in $|-\rangle$, an eigenvector of $X$ with eigenvalue $-1$:

$$U_f\left(|x\rangle|-\rangle\right) = (-1)^{f(x)}|x\rangle|-\rangle$$

Verified: amplitude ratio exactly $+1$ where $f=0$ and exactly $-1$ where $f=1$, with the scratch qubit left unentangled. The bit oracle puts the answer where it cannot interfere; kickback moves it into the phase, where it can. Amplitudes interfere; register contents do not — which is why quantum algorithms are about phases, and why this is the same mechanism as phase estimation (Chapter 22).

Uncomputation is mandatory, not tidy. Measured: computing into an ancilla leaves the input register at entropy 0.8113 — entangled, mixed, and unable to interfere. Uncomputing returns it to 0.0000. A dirty ancilla is indistinguishable from decoherence and will be diagnosed as noise; Chapter 12 §12.7 step 2 settles it in one line, since a dirty ancilla fails identically with all noise removed.

★★ Query complexity hides the cost. Decomposed into genuine Clifford+T, a multi-controlled X:

    n = 2:       7 T gates          n = 6:   12,002 T gates
    n = 4:   2,605 T gates          n = 8:   26,978 T gates

⚠️ And the T count you measure depends on the basis. Including rz in the basis reports zero T gates for a 3-controlled X — the synthesizer emitted rotations instead, and rotations are not free: at fixed T count, 100 of them cost 69× more physical qubits than none. Exclude rz to get a meaningful number.

★★ Ancillas are the trade worth making. At $n = 8$: 26,978 T gates with no ancillas, 55 with six — a 491× reduction, plus 6.3× fewer CX gates. A V-chain accumulates the conjunction in $O(n)$ Toffolis at 7 T gates each, instead of repeatedly recomputing partial products with nowhere to store them.

★ And the V-chain cost is exactly $8n - 9$ — verified at every $n$ from 3 to 12 with no fitted constant, alongside $\mathrm{CX} = 6(n-1)$ and depth $= 14(n-1)$. The structure is $2(n-2)$ relative-phase Toffolis at 4 T each plus one true Toffoli at 7. The chapter's own $14(n-1)$ estimate overshoots by exactly $6n - 5$, which is the 43-gate gap between its predicted 98 and the measured 55 — not overhead, a saving, and one that exists only because uncomputation makes the cheap relative-phase gate safe to use.

491× is a value at $n = 8$, not a trend. Across $n = 3\dots14$ the reduction ranges from 113× to 491× and is not monotonic, because the numerator is a piecewise curve and the denominator is a straight line. The claim safe to carry forward is "two to three orders of magnitude at every size measured," which is more than enough to decide the design.

And the saving is not evenly denominated. Chapter 15's estimator prices the two designs at 300,600 versus 81,444 physical qubits and 161.874 ms versus 0.246 ms: a 491× T reduction buys 657× in time and only 3.69× in space, because 87.5% of even the small machine is still magic-state factories. Every remedy is denominated in the currency of the disease.

★ Measurement is not a substitute for uncomputation. Measured on the same circuit and seed, reset, measure, and doing nothing at all give bit-for-bit identical counts — 0.6199 in all three — because discarding a measured register is the same channel as tracing it out. Uncomputation works because it is unitary and no record was ever made; the corollary is that ancillas must be released in reverse allocation order.

⚠️ And the entropy diagnostic gets quieter as the register grows. The measured 0.8113 is exactly $H_2(1/4)$, and the general form $H_2(1/N)$ falls to 0.0369 at $n = 8$ and 0.0112 at $n = 10$ for the same structural bug. Test ancilla hygiene at small $n$, where the signal is loud, and assert purity exactly rather than against a threshold.

Query complexity is rigorous and narrower than the headline. Three gaps: the oracle is not free (27,000 T gates); the oracle must exist as a reversible circuit, which means the data is in the circuit rather than in a database; and the classical lower bound is over algorithms restricted to queries, which real classical algorithms are not. The theorems are correct; "quadratic speedup" carries three conditions, each of which fails for some real problems.

Next: Chapter 20 — Deutsch, Deutsch–Jozsa, Bernstein–Vazirani, and Simon's algorithm: the first four algorithms with proven quantum advantage, each built from this chapter's oracle plus one idea. They are small, they are exactly solvable, and they are where the pattern that all of Part IV follows becomes visible.