Quantum Complexity Theory

CSE 291 / Math 277A

Place and Time: | CSE 4140, TTh 3:30pm-4:50pm |

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

TA: | Sihan Liu (sil046@ucsd.edu) |

Course materials: | Canvas |

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

Sihan's office hours: | Tuesday from 2pm-3pm in CSE 4232 |

Lecture 1 | Quantum basics: probability theory vs. quantum theory, unitary matrices, and quantum states | scribe notes |

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

**Project (55%):**The majority of the course grade will come from the final research project, which consists of a written report and a presentation. The project will be an in-depth study of a topic related to quantum complexity theory.**Homework (20%):**There will be 2-3 homework assignments throughout the course.**Scribing (15%):**You will be asked to scribe one lecture by carefully writing notes during class and TeX'ing up the final results. A template will be provided for this.**Participation (10%):**Students should actively engage with the material in class and/or office hours.

- 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