Discrete Mathematics
Foundations of Quantum Information Theory
How does information behave in the quantum world - and why does Shor's algorithm threaten the security of the entire internet?
- **Google Quantum AI:** Sycamore (53 qubits, 2019) - 200 seconds vs. 10,000 years on classical Summit
- **Quantum key distribution:** BB84 commercially deployed by Toshiba and ID Quantique
- **Quantum networks:** Micius satellite - quantum teleportation over 1200 km (2017), the foundation of the quantum internet
- **Threat to RSA:** Shor's algorithm factors RSA-2048 at 4000+ logical qubits - the driver of post-quantum cryptography
Предварительные знания
- Linear algebra over C (complex vector spaces)
- Unitary matrices and operators
- Shannon entropy
- Discrete Fourier transform
Qubits and Entanglement
In 2019 Google Sycamore performed in 200 seconds a computation that would take 10,000 years on the classical Summit supercomputer. The secret is superposition: 50 qubits encode 2^50 = 10^15 states simultaneously. A qubit is not just 'bit 0 or 1' but a unit vector in the Hilbert space C^2, and the linear structure unlocks exponential parallelism.
BB84 (Bennett-Brassard, 1984) is the first quantum key distribution protocol. Eavesdropping on the quantum channel inevitably introduces errors (no-cloning theorem) detectable by Alice and Bob. Toshiba and ID Quantique commercially deploy BB84 in banking cryptography.
What does '1 ebit' of entanglement mean for the Bell state |Phi+>?
Quantum Gates
A quantum gate is a unitary operator on n qubits. The analog of classical AND/OR/NOT, but reversible: U^dagger U = I. Every quantum computation is a sequence of gates and measurements. The universal set {H, T, CNOT} suffices to approximate any unitary operator to arbitrary precision - the analog of Post's completeness theorem.
Quantum teleportation (Bennett et al., 1993): transferring a qubit state using 1 ebit and 2 classical bits. Does not violate special relativity: the classical channel is required, bounded by the speed of light. In 2017 the Micius satellite demonstrated teleportation over 1200 km.
Why is {H, T, CNOT} a universal set of quantum gates?
Quantum Algorithms: Shor and Grover
In 1994 Peter Shor showed a quantum computer factors an n-bit number in O(n^3) instead of exp(n^{1/3}) classical operations. This threatens all RSA cryptography protecting banking and TLS. In 1996 Lov Grover gave a quadratic speedup for unstructured search: O(sqrt(N)) instead of O(N). These two algorithms demonstrate that quantum computers beat classical ones not by quantity but by quality.
Quantum information in mathematics and physics
Quantum information theory connects discrete mathematics, analysis, and fundamental physics.
- Coding theory — Quantum error-correcting codes (CSS codes) are built from pairs of classical linear codes over GF(2)
- Complexity theory — The class BQP contains factoring (Shor) and discrete log - outside BPP under standard assumptions
- Cryptography — Threat to RSA at 4000+ logical qubits; post-quantum cryptography (lattice-based, code-based) is the response
- Linear algebra over C — Quantum states are vectors in C^{2^n}; operations are unitary matrices; measurements are projectors
Итоги
- **Qubit:** |psi> = alpha|0> + beta|1> with |alpha|^2 + |beta|^2 = 1; a unit vector in C^2
- **Entanglement:** Bell states; S(rho_A) = 1 ebit - maximal for two qubits
- **No-cloning:** impossibility of copying an arbitrary |psi> - a consequence of linearity
- **Universal gates:** {H, T, CNOT} approximate any unitary operator (Solovay-Kitaev)
- **Superdense coding:** 1 ebit + 1 quantum channel = 2 classical bits
- **Shor's algorithm:** factorization in O(n^3); threat to RSA
- **Grover's algorithm:** search in N elements in O(sqrt(N)); quadratic speedup
What speedup does Grover's algorithm provide for unstructured search?