Chapter 19 — Key Takeaways (Quantum Oracles)

DataField.Dev

Chapter 19 — Key Takeaways (Quantum Oracles)

Part IV opens. §19.3's phase kickback is what every later algorithm runs on; §19.7 is the honest part.

What an oracle is

Classical functions discard information; quantum operations must be unitary. The fix keeps the input:

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

XOR is its own inverse, so $U_f^2 = I$.

def bit_oracle(n, marked):
    qc = QuantumCircuit(n + 1)
    bits = format(marked, f"0{n}b")[::-1]
    for i, b in enumerate(bits):
        if b == "0": qc.x(i)        # flip the zeros
    qc.append(MCXGate(n), list(range(n + 1)))
    for i, b in enumerate(bits):
        if b == "0": qc.x(i)        # NOT optional
    return qc

⚠️ The second X layer is not optional. Omitting it marks a permuted state. No error, no warning — the algorithm returns a confident wrong answer.

The bit oracle alone is useless

  scratch in |0>, uniform input:  [0.5, 0.5, 0.5, 0, 0, 0, 0, 0.5]

The marked term moved into the scratch register. Measuring it collapses the superposition and gives one random $x$ — no better than evaluating $f$ classically.

Computing $f$ on a superposition is trivial. Extracting anything useful requires the answers to INTERFERE, and information in a separate register does not interfere with anything.

★★ Phase kickback

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

   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

   uniform input -> [+0.354, +0.354, +0.354, -0.354]

Exactly $\pm1$, and the scratch qubit is left unentangled.

⚛️ The scratch qubit is used as an eigenvector — applying an operator to its own eigenvector multiplies by the eigenvalue and leaves the state alone, so the eigenvalue is kicked back onto the control register. This is phase estimation with one bit of precision (Ch. 22), and the resemblance is exact.

The phase oracle $O_f|x\rangle = (-1)^{f(x)}|x\rangle$ is what algorithms use. You never build it directly — you build the bit oracle and prepare the scratch in $|-\rangle$.

★ Uncomputation is mandatory

  after computing into an ancilla : entropy = 0.8113
  after UNCOMPUTING               : entropy = 0.0000

Nonzero entropy = the input register is entangled, hence mixed, hence cannot interfere — Chapter 4's classical impostor arriving from bookkeeping rather than noise.

What it costs an algorithm (noiseless simulator, two H layers that should cancel exactly):

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

🐛 A dirty ancilla is indistinguishable from decoherence — washed-out contrast, degradation with size. Ch. 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. Fifth such bug in this book.

Pattern: compute → use → uncompute. Roughly double the cost, and not optional.

★★ What an oracle actually costs

Genuine Clifford+T (no rz in the basis):

    n      CX        T     depth
    2       6        7        11
    4      36    2,605     4,788
    6     136   12,002    22,553
    8     264   26,978    43,413
   10     464   30,816    49,044

An 8-input oracle costs ~27,000 T gates, and Ch. 15 §15.8 measured that one T gate takes a machine from 450 to 2,882 physical qubits.

⚠️ The measurement trap

With rz in the basis:

    n     cx   t+tdg    rz
    3     14       0    15     <- ZERO T gates?
    8    264      74   213

A 3-controlled X with zero T gates is not a discovery — the synthesizer emitted rotations. And rotations are not free:

  tCount=16, rotationCount=  0  ->     65,636 physical qubits
  tCount=16, rotationCount=100  ->  4,558,356 physical qubits    69x

Exclude rz to get a meaningful T count. Chapter 15's estimator takes rotationCount as a separate input for exactly this reason.

★★ Ancillas: a 491× reduction

    n  |  no ancillas: CX        T  |  with ancillas: CX     T   extra qubits
    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 → 55 T gates. A 491× reduction for six qubits, plus 6.3× fewer CX.

Mechanism: a V-chain accumulates the conjunction in $n-1$ Toffolis (7 T each) and uncomputes — linear, instead of repeatedly recomputing partial products with nowhere to store them.

🗝️ You do not have to ask for this. mcx(mode="v-chain") is deprecated in Qiskit 2.1. The replacement is better: add a plain MCXGate and give the circuit spare qubits — HighLevelSynthesis finds it.

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

The practical rule is "leave the transpiler room." A circuit sized exactly to its logical qubits silently forgoes a 491× reduction. Explicit entry points if needed: synth_mcx_n_clean_m15, synth_mcx_n_dirty_i15 (46 vs 39 T at $n{=}6$).

🔬 What query complexity promises

It is rigorous — the lower bounds are proved, not conjectured. And it measures one thing while people hear another. Three gaps:

The oracle is not free. ~27,000 T gates, and T gates are the cost of fault tolerance.

The oracle must exist as a reversible circuit. Early exits, lookup tables, and short-circuiting — what makes classical checkers fast — do not survive reversibility. For "database search," the data must be in the circuit, not in a database (Ch. 21 §21.7).

The classical bound is over query-only algorithms. Real classical algorithms inspect structure, prune, and index. A speedup over a straw man is not a speedup.

Correct reading: 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.

Common pitfalls

Omitting the second X layer (marks the wrong state, silently).
Measuring a T count with rz in the basis.
Leaving ancillas dirty, then diagnosing the result as noise.
Sizing a circuit to exactly its logical qubits.
Comparing query counts against classical operations — different units.
Believing a quadratic speedup without pricing one query.

Project piece added this chapter

vqelab/oracles.py — marked_states(), bit_oracle(), phase_oracle(), phase_signs(), scratch_is_clean(), input_register_entropy(), oracle_cost() (defaults to Clifford+T and flags any rotation-basis measurement as UNTRUSTWORTHY), and compare_ancilla_strategies(). 13 tests pass, including exact $\pm1$ phase signs, a dirty ancilla detected by entropy, and test_rotations_hide_the_t_count_by_orders_of_magnitude.