Sevag Gharibian, Universität Paderborn, Germany, and Virginia Commonwealth University, USA

Title: Efficient algorithms for quantum constraint satisfaction problems.

Abstract: The study of Boolean constraint satisfaction problems, such as MAX-k-SAT, is central to theoretical computer science. In the quantum setting, there is a natural generalization of MAX-k-SAT, known as the k-local Hamiltonian problem (k-LH), which is complete for the quantum analogue of NP [Kitaev, 1999]. Moreover, k-LH is appealing in that it encodes a fundamental physical question: What is the energy of a given quantum system when cooled to low temperature? In this talk, we begin with an introduction to complexity theoretic background regarding k-LH. We then give an optimal linear-time algorithm for the quantum analogue of 2 SAT, improving upon the quartic-time quantum 2-SAT algorithm of [Bravyi, 2006]. Our work exploits the transfer matrix techniques of [Laumann et al., 2010] from the study of random quantum 2-SAT, and bears similarities with both the classic linear time 2-SAT algorithms of [Even, Itai, and Shamir, 1976] (based on backtracking), and [Aspvall, Plass, and Tarjan,1979] (based on strongly connected components).