JOINT ICTP/SISSA STATISTICAL PHYSICS SEMINAR - SPECIAL SEMINAR-: "Phase transitions and random quantum satisfiability"

[statphys]

JOINT ICTP/SISSA STATISTICAL PHYSICS SEMINAR

SPECIAL SEMINAR


Wednesday, 10 June 2009   -    16:00 hrs

Seminar Room
ICTP Leonardo Building - 1st floor


Chris LAUMANN

(Princeton University)

"Phase transitions and random quantum satisfiability"

Abstract
Alongside the effort underway to build quantum computers, it is 
important to better understand which classes of problems they will find 
easy and which others even they will find intractable. Inspired by the 
success of the statistical study of classical constraint optimization 
problems, we study random ensembles of the QMA$_1$- complete quantum 
satisfiability (QSAT) problem introduced by Bravyi. QSAT appropriately 
generalizes the NP-complete classical satisfiability (SAT) problem. We 
show that, as the density of clauses/ projectors is varied, the 
ensembles exhibit quantum phase transitions between phases that are 
satisfiable and unsatisfiable. Remarkably, almost all instances of QSAT 
for any hypergraph exhibit the same dimension of the satisfying 
manifold. This establishes the random QSAT decision problem as 
equivalent to a, potentially new, graph theoretic problem and that the 
hardest typical instances are likely to be localized in a bounded range 
of clause density.
Work done in collaboration with R. Moessner, A. Scardicchio and S. Sondhi.
arXiv:0903.1904