@unpublished{50272,
abstract = {{Despite the fundamental role the Quantum Satisfiability (QSAT) problem has
played in quantum complexity theory, a central question remains open: At which
local dimension does the complexity of QSAT transition from "easy" to "hard"?
Here, we study QSAT with each constraint acting on a $k$-dimensional and
$l$-dimensional qudit pair, denoted $(k,l)$-QSAT. Our first main result shows
that, surprisingly, QSAT on qubits can remain $\mathsf{QMA}_1$-hard, in that
$(2,5)$-QSAT is $\mathsf{QMA}_1$-complete. In contrast, $2$-SAT on qubits is
well-known to be poly-time solvable [Bravyi, 2006]. Our second main result
proves that $(3,d)$-QSAT on the 1D line with $d\in O(1)$ is also
$\mathsf{QMA}_1$-hard. Finally, we initiate the study of 1D $(2,d)$-QSAT by
giving a frustration-free 1D Hamiltonian with a unique, entangled ground state.
Our first result uses a direct embedding, combining a novel clock
construction with the 2D circuit-to-Hamiltonian construction of [Gosset, Nagaj,
2013]. Of note is a new simplified and analytic proof for the latter (as
opposed to a partially numeric proof in [GN13]). This exploits Unitary Labelled
Graphs [Bausch, Cubitt, Ozols, 2017] together with a new "Nullspace Connection
Lemma", allowing us to break low energy analyses into small patches of
projectors, and to improve the soundness analysis of [GN13] from
$\Omega(1/T^6)$ to $\Omega(1/T^2)$, for $T$ the number of gates. Our second
result goes via black-box reduction: Given an arbitrary 1D Hamiltonian $H$ on
$d'$-dimensional qudits, we show how to embed it into an effective null-space
of a 1D $(3,d)$-QSAT instance, for $d\in O(1)$. Our approach may be viewed as a
weaker notion of "simulation" (\`a la [Bravyi, Hastings 2017], [Cubitt,
Montanaro, Piddock 2018]). As far as we are aware, this gives the first
"black-box simulation"-based $\mathsf{QMA}_1$-hardness result, i.e. for
frustration-free Hamiltonians.}},
author = {{Rudolph, Dorian and Gharibian, Sevag and Nagaj, Daniel}},
booktitle = {{arXiv:2401.02368}},
title = {{{Quantum 2-SAT on low dimensional systems is $\mathsf{QMA}_1$-complete: Direct embeddings and black-box simulation}}},
year = {{2024}},
}