Quantum Complexity Theory

CSE 291 / Math 277A - Fall 2022

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 |

The scribe notes were initially prepared by students in the class, but were then modified by me. You can assume any errors are my own. Find an error? Feel free to let me know!

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

Lecture 2 | More quantum basics: No-cloning, mixed states, partial trace, and purification | scribe notes |

Lecture 3 | Quantum circuits, universality | scribe notes |

Lecture 4 | More quantum circuits, Nobel prizes, and the CHSH game | scribe notes |

Lecture 5 | Classical complexity classes, relationships, and BQP | scribe notes |

Lecture 6 | BQP vs. classical complexity classes and Deutsch's algorithm | scribe notes |

Lecture 7 | Quantum query algorithms continued: Deutsch-Jozsa, Berstein-Vazirani, and Simon's problem | scribe notes |

Lecture 8 | Maximal query separations and the forrelation problem | scribe notes |

Lecture 9 | Grover's algorithm and the BBBV lower bound | scribe notes |

Lecture 10 | More quantum query lower bounds: the polynomial method and Adversary bound | scribe notes |

Lecture 11 | Clifford circuits, the Pauli group, and the Gottesman-Knill Theorem | scribe notes |

Lecture 12 | Stabilizer groups continued, constant-depth circuit classes, and the GHZ game | scribe notes |

Lecture 13 | GHZ game continued, Bravyi-Gosset-König separation between constant-depth quantum and classical circuits | scribe notes |

Lecture 14 | NC/AC Hierarchy, hardness of simulating interactive protocols with low-depth Clifford circuits | 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