Quantum Complexity Theory

Aims

The course aims to provide an introduction to Quantum Complexity Theory. Its main aims are to:

1. Develop a rigorous understanding of complexity classes in quantum computing.
2. Explore the fundamental separations and relationships between classical and quantum complexity classes.
3. Analyse key quantum algorithms and protocols from a complexity-theoretic perspective.
4. Investigate the role of quantum complexity in cryptography, interactive proofs, and quantum supremacy.
5. Provide exposure to open problems and recent advances in quantum complexity theory.
6. Prepare the students to conduct research in quantum complexity theory.

Syllabus

1. Quantum Computing Basics

• The postulates of quantum mechanics
• Quantum circuits
•  Basic quantum algorithms: Deutsch-Jozsa, Grover, and Simon’s algorithms

2. Quantum Complexity Classes

• BQP (Bounded-error Quantum Polynomial time)
• QMA (Quantum Merlin-Arthur) 
• The local Hamiltonian problem
• Relationship between BQP, P, NP, and PSPACE

3. Quantum Learning Theory

• Tomography
• Shadow tomography
• Quantum PAC learning

4. Interactive Proofs and Quantum Verification

•  Quantum interactive proofs (QIP = PSPACE)
•  Multi-prover quantum interactive proofs (MIP*, Tsirelson’s problem, and the recent breakthrough that MIP* = RE)
•  Non-local proofs and the power of nonlocality

5. Quantum Cryptography and Complexity

• Quantum zero-knowledge proofs
• ost-quantum vs. quantum cryptographic complexity
• Quantum pseudorandom states

6. Topics

• Quantum supremacy
• Quantum state and unitary synthesis
• State complexity, AdS/CFT, and quantum gravity

8. Open Problems and Research Directions

• Quantum circuit lower bounds
• Quantum locally testable codes
• The Quantum PCP conjecture

Objectives

By the end of the course, students will be able to:

1.  Classify problems within the framework of quantum complexity classes.
2.  Understand and explain fundamental separations between classical and quantum models.
3.  Analyse quantum algorithms from a complexity-theoretic perspective.
4.  Critically evaluate recent results in quantum complexity.
5.  Identify and discuss open problems and conduct research in quantum complexity theory.

Assessment

• Project (80%)
• Presentation (20%)

Timelines for the assignment submissions: 

• deliver talks in Weeks 5-8
• submit their project at the end of term

Recommended reading material and resources

“Quantum Computing Since Democritus” by Scott Aaronson

“Introduction to Quantum Information Science” by Scott Aaronson

“Quantum Computing: Lecture Notes” by Ronald de Wolf

“Quantum Computation and Quantum Information” by Nielsen and Chuang