Reversible Computation and the No-Cloning Theorem
Stub. Reversible (bijective) classical computation as the prerequisite for quantum computation (every quantum gate is reversible, since unitaries are invertible); and the no-cloning theorem — no quantum operation can copy an arbitrary unknown quantum state — the single fact that makes quantum cryptography possible and quantum error correction hard.
Corresponds to Chapters 1 and 3.2.6 of this course. Reversible computation is the classical warm-up: since every quantum gate is a unitary (hence invertible) operator (unitary-dynamics-and-quantum-circuits covers unitary dynamics in full), any classical computation embedded into a quantum circuit must first be made reversible (e.g. via Toffoli gates, covered later in this topic). The basic quantum mechanics this course needs beyond that — quantum states, measurement, unitary evolution, multi-qubit systems and entanglement — is covered in depth by postulates-of-quantum-mechanics-and-the-qubit and composite-quantum-systems-and-entanglement, so it isn’t repeated here. What is new, and is the hinge the rest of this course’s cryptography hangs on, is the no-cloning theorem: linearity of quantum mechanics forbids any unitary (or more general physical) operation from producing two independent copies of an arbitrary unknown state. No-cloning is exactly why eavesdropping on a quantum channel is detectable (an eavesdropper can’t copy the qubit to analyze it risk-free) and exactly why quantum error correction can’t simply duplicate information the way classical error correction does.
Outline (TODO — flesh out each)
- Reversible computation
- The no-cloning theorem — statement and proof
- Why no-cloning underlies quantum cryptography