February 28, 2014: Seminar - Sevag Gharibian: "Approximation algorithms for quantum constraint satisfaction problems"


Approximation algorithms for quantum constraint satisfaction problems

Sevag Gharibian
University of California, Berkeley
Monday, March 3, 2014
11:00 a.m., 1325 SEO Building


Approximation algorithms for constraint satisfaction problems (CSPs) are one of the main areas of study in theoretical computer science. In the quantum setting, there is a natural generalization of CSPs which is well-motivated for two reasons: From a computer science perspective, such problems are complete for the quantum version of NP, known as Quantum Merlin- Arthur (QMA). From a physics standpoint, quantum CSPs encode the behavior of the quantum world around us. Indeed, for this reason, the physics community has spent decades developing heuristic algorithms for this class of problems. In this talk, we give one of the first known rigorous approximation algorithms for quantum CSPs. Specifically, we show how to non-trivially approximate "dense" quantum CSPs efficiently with a classical computer.

This presentation is based on joint work with Julia Kempe. No background in quantum computing is assumed.


Sevag Gharibian completed his Ph.D. in 2012 at the University of Waterloo under the supervision of Richard Cleve. He is currently a Simons Postdoctoral Fellow at the University of California, Berkeley, and a Banting Postdoctoral Fellow of the Natural Sciences and Engineering Research Council of Canada.

Copyright 2016 The Board of Trustees
of the University of Illinois.webmaster@cs.uic.edu
Helping Women Faculty Advance
Funded by NSF