Quantum Query Algorithms — Deutsch-Jozsa and Simon's Algorithm
Stub. The Toffoli/CCNOT gate and reversible circuits (including uncomputing, needed to clean up ancilla qubits without disturbing entanglement); the Deutsch-Jozsa algorithm, the first example of a quantum speedup, distinguishing constant from balanced Boolean functions in one query; and Simon's algorithm, which finds a function's hidden period using the Fourier transform over 𝔽₂ⁿ, the first example of an exponential quantum/classical query-complexity gap and the direct template for Shor's algorithm.
Corresponds to Chapters 4–6 (through Simon’s algorithm). The Toffoli (CCNOT) gate is the standard reversible building block for embedding classical logic into a quantum circuit, and uncomputing — running a computation’s reversible circuit backward on ancilla qubits once they’re no longer needed — is the technique for discarding intermediate results without accidentally leaving them entangled with (and hence disturbing) the main computation. The Deutsch-Jozsa algorithm is the canonical first quantum algorithm: given a function promised to be either constant or balanced, it determines which in a single query, versus exponentially many classical queries in the worst case — the query evaluated in superposition and then Fourier-analyzed (relating to boolean-fourier-analysis-and-complexity-measures) via a Hadamard transform. Simon’s algorithm solves a harder hidden-structure problem (find a function’s period over ) with an exponential query-complexity advantage over any classical algorithm, using exactly the same “query in superposition, then Fourier transform” template that Shor’s algorithm generalizes to period-finding over .
Outline (TODO — flesh out each)
- The Toffoli / CCNOT gate
- Reversible circuits; uncomputing
- The Deutsch-Jozsa algorithm
- Functions as quantum states; representing functions in the Fourier basis
- Simon’s algorithm
- Simon’s algorithm via the Fourier basis over