Quiz: Quantum Oracles

Answers with explanations at the end.

1. Why can't a quantum oracle simply compute $|x\rangle \to |f(x)\rangle$? Write the construction that is used instead and explain why it is reversible.

2. In bit_oracle, what is the X sandwich for, and what happens if you omit the second layer?

3. A bit oracle applied to a uniform superposition with the scratch in $|0\rangle$ gives [0.5, 0.5, 0.5, 0, 0, 0, 0, 0.5]. Where did the marked term go, and why is this result useless?

4. State the eigenvector relation that makes phase kickback work.

5. Write the phase kickback identity, and state what happens to the scratch qubit.

6. You verify a phase oracle and find the amplitude ratios are $+1, +1, +1, -0.87$. Is the oracle correct? What would the value $-0.87$ indicate?

7. Why are quantum algorithms "about phases"? Answer in terms of what interferes.

8. What is the relationship between phase kickback and quantum phase estimation?

9. Computing into an ancilla leaves the input register with entropy 0.8113. What does a nonzero entropy mean physically, and what does it prevent?

10. On a noiseless simulator, a circuit whose two H layers should cancel gives $P(00) = 1.0$ with uncomputation and $0.62$ without. Why is this result particularly dangerous to diagnose?

11. Give the one-line check that distinguishes a dirty ancilla from decoherence.

12. An MCXGate on 3 controls transpiles to zero T gates. Is this good news? Explain.

13. At a fixed T count of 16, going from 0 to 100 arbitrary rotations changes the physical qubit requirement from 65,636 to 4,558,356. Why does the estimator treat rotations separately from T gates?

14. State the honest Clifford+T cost of an 8-input multi-controlled X, and relate it to Chapter 15's finding about T gates.

15. Give the T counts for an 8-input MCXGate with and without ancillas, and the number of extra qubits required.

16. Explain the V-chain mechanism, and why it makes the cost linear in $n$.

17. mcx(mode="v-chain") is deprecated. What is the replacement, and why is it arguably better advice than the thing it replaced?

18. A circuit is declared with exactly $n+1$ qubits for an $n$-controlled gate. What does this cost, and why does nothing warn you?

19. State the three gaps between "one oracle query" and "one operation."

20. A team proposes Grover for a 20-bit search: $10^6$ classical checks versus $10^3$ quantum queries. What is wrong with that comparison, and what three numbers should they measure first?

Answers

1. Because $f$ is generally not injective — it discards information — while quantum operations must be unitary and therefore reversible. The construction keeps the input and XORs the answer into a scratch register: $U_f|x\rangle|y\rangle = |x\rangle|y \oplus f(x)\rangle$. It is reversible because XOR is its own inverse, so $U_f^2 = I$.

2. A multi-controlled X fires only when every control is 1, so you flip the bits that should be 0, apply it, and flip them back. Omitting the second layer leaves the input register in a permuted basis state, so the oracle marks a different state — with no error and no warning, and the algorithm returns a confident wrong answer.

3. Into the scratch register — the marked term moved to a basis state with the scratch at 1 (index 7). It is useless because measuring the scratch collapses the superposition and yields one random $x$ with its $f(x)$, which is no better than evaluating $f$ classically on a random input. Information in a separate register does not interfere.

4. $X|-\rangle = -|-\rangle$ — the state $|-\rangle = (|0\rangle - |1\rangle)/\sqrt2$ is an eigenvector of $X$ with eigenvalue $-1$.

5. $U_f\left(|x\rangle|-\rangle\right) = (-1)^{f(x)}|x\rangle|-\rangle$. The scratch qubit is left unchanged — unentangled, and available to discard or reuse.

6. No, it is wrong. The signs must be exactly $\pm1$. A magnitude below 1 means the input register is entangled with something — almost certainly a scratch or ancilla qubit that was not returned to $|0\rangle$ — so the "amplitude ratio" is really a partial trace artifact.

7. Because amplitudes interfere and register contents do not. Computing $f$ into a separate register puts the answer somewhere it cannot contribute to interference. Kickback moves it into the phase of the input register's amplitudes, where the interference that produces a quantum speedup can actually happen.

