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

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:

The area law and correlations in ground states of gapped Hamiltonians. The area law bounds the strength of quantum correlations (as measured by the entanglement entropy) that can exist between two subsets of particles in the ground state of a local Hamiltonian having a spectral gap: it states that they should scale with the perimeter, or surface, of the region, rather than its volume. We will see a recent combinatorial proof of the area law in one dimension due to Arad et al.
de Finetti theorems are general results on the structure of n-partite distributions, such as distributions over n-bit strings or n-qubit states, that are invariant under any permutation of the n systems. We will study a recent de Finetti theorem by Brandao and Harrow, and its application to bounding entanglement in ground states of local Hamiltonians whose constraint graph has an expanding structure.
Interactive proofs with entangled provers. The original proof of the PCP theorem was discovered through the study of multiprover interactive proof systems. Allowing the isolated provers to share the resource of quantum entanglement can have drastic consequences on such proof systems. We will see how classical techniques used in the analysis of multiprover interactive proofs, such as the linearity test (or Hadamard code), can be extended to the quantum setting.

Course outline

Weeks 1-2: The classical PCP theorem
Weeks 3-4: Introduction to quantum Hamiltonian complexity and the quantum PCP conjecture
Weeks 5-6: The area law and decay of correlations in 1-dimensional systems
Weeks 7-8: de Finetti theorems in classical and quantum information theory
Weeks 9-10: Multiprover interactive proofs with entangled provers

Prerequisites

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.

Lectures

Sept. 30th. (Lecture notes) Introduction. Three equivalent variants of the PCP theorem: proof checking, multiplayer games, and hardness of approximation.
Reading: Sections 11.1 to 11.4 of Arora-Barak.
Exercises: Problem set 1.
Oct. 2nd. (Lecture notes) The linearity test and NP in PCP(poly,3).
Reading: remainder of Chapter 11 of Arora-Barak.
Oct. 7th. (Lecture notes) Fourier-analysis-based proof of soundness of the BLR linearity test. Discussion of NP in PCP(O(log n),O(1)).
Reading: Section 5 of Chapter 22 in Arora-Barak.
Oct. 9th. (Lecture notes) Dinur's proof of the PCP theorem.
Reading: Sections 1-3 of Chapter 22 in Arora-Barak.
Oct. 14th. (Lecture notes) Intro to Hamiltonian complexity: QMA and the Local Hamiltonian problem
Reading: Chapter of Kitaev-Shen-Vialyi, See also the survey by Aharonov-Naveh and more recent work for the latest QMA-hardness results.
Oct. 16th. (Lecture notes) QMA-completeness of the local Hamiltonian problem: the circuit-to-Hamiltonian construction.
Reading: Section 1.5 of Gharibian's thesis contains a description of the construction. We'll see the analysis by Kempe-Kitaev-Regev (see Sections 3 and 4).
Exercises: Problem set 2.
Oct. 21st. No class (FOCS).
Oct. 23rd. (Lecture notes) The quantum PCP conjecture.
Reading: A survey on the conjecture.
Oct. 28th. (Lecture notes) A variant of QPCP for multiplayer entangled games.
Reading: Lecture notes 1 and 2 by Zhengfeng Ji on quantum games. A great paper by Cleve et al. on the topic. See also Section 5 in the survey.
Challenge problem: baby versions of QPCP.
Oct. 30th. (Lecture notes) Tensor networks, the detectability lemma, and exponential decay of correlations.
Reading: A nice recent survey on quantum Hamiltonian complexity gives more CS-oriented background on the physics behind the local Hamiltonian problem.
A good introduction to tensor networks is this video of a short course given by Zeph Landau at the Simons Institute.
For the detectability lemma and decay of correlations we will mostly follow Sections 3 and 6 from this paper.
Nov. 4th. (Lecture notes) The area law in 1D (1).
Reading: See Section 6.5 in this survey for an introduction. We will follow a mixture of the proofs in the two papers by Arad, Kitaev, Landau and Vazirani: arXiv:1111.2970 and arXiv:1301.1161.
Nov. 6th. (Lecture notes) The area law in 1D (2).
Nov. 11th. (Lecture notes) de Finetti theorems.
Reading: For a very enjoyable read proving the de Finetti theorem for classical permutation-invariant distributions, see the classic paper by Diaconis and Freedman. The first quantum de Finetti theorem we will see appears in a paper by Christandl et al. We will see a very nice proof by Chiribella. (See also the slightly simplified exposition by Harrow. )
Nov. 13th. (Lecture notes) A quantum de Finetti for non-permutation invariant states.
Reading: We will prove Theorem 17 in the recent paper by Brandao and Harrow.
Nov. 18th. (Lecture notes) A no-go result for QPCP over graphs of high degree.
Reading: See Corollary 4 in Brandao-Harrow.
Nov. 20th. (Lecture notes) Tsirelson's characterization of XOR games
Reading: Some lecture notes by Zhengfeng Ji on quantum games, and a classic paper by Cleve et al. that introduced XOR games in the quantum setting.
Nov. 25th. (Lecture notes) 3-player variants of the CHSH and Magic Square games: the role of monogamy.
Reading: A nice paper by Toner on an intriguiding three-player variant of the CHSH game. For the NP-hardness, see Theorem 4.10 in the third set of lecture notes by Ji, and this paper for the original three-player NP-hardness result.
Nov. 27th. No class (Thanksgiving).
Dec. 2nd. (Lecture notes) NP-hardness for the entangled value.
Dec. 4th. Project presentations.
Each group should prepare a 20-minute presentation explaining their project and their findings. Ideally, each group member gets a share of the presentation.
Lunch will be provided.
Write-ups for the projects will be due Dec. 12th. These should be written in latex. There are no length requirements.

Resources

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

On the PCP theorem: Chapters 11 and 22 in the Arora-Barak book ; a nice survey by Jaikumar Radhakrishnan and Madhu Sudan on Dinur's proof; a fun history by Ryan O'Donnell.
John Watrous' lecture notes are a very good introduction to quantum information and complexity theory. See also his survey on quantum complexity.
On the local Hamiltonian problem: A (somewhat dated) introductory paper by Aharonov and Naveh; Kitaev's book has a very clear treatment.
The quantum PCP conjecture: An old but fun post on Scott Aaronson's blog; a more serious one on mine; a recent survey on the conjecture.
The area law: the original paper by Hastings (hard!), and subsequent improvements by Arad et al. See also the survey by Eisert et al.
de Finetti theorems: a beautiful and very clear paper by Diaconis and Freedman; a much more recent paper by Brandao and Harrow and follow-up work applying the result to quantum PCP.