Quantum Computer Science (Stanford CS269Q - Lecture Notes)

Stanford’s graduate quantum computer science course, approached entirely from a computer science perspective. Slides and problem sets are freely available and cover the material with more rigour and less physics than most equivalents.

CS269Q treats quantum computing as a topic in theoretical computer science. The emphasis is on models of computation, provable complexity separations, and formal algorithm analysis. Learners who found other courses too physics-heavy or too informal about complexity claims will find this treatment more satisfying.

What you’ll learn

• The quantum circuit model from a computational perspective: gate sets, universality, and circuit complexity as a formal measure of quantum algorithmic cost
• The quantum query model: how to define oracle problems precisely and use the model to prove both upper and lower bounds on query complexity
• BQP and its relationship to classical complexity classes: what is currently known and unknown about BQP vs P, NP, and PSPACE, including oracle separations
• Deutsch-Jozsa, Simon, and Bernstein-Vazirani algorithms derived from first principles within the query model
• Grover’s algorithm: the full algorithm, the O(sqrt(N)) query complexity analysis, and the matching lower bound showing no quantum algorithm can do better
• The quantum Fourier transform, phase estimation, and Shor’s factoring algorithm with the number-theoretic reduction carefully stated
• Quantum error correction: stabiliser formalism, the quantum Hamming bound, CSS codes, and the basics of fault-tolerant computation
• Topological codes: a conceptual introduction to the surface code and why topological approaches to error correction are practically attractive

Course structure

Materials consist of lecture slides and problem sets. There are no video recordings publicly available. The slides are detailed enough to function as lecture notes and are more information-dense than most slide decks.

The course follows a logical progression from computational models through algorithms and into error correction. The CS framing is consistent throughout: everything is stated in terms of circuits, complexity classes, and formal computational problems rather than physical Hamiltonians or experimental implementations.

Problem sets require both mathematical proofs and circuit constructions. Working through them is the primary way to build genuine understanding from the slide materials.

Who is this for?

• Computer science graduate students who want a theoretically rigorous treatment of quantum algorithms without heavy quantum physics prerequisites
• Researchers in classical algorithms or complexity theory exploring quantum computing
• Learners who have found other advanced courses too informal about complexity claims
• Anyone who wants to read quantum complexity theory papers and needs the formal background

Prerequisites

Graduate-level computer science background is expected. Computational complexity at the level of P, NP, polynomial reductions, and oracle separations should be familiar. Linear algebra including eigenvalues, tensor products, and unitary matrices is required. No prior quantum mechanics is assumed, though prior exposure to quantum computing concepts helps with pace.

Hands-on practice

This is a theory-focused course and the primary practice is mathematical:

• Prove query complexity bounds for specified oracle problems using the polynomial method or adversary arguments
• Construct quantum circuits for given computational tasks and analyse their complexity
• Verify algorithm correctness for small inputs by hand calculation
• Work through the complexity class inclusions and prove or disprove oracle separations
• Design stabiliser codes satisfying specified parameters and determine their error-correcting capability

The problem sets are challenging and representative of graduate qualifying exam level difficulty. Working solutions are not publicly posted, so peer discussion or an instructor is valuable for checking work.

Why take this course?

Stanford CS269Q provides something rare: a quantum computing course that treats complexity theory with the same care a theoretical computer science course would. The query model is used properly, BQP is defined correctly, and the limitations of what is known about quantum vs classical separation are stated honestly.

For learners who care about the theoretical foundations rather than immediate engineering application, this course gives the background needed to read and contribute to the quantum complexity and quantum algorithms research literature. Combined with Preskill’s Caltech notes for error correction depth, it forms a solid graduate-level self-study programme.