A Programmer’s Guide to Building the Right Oracle Most quantum speedup claims depend on an oracle that exists only on paper. This course teaches the craft of building practical quantum circuits from scratch.
Choose the problem, build the oracle
- A different computer
- CPU, GPU, QPU: three devices, three workloads
- the QPU’s job: fewer samples for an average
- three questions: task randomness, precision, oracle cost
- Grover on a database loses to data loading
- break-even:
- The Monte Carlo speedup
- a query count is not a runtime
- the payoff qubit’s angle encodes the win probability
- amplitude estimation reads that angle to precision ε
- best of k arms:
- Go fails question 1, the bandit fails question 3
- Sway: gaps of 10⁻⁴ on a 32×32 board
- the same oracle shape fits an epidemic model
- Ship it
- the contract: board, two moves, randomness tape, payoff qubit
- one round: Black places, White places, every stone rolls
- the register layout in Qiskit
- a uniform move choice over the legal cells
- the d20 as a 5-bit comparison against a neighbor count
- 3×3, two rounds: 169 qubits
- Reversible by design
- amplitude estimation runs the rollout forward and backward
- decide from the old board, write to a shadow board, keep the old one
- in-place updates read a neighbor that already flipped
- erase move-selection scratch before the board changes
- one payoff qubit, everything else inverted
- the qubit and gate count as the board grows
Make it correct 5. Garbage collection
- reversible circuits have no delete
- entangled scratch breaks interference
- Bennett: compute, copy out, uncompute
- the inverse must see the same inputs as the forward pass
- peak scratch sets the qubit count
- clean scratch is necessary, not sufficient
- Measure to erase
- the textbook says never measure mid-circuit
- compilers measure scratch to reclaim qubits
- Gidney’s AND†: an X-basis measurement instead of a Toffoli
- a random sign, fixed by one phase gate
- half the T gates of an...