Quantum Computing
A comprehensive university-level course on quantum computing -- from the physics of qubits through fault-tolerant algorithms and near-term applications on real hardware.
Course Overview
Quantum computing harnesses the principles of quantum mechanics -- superposition, entanglement, and interference -- to process information in fundamentally new ways. This course provides a rigorous treatment of the field, spanning foundational theory, practical algorithms, error correction, hardware implementations, and cutting-edge variational methods.
What You Will Learn
- - Qubits, quantum gates, and the circuit model
- - Landmark algorithms: Grover, Shor, HHL
- - Quantum error correction and fault tolerance
- - Hardware: superconducting, trapped-ion, photonic, topological
- - Variational quantum eigensolver (VQE) and QAOA
- - Applications in chemistry, optimization, ML, and cryptography
Prerequisites
- - Linear algebra (vectors, matrices, eigenvalues, tensor products)
- - Complex numbers and probability
- - Basic quantum mechanics (helpful but not required)
- - Python programming for Qiskit examples
- - Familiarity with algorithms and complexity theory (helpful)
76+ pages | 6 major parts | Qiskit code examples | Key equations and derivations
Why Quantum Computing?
Classical computers encode information in bits that are either 0 or 1. A quantum computer uses qubits that can exist in superpositions of both states simultaneously:
$$|\psi\rangle = \alpha|0\rangle + \beta|1\rangle, \quad |\alpha|^2 + |\beta|^2 = 1$$
This, combined with entanglement and quantum interference, enables algorithms that are exponentially faster than any known classical algorithm for certain problems. Shor's algorithm factors large integers in polynomial time, threatening RSA encryption. Grover's algorithm provides a quadratic speedup for unstructured search. Variational algorithms already run on today's noisy quantum hardware.
Exponential
Speedup for factoring (Shor)
Quadratic
Speedup for search (Grover)
NISQ Era
Variational algorithms on real hardware
Course Structure
Part I: Qubits and Quantum Gates
The qubit as the fundamental unit of quantum information. The Bloch sphere representation, single-qubit gates (Pauli X, Y, Z, Hadamard, phase, T), multi-qubit gates (CNOT, Toffoli, SWAP), and the quantum circuit model. Universal gate sets and circuit identities.
Part II: Quantum Algorithms
From the Deutsch-Jozsa problem to Shor's factoring algorithm. Grover's search with amplitude amplification, quantum phase estimation, the quantum Fourier transform, and the HHL algorithm for solving linear systems.
Part III: Quantum Error Correction
Why quantum errors are different from classical errors. Bit-flip and phase-flip codes, the Shor 9-qubit code, the Steane [[7,1,3]] code, CSS codes, stabilizer formalism, surface codes, and the fault-tolerance threshold theorem.
Part IV: Hardware Platforms
Physical implementations of qubits. Superconducting circuits (transmon qubits), trapped-ion systems (Yb+, Ca+, Ba+), photonic quantum computing, and topological qubits (Majorana fermions). Decoherence times, gate fidelities, and scalability challenges.
Part V: Variational Algorithms
The hybrid quantum-classical paradigm. Variational Quantum Eigensolver (VQE), Quantum Approximate Optimization Algorithm (QAOA), parameterized quantum circuits, the parameter shift rule for gradient computation, and the barren plateau problem.
Part VI: Applications
Real-world applications of quantum computing. Quantum chemistry and molecular simulation, combinatorial optimization, quantum machine learning, and post-quantum cryptography. Current state of the art and future outlook.
Key Equations You Will Encounter
Qubit State
$$|\psi\rangle = \alpha|0\rangle + \beta|1\rangle = \cos\frac{\theta}{2}|0\rangle + e^{i\phi}\sin\frac{\theta}{2}|1\rangle$$
Grover's Speedup
$$\text{Classical: } O(N) \quad \longrightarrow \quad \text{Quantum: } O(\sqrt{N})$$
Shor's Algorithm Complexity
$$O\bigl((\log N)^2 (\log \log N)(\log \log \log N)\bigr)$$
Variational Energy
$$E(\vec{\theta}) = \langle\psi(\vec{\theta})|\hat{H}|\psi(\vec{\theta})\rangle \geq E_0$$
Fault-Tolerance Threshold
$$p_{\text{physical}} < p_{\text{th}} \approx 1\% \implies \text{arbitrarily long quantum computation}$$
Historical Milestones
Richard Feynman proposes using quantum systems to simulate quantum physics
David Deutsch introduces the concept of a universal quantum computer
Deutsch-Jozsa algorithm demonstrates exponential quantum advantage for an oracle problem
Peter Shor publishes polynomial-time quantum factoring algorithm
Shor introduces quantum error correction; Steane publishes the [[7,1,3]] code
Lov Grover publishes quadratic-speedup search algorithm
Fault-tolerance threshold theorem proved (Aharonov-Ben-Or, Kitaev, Knill-Laflamme-Zurek)
IBM and Stanford factor 15 using Shor's algorithm on 7 NMR qubits
Harrow, Hassidim, Lloyd (HHL) algorithm for linear systems
Peruzzo et al. demonstrate VQE on a photonic quantum processor
Google claims quantum supremacy with 53-qubit Sycamore processor
IBM demonstrates error-mitigated utility-scale quantum computation (127 qubits)
Google Willow achieves below-threshold error correction with 105 qubits
Classical vs Quantum Computational Models
Classical (Turing Machine)
- - Bits: $\{0, 1\}$
- - Deterministic or probabilistic
- - Gates: AND, OR, NOT, NAND
- - Complexity: P, NP, BPP
- - Factoring in $O(e^{n^{1/3}})$ (GNFS)
- - Search in $O(N)$
Quantum (Circuit Model)
- - Qubits: $\alpha|0\rangle + \beta|1\rangle$
- - Unitary evolution + measurement
- - Gates: H, CNOT, T, Toffoli
- - Complexity: BQP
- - Factoring in $O((\log N)^3)$ (Shor)
- - Search in $O(\sqrt{N})$ (Grover)
The central open question: Is BQP strictly larger than BPP? We believe so (factoring appears hard classically), but proving $\text{BPP} \neq \text{BQP}$ remains one of the great unsolved problems in computational complexity.
Begin Your Quantum Journey
Start with the fundamentals of qubits and gates, then progress through algorithms, error correction, hardware, variational methods, and real-world applications.