PU-404 · Quantum Information & Computation
The unit builds from the physical postulates of quantum mechanics to the claim that information is physical: qubits, entanglement, and channels are developed rigorously, then turned into protocols (teleportation, key distribution) and algorithms (Deutsch-Jozsa, Grover, Shor) whose power is proven, not asserted. It closes by bounding what quantum systems can and cannot do — Holevo's limit on communication, Landauer's cost of erasure, and the stabilizer machinery that makes fault-tolerant computation possible against decoherence.
Lectures
| L01 | What Is Quantum Information? — |
| L02 | Qubits, the Bloch Sphere, and Density Operators |
| L03 | Composite Systems, Tensor Products, and Entanglement |
| L04 | The No-Cloning Theorem |
| L05 | Schmidt Decomposition and Quantifying Entanglement |
| L06 | Mixed States, Ensembles, and Purification |
| L07 | Open Systems and Quantum Channels |
| L08 | EPR, Hidden Variables, and the CHSH Inequality |
| L09 | The Tsirelson Bound and Quantum Nonlocality |
| L10 | Quantum Teleportation |
| L11 | Superdense Coding |
| L12 | Quantum Key Distribution and BB84 |
| L13 | The Circuit Model and Universal Gate Sets |
| L14 | Gate Compilation and the Solovay-Kitaev Theorem |
| L15 | Quantum Parallelism and Deutsch-Jozsa |
| L16 | Grover's Search Algorithm |
| L17 | Optimality and Query Lower Bounds |
| L18 | The Quantum Fourier Transform |
| L19 | Phase Estimation |
| L20 | Shor's Algorithm: Order Finding and Factoring |
| L21 | Shannon and Von Neumann Entropy |
| L22 | The Holevo Bound and Accessible Information |
| L23 | Landauer's Principle and the Thermodynamics of Computation |
| L24 | Decoherence and the Case for Error Correction |
| L25 | Stabilizer Formalism and Error Discretization |
| L26 | Fault Tolerance and the Threshold Theorem |
| L27 | Physical Platforms for Qubits — |
| L28 | Outlook: Complexity, Advantage, and Open Problems |
Derivations homed in this unit
The No-Cloning Theorem
No unitary process can copy an arbitrary unknown quantum state, proven from linearity of evolution and preservation of inner products.
Reduced States and the Partial Trace
The partial trace is the unique map reproducing all local measurement statistics of a subsystem of an entangled state.
Schmidt Decomposition of Bipartite States
Any bipartite pure state reduces via the SVD to a single sum over orthonormal local bases, defining the Schmidt rank as an entanglement measure.
Quantum Channels: Kraus and Stinespring
Every completely positive trace-preserving map admits an operator-sum (Kraus) form, equivalent to a unitary acting on a dilated environment.
CHSH Inequality and the Tsirelson Bound
Local hidden-variable theories obey |CHSH| <= 2, while quantum correlations reach exactly 2*sqrt(2) and no higher.
Quantum Teleportation
An unknown qubit is transferred using one shared Bell pair and two classical bits, in a way fully consistent with no-cloning.
Superdense Coding
Two classical bits are transmitted by sending a single qubit from a pre-shared Bell pair, dual to teleportation.
Universality of CNOT with Single-Qubit Gates
CNOT together with arbitrary single-qubit rotations can implement any n-qubit unitary exactly.
The Solovay-Kitaev Theorem
Any finite universal gate set approximates an arbitrary single-qubit unitary to accuracy epsilon using only polylog(1/epsilon) gates.
Deutsch-Jozsa Oracle Separation
A single quantum query distinguishes constant from balanced functions with certainty, which classical deterministic querying cannot do sub-exponentially.
Grover Search and Its Optimality
Amplitude amplification finds a marked item among N in Theta(sqrt(N)) queries, and this query complexity is provably optimal.
The Quantum Fourier Transform Circuit
The discrete Fourier transform on n qubits is realised with O(n^2) Hadamard and controlled-phase gates.
Quantum Phase Estimation
The eigenphase of a unitary is estimated to n bits of precision using controlled powers of U followed by the inverse QFT.
Shor's Algorithm: Order Finding and Factoring
Integer factoring reduces to modular order-finding, solved efficiently by phase estimation and classical continued-fraction recovery.
Von Neumann Entropy and Subadditivity
The von Neumann entropy reduces to Shannon entropy for diagonal states and obeys concavity, subadditivity, and the Araki-Lieb bound.
The Holevo Bound
The classical information accessible from a quantum ensemble is bounded above by the Holevo chi quantity, limiting qubit communication capacity.
Landauer's Erasure Principle
Erasing one bit of information dissipates at least kT ln 2 of heat, tying logical irreversibility to the second law.
Stabilizer Codes and Error Discretization
Stabilizer measurement projects continuous errors onto a discrete Pauli set enabling correction, while the Gottesman-Knill theorem makes such circuits classically simulable.