Computer Science Events

This calendar presented by Computer Science

[PAST EVENT] On efficient algorithms for quantum constraint satisfaction problems

February 24, 2017
8am - 9am
Location
McGlothlin-Street Hall, Room 020
251 Jamestown Rd
Williamsburg, VA 23185Map this location

Abstract:

The study of Boolean constraint satisfaction problems, such at MAX-k-SAT, is central to theoretical computer science. In the setting of quantum computation, there is a natural generalization of MAX-k-SAT, known as the k-local Hamiltonian problem (k-LH), which is appealing for two reasons: First, in terms of complexity theory, it is complete for the quantum analogue of NP [Kitaev, 1999]. Second, from a physical perspective, it asks a fundamental question: What is the energy of a given quantum system when cooled to low temperature? In this talk, we begin by introducing k-LH and relevant complexity theoretic background. We then give an optimal linear-time algorithm for the quantum analogue of 2-SAT, which improves 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 limited backtracking), and [Aspvall, Plass, and Tarjan,1979 ](based on strongly connected components).

This talk assumes no background in quantum computation, and is based partly on joint work with Niel de Beaudrap (University of Oxford).

Bio:

Sevag obtained his Ph.D. in 2012 from the University of Waterloo, Canada under the supervision of Dr. Richard Cleve. He taught as a Visiting Lecturer at the University of Illinois at Chicago in Fall 2012, and from 2013-2014 was a Postdoctoral Fellow in the group of Dr. Umesh Vazirani at the University of California, Berkeley. He was awarded Canada's prestigious NSERC Banting Postdoctoral Fellowship in 2013, and was also a Simons Research Fellow at the Simons Institute for the Theory of Computing at UC Berkeley. In 2014, he joined VCU as an Assistant Professor in Computer Science. He currently serves as Secretary on the Board of Trustees of the Computational Complexity Conference (CCC), and is a Founding Editor of the open-access journal Quantum.

Contact

Xu Liu 757-221-7739