Name
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. 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
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. |
Year | Venue | Keywords |
|---|---|---|
2009 | Clinical Orthopaedics and Related Research | satisfiability,neural network,quantum physics,quantum computer,decision problem,computational complexity,statistical mechanics,phase transition,quantum phase transition |
Field | DocType | Volume |
Quantum complexity theory,Quantum statistical mechanics,Discrete mathematics,Quantum mechanics,Satisfiability,Quantum computer,Quantum simulator,Quantum algorithm,Quantum information,Mathematics,Quantum network | Journal | abs/0903.1 |
ISSN | Citations | PageRank |
Quant. Inf. and Comp. (2010) vol. 10 (1) 1 pp. 0001-0015 | 7 | 0.56 |
References | Authors | |
0 | 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 |