CMPT 409/981: Quantum Circuits and Compilation

Quantum computers in the gate model operate by executing quantum circuits. This course aims to broadly explore the techniques, foundational to modern, through which a high-level quantum algorithm may be compiled down to a circuit which can then be run on quantum hardware. It will cover the basics of gate model quantum computation then delve into different aspects of the quantum compilation stack, including the design and synthesis of quantum circuits, optimization of circuits, theoretical questions of efficiency, and the simulation and verification of quantum circuits.

Updates

Course information

Instructor:   Matt Amy
Email:   matt_amy at sfu.ca
Office:   TASC1 9215
Office hours:   F 1:20-2:30 (after class)
Classes:   Tu 12:30-2:20 (AQ 5018)
F 12:30-1:20 (BLU 10011)
Textbook:   None (see additional resources below)

Link to collaborative class notes

Tentative schedule

Date Topic(s) Materials Readings/notes
Sept. 9 Introduction to course & QC Lecture 1
13 Linear algebra review, Dirac notation, postulates of QM Lecture 2 Optional reference: Section 2 of Josza's lecture notes
16 The circuit model of computation Lecture 3 Optional reference: Chapters 5.1 & 5.2 of Preskill's lecture notes (ignore classical circuit complexity)
20 Reversible circuits, Quantum circuits I Lecture 4 Optional reference: Chapter 4 of Nielsen & Chuang (Copyright Cambridge University Press)
23 Quantum circuits II Lecture 4 cont. Nielsen & Chuang Chapter 4.
Assignment 1 posted (Due Friday October 7th at the start of class on paper or by email)
Note: In question 3.3, the initial state should be read as $|\psi\rangle \otimes ((A\otimes I)|\Phi^+\rangle)$
27 Quantum circuits III Lecture 5 Reading: Barenco et al. Elementary gates for quantum computation
30 No class (Holiday)
Oct. 4 Universal gate sets Lecture 6
7 Quantum fault-tolerance and universality I Lecture 7
11 Quantum fault-tolerance and universality II Lecture 7 cont. Optional reference: Preskill's notes
14 Quantum fault-tolerance and universality III Lecture 8 Assignment 2 posted (Due Friday October 28th at the start of class on paper or by email)
18 Quantum fault-tolerance and resource usage Lecture 8 cont.
21 The Number-Theoretic Method I Lecture 9 Reading: Giles & Selinger, Exact synthesis of multiqubit Clifford+T circuits
25 The Number-Theoretic Method II Lecture 9 cont.
28 The Number-Theoretic Method III Lecture 9 cont. Optional reading: Kliuchnikov, Synthesis of unitaries with Clifford+T circuits
Nov. 1 Circuit optimization I - re-writing Lecture 10
4 Circuit optimization II - re-synthesis Lecture 11 Assignment 3 posted (Due Friday October 28th at the start of class on paper or by email)
8 Circuit optimization III - phase polynomial methods Lecture 12 Optional references: T-par, gray-synth
15 Circuit optimization IV - sum-over-paths and phase folding Lecture 13
18 Circuit optimization V - phase folding
22 (Jonas) Alexandre Clément et al. A Complete Equational Theory for Quantum Circuits. arXiv 2022.
(Lucas) Miriam Backens. The ZX-calculus is complete for stabilizer quantum mechanics. njp 2014.
25 (Ashish) M. Amy, Owen Bennett-Gibbs, Neil J. Ross. Symbolic synthesis of Clifford circuits and beyond. QPL 2022.
29 (Mehdi) Craig Gidney. Halving the cost of quantum addition. Quantum 2018.
(Luis) Madhav Krishnan Vijayan et al. Compilation of algorithm-specific graph states for quantum circuits. arXiv 2022.
Dec. 2 (Shishir) David Ittah et al. Enabling Dataflow Optimization for Quantum Programs. ACM TQC 2021.
6 (Ming) Adam Paetznick, Austin G. Fowler. Quantum circuit optimization by topological compaction in the surface code. arXiv 2013.
(Camille) Daniel Litinski. A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery. Quantum 2019.

Paper readings & discussion

The last 3 or so weeks of class will be devoted to paper discussion. Graduate students will briefly (~30 minutes) present a paper, and then we will discuss as a class. Graduate students should select a paper they would like to present and lead discussion for by November 4th. A list of possible papers are provided here

Project

See the project description here

Topics

Topics will be gauged in part by class interest, but generally speaking will fit into these broad categories

Prerequisites

The topics in this course involve a wide range of theoretical computer science and mathematical concepts. At minimum students should be comfortable with linear algebra (e.g. MATH 240) and algorithms and complexity (e.g. CMPT 307), but prior knowledge of quantum information, abstract algebra, and theoretical computer science will be an asset.

If you haven't seen quantum computation before and are wondering if the course will be accessible to you, read this crash course on quantum information. We will cover this material quickly in the first week or two.

Course goals

Given an instance of a quantum algorithm, understand the issues and costs involved with compiling it to either near-term or fault-tolerant hardware, and be able to compile it using modern techniques.

Evaluation

Additional resources

Unfortunately, there's no "Dragon book" for quantum compilers just yet. However, there are many resources available for learning quantum computation. Highly recommended if you're new to QC.