The Weizmann Institute of Science
Faculty of Mathematics and Computer Science
Foundations of Computer Science Seminar
Seminar Room, Room 261, Ziskind Building
on Monday, February 7, 2011
14:30 - 15:30
Julia Kempe
Tel Aviv University and University of Paris
will speak on
A geometric Lovasz Local Lemma
and applications to quantum SAT
Abstract:
The Lovasz Local Lemma (LLL) is a powerful tool in probability theory to show
the existence of combinatorial objects meeting a prescribed collection of {\it
weakly dependent} criteria. We show that the LLL extends to a much more general
geometric setting, where events are replaced with subspaces and probability is
replaced with relative dimension, which allows to lower bound the dimension of
the intersection of vector spaces under certain independence conditions.
We show how our result applies directly to the quantum SAT problem. This
problem is the natural generalisation of SAT to the quantum setting and is
QMA-complete (QMA is ``quantum NP"). We then apply our results to the recently
studied model of random $k$-QSAT. Recent works have shown that the satisfiable
region extends up to a density of 1 in the large $k$ limit, where the density
is the ratio of projectors to qubits. Using our result we greatly extend the
known satisfiable region for random $k$-QSAT.
We will introduce all relevant notions of quantum information.
Joint work with Andris Ambainis (Univ. of Latvia) and Or Sattath (Hebrew
University and Tel Aviv University)