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

The Swiss National Science Foundation

ETH Zurich (Computer Science and Physics Department)

Quantum Science and Technology

CQT Singapore

QAP European Project

Sandia National Laboratories

Institute for Quantum Computing

id Quantique

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