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:
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