2026-07-20T15:08:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4812 2024-03-06T10:35:12Z ddc:004 open_access

Difficult Instances of the Counting Problem for 2-quantum-SAT are Very Atypical de Beaudrap, Niel Frustration-free Hamiltonian quantum counting satisfiability The problem 2-QUANTUM-SATISFIABILITY (QSAT[2]) is the generalisation of the 2-CNF-SAT problem to quantum bits, and is equivalent to determining whether or not a spin-1/2 Hamiltonian with two-body terms is frustration-free. 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 #P-complete. 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 two-qubit constraints are entangled, which more readily give rise to long-range 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ös-Renyi graphs or bond-percolated lattices, are asymptotically almost surely efficiently solvable except to the extent that they are biased to resemble monotone instances of #SAT[2]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Niel de Beaudrap 2014 Is Part Of LIPIcs, Volume 27, 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.TQC.2014.118 urn:nbn:de:0030-drops-48129 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2014.118 eng https://creativecommons.org/licenses/by/3.0/legalcode