8. Phase kickback is phase estimation with one bit of precision. In both, a register in an eigenstate of some operator causes the eigenvalue to appear as a phase on the control register rather than changing the eigenstate. Kickback uses eigenvalue $-1$; phase estimation (Chapter 22) extracts a general $e^{2\pi i\phi}$ across many control qubits.

9. It means the input register is entangled with the ancilla, so on its own it is a mixed state rather than a pure one. A mixed state does not interfere — it is Chapter 4's classical impostor, arriving from bookkeeping rather than noise — which destroys the mechanism every quantum algorithm depends on.

10. Because the symptoms — washed-out contrast, reduced fidelity, degradation with size — are exactly the symptoms of decoherence, so it will be diagnosed as noise. And it is not: the measurement above was taken on a simulator with no noise in it at all.

11. Does it fail in noiseless simulation too? (Chapter 12 §12.7 step 2.) A dirty ancilla fails identically with all noise removed; decoherence does not.

12. No — it means the measurement is meaningless. The transpiler's basis included rz, so the synthesizer emitted general rotations instead of T gates. Rotations are not free: under error correction each must itself be synthesized into Clifford+T at a precision-dependent cost. Exclude rz from the basis and the same gate costs 1,905 T gates.

13. Because an arbitrary rotation is not a primitive under error correction — it must be approximated by a sequence of Clifford and T gates, and the length of that sequence depends on the precision you demand. A tCount is a count of gates you already have; a rotationCount is a promise of synthesis work still to be done, and at 100 rotations that work costs 69× more physical qubits than the T gates themselves.

14. 26,978 T gates, at depth 43,413, with 264 CX. Chapter 15 §15.8 measured that a single T gate takes a fault-tolerant machine from 450 to 2,882 physical qubits, and that ten T gates put 98.6% of the machine into magic-state factories — so an oracle at this cost is not a detail of the resource analysis, it is essentially all of it.

15. 26,978 T gates without ancillas; 55 with six of them — a 491× reduction, plus a 6.3× reduction in CX count (264 → 42).

16. Instead of synthesizing one enormous $n$-controlled gate, accumulate the conjunction through a cascade: $a_1 = x_1 \wedge x_2$, $a_2 = a_1 \wedge x_3$, and so on. That is $n-1$ Toffolis to compute, one controlled operation, and $n-1$ to uncompute — at 7 T gates per Toffoli, the total is linear in $n$. Without ancillas there is nowhere to store partial products, so they are repeatedly recomputed.

17. Add a plain MCXGate and give the circuit spare qubits; HighLevelSynthesis finds the cheap decomposition automatically. It is better advice because it describes the actual requirement — the transpiler needs somewhere to put ancillas — rather than naming one specific synthesis. A 6-control gate in a 7-qubit circuit costs 12,002 T gates; in a 12-qubit circuit, 39.

18. It costs up to 491× the T count, because there is no room for ancillas and the synthesizer must use a construction that repeatedly recomputes partial products. Nothing warns you because the circuit is valid, the transpilation succeeds, the answer is correct, and on a simulator the two versions are indistinguishable. The difference only appears under error correction, where T gates are the currency.

19. (a) The oracle is not free — thousands of T gates per call, and T gates are the dominant fault-tolerant cost. (b) The oracle must exist as a reversible circuit: early exits, lookup tables, and short-circuit evaluation do not survive reversibility, and for "database search" the data must be in the circuit rather than in a database. (c) The classical lower bound is over query-only algorithms, and real classical algorithms inspect structure, prune, and index.

20. The comparison uses different units — a classical operation (one microsecond of real CPU) against a quantum query (thousands of fault-tolerant T gates). The meaningful ratio is $\frac{10^6 \times \text{cost per classical check}}{10^3 \times \text{cost per oracle call}}$. Three numbers to measure first: the Clifford+T cost of one oracle call (with rz excluded); that total fed through Chapter 15's resource estimator; and the wall-clock time of the classical solver they would actually run, not the theoretical brute-force bound.