License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.TQC.2014.118
URN: urn:nbn:de:0030-drops-48129
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4812/
Go to the corresponding LIPIcs Volume Portal

de Beaudrap, Niel

Difficult Instances of the Counting Problem for 2-quantum-SAT are Very Atypical

pdf-format:
12.pdf (0.7 MB)

Abstract

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].

BibTeX - Entry

@InProceedings{debeaudrap:LIPIcs:2014:4812,
  author =	{Niel de Beaudrap},
  title =	{{Difficult Instances of the Counting Problem for 2-quantum-SAT are Very Atypical}},
  booktitle =	{9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)},
  pages =	{118--140},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-73-6},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{27},
  editor =	{Steven T. Flammia and Aram W. Harrow},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4812},
  URN =		{urn:nbn:de:0030-drops-48129},
  doi =		{10.4230/LIPIcs.TQC.2014.118},
  annote =	{Keywords: Frustration-free, Hamiltonian, quantum, counting, satisfiability}
}

Keywords: Frustration-free, Hamiltonian, quantum, counting, satisfiability
Collection: 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)
Issue Date: 2014
Date of publication: 11.12.2014

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI