Phase transitions and random quantum satisfiability

Details Phase transitions and random quantum satisfiability Phase transitions and random quantum satisfiability

2009-03-11

arxiv.org/abs/0903.1904v1

Quant. Inf. and Comp. (2010) vol. 10 (1) 1 pp. 0001-0015

Physics

Quantum Physics

9 pages, 3 figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Phase transitions and random quantum satisfiability does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Phase transitions and random quantum satisfiability, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Phase transitions and random quantum satisfiability will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-123475