Basics of Quantum Information, Computation, and Cryptography

Corresponds to CS/ECE 598DA, Weeks 11–12. Covers just enough quantum mechanics to understand quantum cryptography: qubits as superpositions of classical bits (postulates-of-quantum-mechanics-and-the-qubit covers this in full generality via density matrices and the Bloch sphere), the unitary gates that manipulate them (unitary-dynamics-and-quantum-circuits), and the measurement postulate (quantum-measurement-and-steering) — crucially, that measuring a quantum state in the “wrong” basis irreversibly disturbs it, which is the physical principle quantum cryptography exploits rather than a complexity-theoretic hardness assumption the way public-key-cryptography-foundations‘s classical protocols do. Quantum key distribution (e.g. BB84-style protocols) is the main application: two parties exchange qubits, and any eavesdropper’s attempt to measure them in transit is detectable, because measurement disturbance shows up as an anomalously high error rate the parties can check for. See reversible-computation-and-the-no-cloning-theorem for the no-cloning theorem that makes this detectability possible at all, and quantum-key-distribution-security-proof for the full, rigorous security proof (indistinguishability, the adversarial sampling game, agreement/secrecy, error correction and privacy amplification) this note’s sketch defers to.

Outline (TODO — flesh out each)

• Qubits and superposition
• Quantum gates and circuits
• Quantum measurement
• Quantum key distribution (deep dive: quantum-key-distribution-security-proof)
• Other quantum cryptographic protocols (deep dive: the security/quantum-cryptography notes — oblivious transfer, LWE encryption, quantum money, and more)