Name
Abstract | ||
|---|---|---|
Alongside the effort underway to build quantum computers, it is important to betterunderstand which classes of problems they will find easy and which others even theywill find intractable. We study random ensembles of the QMA1-complete quantum sat-isfiability (QSAT) problem introduced by Bravyi [1]. QSAT appropriately generalizesthe NP-complete classical satisfiability (SAT) problem. We show that, as the density ofclauses/projectors is varied, the ensembles exhibit quantum phase transitions betweenphases that are satisfiable and unsatisfiable. Remarkably, almost all instances of QSATfor any hypergraph exhibit the same dimension of the satisfying manifold. This estab-lishes the QSAT decision problem as equivalent to a, potentially new, graph theoreticproblem and that the hardest typical instances are likely to be localized in a boundedrange of clause density. |
Year | Venue | Keywords |
|---|---|---|
2010 | Quantum Information & Computation | hypergraph exhibit,graph theoreticproblem,random quantum satisfiabiilty,QSAT decision problem,effort underway,quantum computer,generalizesthe NP-complete classical satisfiability,QMA1-complete quantum sat-isfiability,ensembles exhibit quantum phase,density ofclauses,clause density |
DocType | Volume | Issue |
Journal | 10 | 1 |
ISSN | Citations | PageRank |
1533-7146 | 0 | 0.34 |
References | Authors | |
1 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| C. R. Laumann | 1 | 16 | 3.09 |
| R. Moessner | 2 | 15 | 1.79 |
| A. Scardicchio | 3 | 15 | 2.46 |
| S. L. Sondhi | 4 | 15 | 2.12 |