Quantum Complexity Theory

CSE 291 / Math 277A - Fall 2024

Place and Time: | WLH 2207, TTh 3:30pm-4:50pm |

Instructor: | Daniel Grier (dgrier@ucsd.edu) |

TA: | Shinjini Halder (shhalder@ucsd.edu) |

Resources: | Canvas, Gradescope, Piazza |

Daniel's office hours: | Thursday after class and by appointment in CSE 4218 |

Shinjini's office hours: | Wednesday from 12pm-1pm in CSE B240A |

- Homework 1 - due October 8th at 3:00pm
- Homework 2 - due October 17th at 3:00pm
- Homework 3 - due October 24th at 3:00pm
- Homework 4 - due October 31st at 3:00pm
- Homework 5 - due November 7th at 3:00pm

These lecture notes are intended to be a comprehensive reflection of the course material. They will be updated throughout the quarter (last updated: 10/31/24). When possible, I have also included links below to other resources for specific topics.

Lecture 1 | Foundations of quantum mechanics | pg 1-5 |

Lecture 2 | Tensor products, partial measurements, Dirac notation | pg 1-8, pg 6-8 |

Lecture 3 | Quantum circuits | pg 2-5 |

Lecture 4 | The complexity class BQP | pg 1-4 |

Lecture 5 | BQP vs. PSPACE, query algorithms | pg 5-6, pg 3-6 |

Lecture 6 | Deutsch-Jozsa, Berstein-Vazirani, and Simon's Problem | pg 3-6, pg 1-5 |

Lecture 7 | Grover's algorithm and the BBBV lower bound | pg 1-6, pg 1-5 |

Lecture 8 | The polynomial method | pg 90-94 |

Lecture 9 | Clifford gates, Gottesman-Knill theorem | pg 48-55 |

This is a graduate-level course that will use tools from complexity theory to understand the fundamental differences between quantum and classical computers. After an introduction to the basics of quantum computation, the course will explore several settings in which quantum computers provably outperform their classical counterparts. This will take us to the forefront of quantum computing research, where we'll look at the complexity-theoretic foundations of recent quantum computing experiments.

**Prerequisites:** A previous course in complexity theory (CSE 200 or equivalent) is highly recommended. No prerequisite knowledge of physics or quantum computation is required. That said, this is an advanced research-level course and is not intended as an introduction to quantum computation and information.

- Quantum foundations: states, operations, measurements
- Quantum algorithms: Deutsch-Jozsa, Simon, Grover
- Lower bounds from query complexity: polynomial method, adversary method
- Classical vs. quantum complexity classes: P vs. BQP, NP vs. QMA
- Quantum satisfiability and the local Hamiltonian problem
- Classical simulation: Clifford circuits, tensor networks
- Near-term computational advantage: Shallow circuits, BosonSampling

**Homework (55%):**There will be 5-6 homework assignments throughout the course.**Project (20%):**The project consists of a written report/survey of a topic related to quantum complexity theory. Attempts at novel research are encouraged but not required.**Peer Grading (15%):**Each student will be required to help grade at least one homework assignment during the quarter.**Participation (10%):**Participation is based entirely on Gradescope quizzes given during class. The quizzes are graded for completion rather than correctness. There will be roughly 1 quiz per week, and you are allowed to miss 3 quizzes without penalty.

- Complexity Zoo Largest unified collection of complexity classes and their relationships
- SciRate Popular voting for recent quantum papers on the arXiv
- Quantum Computation and Quantum Information The canonical introductory textbook on the foundations of quantum information theory
- Ronald de Wolf's Quantum Computing Lecture Notes Published freely on the web
- Quantikz LaTex package for drawing quantum circuits