{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,31]],"date-time":"2022-03-31T07:27:29Z","timestamp":1648711649388},"reference-count":0,"publisher":"Rinton Press","issue":"11&12","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["QIC"],"published-print":{"date-parts":[[2015,9]]},"abstract":"<jats:p>The Quantum Satisfiability problem ($\\qsat$) is the generalization of the canonical $\\NPC$ problem - Boolean Satisfiability. $\\ksqsat$ is the following variant of the problem: given a set of projectors of rank $1$, acting non-trivially on $k$ qubits out of $n$ qubits, such that each qubit appears in at most $s$ projectors, decide whether there exists a quantum state in the null space of all the projectors. Let $\\qf(k)$ be the maximal integer $s$ such that every $\\ksqsat$ instance is satisfiable. Deciding $\\ksqsat[\\qf(k)]$ is computationally easy: by definition the answer is ``satisfiable''. But, by relaxing the conditions slightly, we show that $\\ksqsat[\\qf(k)+2]$ is $\\QMAoH$, for $k \\geq 15$. This is a quantum analogue of a classical result by Kratochv{\\'\\i}l et al.~\\cite{kratochvil1993one}. We use the term ``an \\emph{almost} sudden jump'' to stress that the complexity of $\\ksqsat[\\qf(k)+1]$ is open, where the jump in the classical complexity is known to be sudden. We present an implication of this finding to the quantum PCP conjecture, arguably one of the most important open problems in the field of Hamiltonian complexity. Our implication imposes some constraints on one possible way to refute the quantum PCP.<\/jats:p>","DOI":"10.26421\/qic15.11-12-11","type":"journal-article","created":{"date-parts":[[2021,2,28]],"date-time":"2021-02-28T02:51:47Z","timestamp":1614480707000},"page":"1048-1059","source":"Crossref","is-referenced-by-count":0,"title":["An almost sudden jump in quantum complexity"],"prefix":"10.26421","volume":"15","author":[{"given":"Or","family":"Sattath","sequence":"first","affiliation":[]}],"member":"10955","published-online":{"date-parts":[[2015,9]]},"container-title":["Quantum Information and Computation"],"original-title":[],"deposited":{"date-parts":[[2021,2,28]],"date-time":"2021-02-28T02:52:00Z","timestamp":1614480720000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.rintonpress.com\/journals\/doi\/QIC15.11-12-11.html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,9]]},"references-count":0,"journal-issue":{"issue":"11&12","published-online":{"date-parts":[[2015,9]]},"published-print":{"date-parts":[[2015,9]]}},"URL":"https:\/\/doi.org\/10.26421\/qic15.11-12-11","relation":{},"ISSN":["1533-7146","1533-7146"],"issn-type":[{"value":"1533-7146","type":"print"},{"value":"1533-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,9]]}}}