Exercises: Quantum Oracles

All of these run on a simulator. Solutions to starred exercises are in Answers to Selected Exercises.

Warm-up

19.1 ★ Build a bit oracle for $f(x) = 1$ iff $x = 5$ on three input qubits. Apply it to $|101\rangle|0\rangle$ and to $|011\rangle|0\rangle$ and confirm only the first flips the scratch qubit.

19.2 Apply the same oracle to a uniform superposition with the scratch in $|0\rangle$ and print the state vector. Identify which amplitude moved and explain why the result is useless as it stands.

19.3 ★ Repeat with the scratch qubit in $|-\rangle$. Report the input-register amplitudes and confirm exactly one has a minus sign.

19.4 ★ Verify the kickback identity directly: for each of the eight basis inputs, compute the ratio of the amplitude after the oracle to the amplitude before. Confirm every value is exactly $+1$ or exactly $-1$.

19.5 Build a deliberately broken oracle that omits the second X layer. Show that it marks a different state, and identify which one, without running it.

Phase kickback

19.6 ★ Show algebraically that $X|-\rangle = -|-\rangle$, then verify numerically with Operator(XGate()) applied to the $|-\rangle$ state vector.

19.7 ★★ Prepare the scratch qubit in $|+\rangle$ instead of $|-\rangle$. What happens to the kickback, and why? What does this tell you about which eigenvector you need?

19.8 ★★ Build a phase oracle marking two states out of eight, and confirm exactly two amplitudes carry a minus sign.

19.9 ★★ Build a phase oracle marking all states. What circuit does it reduce to, and what does that tell you about oracles that mark too much?

19.10 ★★★ Phase kickback with an $n$-qubit scratch register in an eigenstate of some unitary $U$ kicks back $e^{2\pi i\phi}$ rather than $\pm1$. Implement the one-qubit version for $U = \text{Phase}(\theta)$ and confirm the control register picks up $e^{i\theta}$. Relate your construction to Chapter 22's phase estimation.

Uncomputation

19.11 ★ Reproduce §19.4's entropy measurement: compute into an ancilla, report the input register's entropy, uncompute, report it again.

19.12 ★ Reproduce the interference measurement: a circuit whose two H layers should cancel, run with and without uncomputation, on a noiseless simulator. Report $P(00)$ for each.

19.13 ★★ Write ancillas_are_clean(circuit, ancilla_qubits) returning a boolean. Test it on a correctly uncomputed circuit and a dirty one. What tolerance is appropriate?

19.14 ★★ Build a two-level oracle: compute an intermediate result into ancilla A, use it to compute into ancilla B, apply the phase, then uncompute both. Verify the input register's entropy returns to zero, and confirm the uncomputation order matters.

19.15 ★★★ A dirty ancilla and genuine decoherence produce similar symptoms. Design an experiment that distinguishes them using only measurements you could take on hardware — that is, without access to the state vector. (Hint: Chapter 12 §12.7's procedure, and Chapter 11 §11.7's two axes.)

What it costs

19.16 ★ Transpile an MCXGate on 2, 4, 6, and 8 controls into a basis including rz, then into one excluding it. Present both T counts side by side and explain the discrepancy.

19.17 ★★ Reproduce §19.5's rotation-cost measurement: hold tCount fixed at 16 and vary rotationCount over 0, 10, and 100 in Chapter 15's estimator. Report the physical qubit counts.

19.18 ★★ Write oracle_cost(circuit) that returns the Clifford+T cost and refuses to report a trustworthy number when rotations remain. Test it against both bases.

19.19 ★★ Reproduce §19.6's ancilla comparison for $n = 4, 6, 8, 10$. Report the T-count reduction and the extra qubits required at each size. At which $n$ is the trade most favourable?

19.20 ★★ Verify the linear-scaling claim: fit the v-chain T counts against $14(n-1)$ and report the residuals. Where does the model break down?

19.21 ★★ Show that the reduction is available without calling any deprecated API: build the same MCXGate in a circuit with $n+1$ qubits and in one with $2n$, transpile both, and compare.

19.22 ★★★ Compare synth_mcx_n_clean_m15 and synth_mcx_n_dirty_i15 at $n = 4, 6, 8$. Report the T-count difference and explain what "dirty" buys you. When would you accept the higher cost?

Query complexity, honestly

19.23 ★★ Case Study 1 prices a 20-bit Grover search. Redo the calculation for 30 and 40 bits. At what problem size does the quantum approach become competitive against a one-microsecond classical check, assuming 3,000 T gates per oracle call?

19.24 ★★ Take a small classical predicate written normally — with an early return and a lookup table — and write out what its reversible implementation would need. Count the ancillas.

19.25 ★★★ The $\Omega(N)$ classical lower bound assumes query-only access. Construct a concrete predicate over 16 bits for which a structure-exploiting classical algorithm beats $\sqrt N$ quantum queries, and quantify the margin.

Project

19.26 ★★ (Project Checkpoint) Build vqelab/oracles.py with marked_states, bit_oracle, phase_oracle, phase_signs, scratch_is_clean, input_register_entropy, oracle_cost, and compare_ancilla_strategies. Write tests asserting:

  1. marked_states enumerates the predicate correctly.
  2. An empty predicate raises rather than returning the identity.
  3. A phase oracle applies exactly $-1$ to marked states and exactly $+1$ elsewhere.
  4. Multiple marked states all receive $-1$.
  5. Every sign has magnitude exactly 1 (a partial phase means the oracle is wrong).
  6. The phase oracle leaves the scratch qubit clean.
  7. A dirty ancilla leaves the input register with entropy above 0.5, and uncomputation returns it to 0.
  8. A Clifford+T cost measurement is reported as trustworthy.
  9. A cost measured with rotations allowed is flagged UNTRUSTWORTHY.
  10. The honest T count exceeds the naive one by more than 50×.
  11. Ancillas reduce the T count by more than 10× at $n = 6$.
  12. The ancilla advantage grows with $n$.

Tests 9 and 11 encode this chapter's two case studies.

19.27 ★★★ Extend oracles.py with oracle_from_cnf(clauses), building an oracle from a conjunctive-normal-form formula. Each clause needs its own ancilla; the final AND needs one more. Verify against a brute-force classical evaluation for random 4-variable formulas, and report the T count as a function of clause count.

Going further

19.28 ★★★ Grover's algorithm (Chapter 21) uses a phase oracle plus a diffuser. The diffuser is itself a phase oracle — marking $|0\dots0\rangle$ — wrapped in Hadamards. Build it using this chapter's phase_oracle and verify it implements the reflection $2|s\rangle\langle s| - I$.

19.29 ★★★ The oracles here mark states by enumeration, which is exponential in $n$ to construct. Explain why this is acceptable for testing and unacceptable for a real algorithm, and describe what a real oracle does instead.