{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,21]],"date-time":"2026-07-21T01:43:21Z","timestamp":1784598201206,"version":"3.55.0"},"reference-count":0,"publisher":"Rinton Press","issue":"13&14","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["QIC"],"published-print":{"date-parts":[[2016,10]]},"abstract":"<jats:p>We study a quantum algorithm that consists of a simple quantum Markov process, and we analyze its behavior on restricted versions of Quantum 2-SAT. We prove that the algorithm solves these decision problems with high probability for n qubits, L clauses, and promise gap c in time O(n^2 L^2 c^{\u22122} ). If the Hamiltonian is additionally polynomially gapped, our algorithm efficiently produces a state that has high overlap with the satisfying subspace. The Markov process we study is a quantum analogue of Schoning\u2019s probabilistic algorithm for  k-SAT.<\/jats:p>","DOI":"10.26421\/qic16.13-14-7","type":"journal-article","created":{"date-parts":[[2021,2,26]],"date-time":"2021-02-26T05:28:51Z","timestamp":1614317331000},"page":"1212-1227","source":"Crossref","is-referenced-by-count":7,"title":["A quantum version of Schoning's algorithm applied to quantum 2-SAT"],"prefix":"10.26421","volume":"16","author":[{"given":"Edward","family":"Farhi","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shelby","family":"Kimmel","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kristan","family":"Temme","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"10955","published-online":{"date-parts":[[2016,10]]},"container-title":["Quantum Information and Computation"],"original-title":[],"deposited":{"date-parts":[[2021,2,26]],"date-time":"2021-02-26T05:28:51Z","timestamp":1614317331000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.rintonpress.com\/journals\/doi\/QIC16.13-14-7.html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,10]]},"references-count":0,"journal-issue":{"issue":"13&14","published-online":{"date-parts":[[2016,10]]},"published-print":{"date-parts":[[2016,10]]}},"URL":"https:\/\/doi.org\/10.26421\/qic16.13-14-7","relation":{},"ISSN":["1533-7146","1533-7146"],"issn-type":[{"value":"1533-7146","type":"print"},{"value":"1533-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,10]]}}}