Abstract
The problem 2QUANTUMSATISFIABILITY (QSAT[2]) is the generalisation of the 2CNFSAT problem to quantum bits, and is equivalent to determining whether or not a spin1/2 Hamiltonian with twobody terms is frustrationfree. imilarly to the classical problem #SAT[2], the counting problem #QSAT[2] of determining the size (i.e. the dimension) of the set of satisfying states is #Pcomplete. However, if we consider random instances of QSAT[2] in which constraints are sampled from the Haar measure, intractible instances have measure zero. An apparent reason for this is that almost all twoqubit constraints are entangled, which more readily give rise to longrange constraints.
We investigate under which conditions product constraints also give rise to efficiently solvable families of #QSAT[2] instances. We consider #QSAT[2] involving only discrete distributions over tensor product operators, which interpolates between classical #SAT[2] and #QSAT[2] involving arbitrary product constraints. We find that such instances of #QSAT[2], defined on ErdösRenyi graphs or bondpercolated lattices, are asymptotically almost surely efficiently solvable except to the extent that they are biased to resemble monotone instances of #SAT[2].
BibTeX  Entry
@InProceedings{debeaudrap:LIPIcs:2014:4812,
author = {Niel de Beaudrap},
title = {{Difficult Instances of the Counting Problem for 2quantumSAT are Very Atypical}},
booktitle = {9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)},
pages = {118140},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897736},
ISSN = {18688969},
year = {2014},
volume = {27},
editor = {Steven T. Flammia and Aram W. Harrow},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2014/4812},
URN = {urn:nbn:de:0030drops48129},
doi = {10.4230/LIPIcs.TQC.2014.118},
annote = {Keywords: Frustrationfree, Hamiltonian, quantum, counting, satisfiability}
}
Keywords: 

Frustrationfree, Hamiltonian, quantum, counting, satisfiability 
Seminar: 

9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014) 
Issue Date: 

2014 
Date of publication: 

26.11.2014 