Tuesday, March 08, 2016

3:00 PM -
4:00 PM

Annenberg 107

# IQI Weekly Seminar

A linear time algorithm for quantum 2-SAT

Sevag Gharibian

*,*Virginia Commonwealth University*,*The Boolean constraint satisfaction problem 3-SAT is arguably the canonical NP-complete problem. In contrast, 2-SAT can not only be decided in polynomial time, but in fact in deterministic linear time. In 2006, Bravyi proposed a physically motivated generalization of k-SAT to the quantum setting, defining the problem "quantum k-SAT". He showed that quantum 2-SAT is also solvable in polynomial time on a classical computer, in particular in deterministic time O(n^4), assuming unit cost arithmetic over a field extension of the rational numbers, where n is number of variables. In this paper, we present an algorithm for quantum 2-SAT which runs in linear time, i.e. deterministic time O(n + m) for n and m the number of variables and clauses, respectively. Our approach exploits the transfer matrix techniques of Laumann et al. [QIC, 2010] used in the study of phase transitions for random quantum 2-SAT, and bears similarities with both the linear time 2-SAT algorithms of Even, Itai, and Shamir (based on backtracking) [SICOMP, 1976] and Aspvall, Plass, and Tarjan (based on strongly connected components) [IPL, 1979].

This talk is based on joint work with Niel de Beaudrap (University of Oxford).

This talk is based on joint work with Niel de Beaudrap (University of Oxford).

For more information, please contact Jackie O'Sullivan by phone at 626.395.4964 or by email at jackieos@caltech.edu.