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
- Θ(1/ε) queries in place of Θ(1/ε²) samples
- three questions: task randomness, precision, oracle cost
- Grover on a database loses to data loading
- break-even: t_oracle < t_roll / (C·P·g)
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: Ω(k/ε²) samples vs Õ(√k/ε) 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, swap
- 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 bill 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 bill
- 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
Price 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
- log n and √n 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 2q(1 − γ)n
- 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 1/g² 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