printlogo
http://www.ethz.ch/index_EN
International Workshop on Quantum Information Processing
 
print
  

QIP 2010 at

ETH Life

The daily web-journal of ETH Zurich:

"Lifting the big veil"

"Nach dem grossen Schleier lüften"

18.01.2010

QIP 2010 at the

Swiss Radio DRS

Echo der Zeit

from Monday Jan 18, 2010

in German, Link >>

(Real Player recommended)

chocolate


pdf files of
Programme Booklet >>
and
Abstracts of all Talks >>

You will receive a hard copy of these files at the registration desk.

Sponsors

Pauli Center for Theoretical Studies

pauliohne


The Swiss National Science Foundation

snflogo


ETH Zurich (Computer Science and Physics Department)

ethlogo


Quantum Science and Technology

qsitmitschrift


CQT Singapore

cqtlogo


QAP European Project

qaplogo3


Sandia National Laboratories

sandia


Institute for Quantum Computing

finaliqc


id Quantique

3rdideequantique

A quantum Lovász Local Lemma

Julia Kempe, Tel Aviv University

joint work with Andris Ambainis (Univ. of Latvia) and Or Sattath (Hebrew University and Tel Aviv University)


The Lovász Local Lemma (LLL) is a powerful tool in probability theory to show the existence of combinatorial objects meeting a prescribed collection of “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.

Our result immediately applies to the k-QSAT problem: For instance we show that any collection of rank 1 projectors with the property that each qubit appears in at most 2k/(e · k) of them, has a joint satisfiable state.

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 a hybrid approach building on work by Laumann et al. (also presented at QIP) we greatly extend the known satisfiable region for random k-QSAT to a density of Ω(2k/k2). Since our tool allows us to show the existence of joint satisfying states without the need to construct them, we are able to penetrate into regions where the satisfying states are conjectured to be entangled, avoiding the need to construct them, which has limited previous approaches to product states.

 

Wichtiger Hinweis:
Diese Website wird in älteren Versionen von Netscape ohne graphische Elemente dargestellt. Die Funktionalität der Website ist aber trotzdem gewährleistet. Wenn Sie diese Website regelmässig benutzen, empfehlen wir Ihnen, auf Ihrem Computer einen aktuellen Browser zu installieren. Weitere Informationen finden Sie auf
folgender Seite.

Important Note:
The content in this site is accessible to any browser or Internet device, however, some graphics will display correctly only in the newer versions of Netscape. To get the most out of our site we suggest you upgrade to a newer browser.
More information

© 2013 ETH Zürich | Imprint | Disclaimer | 2 January 2010
top