CS286 Seminar in Computer Science

Around the quantum PCP conjecture

Term: Fall 2014
Lectures: TTh 1-2:25, 314 Annenberg
Instructor: Thomas Vidick
Office hours: Monday 2-3pm, 207 Annenberg

Jump to:

Course description

The PCP theorem is a major development in classical complexity theory from the 90s. The theorem asserts that any statement that has an efficiently verifable proof (i.e. any language in NP) also has a proof that can be verified, with high probability, by reading only a constant number of bits. The theorem has many applications to the study of interactive proof systems and hardness of approximation of constraint satisfaction problems such as 3SAT.
A quantum analogue of the PCP theorem was conjectured over a decade ago. The quantum PCP is a conjecture about the hardness of the local Hamiltonian problem, a complete problem for the complexity class QMA, the quantum analogue of NP, that was originally introduced by Prof. Kitaev. The quantum PCP conjecture asks whether there is always a witness for the ground state energy that can be verified locally, by only accessing a constant number of qubits.
Precious little is known about the conjecture. In this class we will use it as motivation for exploring some advanced topics in quantum information theory and complexity theory that are loosely connected to the conjecture. Sample topics include:

Course outline


Even though the class will cover advanced topics of current research, I will try to keep it as self-contained as possible. The required background is a good grasp of linear algebra and probability theory and some basics of information theory. In addition, you should have taken advanced classes either in algorithms and complexity theory (such as CS 150 or CS 151) or in quantum information (such as Phys/CS 219), but it is not necessary to be familiar with both: students with no background in quantum information, but a strong background in complexity theory, or vice versa, are welcome. Talk to the instructor if you're unsure whether you have the requisite background.

Evaluation and workload

Course evaluation will mostly be through attendance and participation. After the first four weeks of class I will issue two research challenges, and students will be expected to write, in small groups, a short paper indicating research on one of the challenges (this can range from reading a paper related to a challenge to actually presenting a solution!).
The course will be relatively fast-paced and the first few weeks may involve a fair amount of reading for those less familiar with sme of the topics we will cover. Students with no prior exposure to quantum information will be expected to spend time hugging the book by Nielsen and Chuang; those with no background in complexity theory may do the same with the book by Arora and Barak.



You may find the following resources, almost all available online, helpful: