I'm teaching an introductory 12 week course on Quantum Oracle Engineering

# Quantum Oracle Engineering Source: [https://shukla.io/quantum-oracle-engineering/](https://shukla.io/quantum-oracle-engineering/) 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 ## 1\. A different computer - **CPU, GPU, QPU**: three devices, three workloads - the QPU’s job:**fewer samples**for an average - ****queries in place of****samples - **three questions**: task randomness, precision, oracle cost - Grover on a database loses to**data loading** - break\-even:**** [View slides](https://shukla.io/quantum-oracle-engineering/a-different-computer/) ## 2\. 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:****samples vs****queries - **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** ## 3\. 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** ## 4\. 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** ## 6\. 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 adder - safe when scratch holds a**basis function**of the data ## 7\. Calling conventions - three scratch classes:**clean, borrowed, conditionally clean** - Qiskit passes the reuse condition as**unchecked convention** - a block can**destroy its own condition** - two correct blocks, one**unguaranteed boundary** - **restoration types**: Hoare contracts over subspaces - a 12\-bit oracle:**20 qubits to 13** ## 8\. Proof\-carrying circuits - truth tables**cannot see a phase** - full\-basis checking costs**2ⁿ** - certificates replayed by a**Lean kernel** - gate\-by\-gate checking needs**closure**under the gate set - past**Toffoli**, assertions grow exponentially - **one theorem per family**, checked in milliseconds Count it, test it, judge it ## 9\. Where the quantum lives - a process that runs**step by step** - between any two steps,**classical bits**would do - no one classical carrier works for**all steps at once**\(Bisio\) - the**SHIFTS channel**: one qubit in, two out, built to show it - the quantum lives in the**memory between steps** ## 10\. All or nothing - running n copies**does not amortize** - quantum memory:**zero or linear**in n, nothing between - **and**scalings ruled out - the same law for**preparing states** - SHIFTS: at least**0\.03 qubits per copy** - a**theorem**, with constants ## 11\. Test, don’t trust - a test with**single\-qubit measurements**only - a correct device passes**every time** - q qubits of memory pass with probability at most**** - too little memory fails**exponentially fast** - the device stays a**black box** ## 12\. Audit the next claim - the AI era’s assumption:**compute closes every gap** - the**wall**: tiny gaps, irreducible randomness - **weak baselines**, query counts sold as runtimes - **ignored parallelism**, solver randomness as task randomness - oracle cost hidden behind**“assume oracle access”** - the three questions on a**headline claim**, live