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

Random quantum satisfiability: statistical mechanics of disordered quantum optimization 


Roderich Moessner, MPI Dresden

joint work with Sergey Bravyi, Cristopher Moore, Alexander Russell, Christopher Laumann, Andreas Läuchli, Antonello Scardicchio, and Shivaji Sondhi

We report a cluster of results on random quantum k-QSAT formulas with M clauses and N qubits. In this approach, the clause density M/N acts as a control parameter with which to tune one's attention from low density, easily satisfied to high density, highly frustrated instances of QSAT. We characterize the phase diagram of random k-QSAT using several complementary approaches. We examine unentangled (product) satisfying states and discover a geometric criterion for deciding when a QSAT interaction graph is generically product satisfiable. Applied to the random graph ensemble, this criterion provides improved lower bounds on the location of the SAT--UNSAT transition. Coupled with recent work on the quantum Lovasz local lemma, this shows the existence of an entanglement transition in the satisfying space of the random ensemble at large k. For k=3 and k=4, we present numerical results which provide mild evidence for a similar transition at smaller k. Finally, we examine the UNSAT regime and improve the upper bound on the SAT-UNSAT threshold. We show that the threshold for random quantum k-SAT is strictly less than the conjectured classical k-SAT threshold. These bounds work by determining the generic dimension of the satisfying subspace for certain gadgets, and then using differential equations to analyze algorithms that partition the hypergraph of clauses into a collection of these gadgets. The use of differential equation to establish upper bounds on a satisfiability threshold appears to be novel, and our techniques may apply to various classical problems as well.

The results regarding product satisfiability and numerics are due to C.R. Laumann, A. Lauchli, R. Moessner, A. Scardicchio and S.L. Sondhi. The use of gadgets and differential equations to improve the upper bound on the threshold are due to S. Bravyi, C. Moore, and A. Russell.

Joint talk given on the submissions:

Sergey Bravyi, Cristopher Moore, and Alexander Russell

Bounds on the quantum satisfiability threshold

and

Christopher Laumann, Andreas Läuchli, Roderich Moessner, Antonello Scardicchio, and Shivaji Sondhi

Random quantum satisfiability: statistical mechanics of disordered quantum optimization 

 

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 | 8 January 2010
top