Quantum 2-SAT on low dimensional systems is $\mathsf{QMA}_1$-complete: Direct embeddings and black-box simulation

conference paper Quantum 2-SAT on low dimensional systems is $\mathsf{QMA}_1$-complete: Direct embeddings and black-box simulation published Dorian Rudolph author Sevag Gharibian author 715410000-0002-9992-3379 Daniel Nagaj author 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. 2025 eng 16th Innovations in Theoretical Computer Science (ITCS) 2401.0236810.4230/LIPIcs.ITCS.2025.85 325851-24 Rudolph D, Gharibian S, Nagaj D. Quantum 2-SAT on low dimensional systems is $\mathsf{QMA}_1$-complete: Direct embeddings and black-box simulation. In: 16th Innovations in Theoretical Computer Science (ITCS). Vol 325. ; 2025:1-24. doi:<a href="https://doi.org/10.4230/LIPIcs.ITCS.2025.85">10.4230/LIPIcs.ITCS.2025.85</a> Rudolph, Dorian, Sevag Gharibian, and Daniel Nagaj. “Quantum 2-SAT on Low Dimensional Systems Is $\mathsf{QMA}_1$-Complete: Direct Embeddings and Black-Box Simulation.” In 16th Innovations in Theoretical Computer Science (ITCS), 325:1–24, 2025. <a href="https://doi.org/10.4230/LIPIcs.ITCS.2025.85">https://doi.org/10.4230/LIPIcs.ITCS.2025.85</a>. D. Rudolph, S. Gharibian, and D. Nagaj, “Quantum 2-SAT on low dimensional systems is $\mathsf{QMA}_1$-complete: Direct embeddings and black-box simulation,” in 16th Innovations in Theoretical Computer Science (ITCS), 2025, vol. 325, no. 85, pp. 1–24, doi: <a href="https://doi.org/10.4230/LIPIcs.ITCS.2025.85">10.4230/LIPIcs.ITCS.2025.85</a>. Rudolph, Dorian, et al. “Quantum 2-SAT on Low Dimensional Systems Is $\mathsf{QMA}_1$-Complete: Direct Embeddings and Black-Box Simulation.” 16th Innovations in Theoretical Computer Science (ITCS), vol. 325, no. 85, 2025, pp. 1–24, doi:<a href="https://doi.org/10.4230/LIPIcs.ITCS.2025.85">10.4230/LIPIcs.ITCS.2025.85</a>. @inproceedings{Rudolph_Gharibian_Nagaj_2025, title={Quantum 2-SAT on low dimensional systems is $\mathsf{QMA}_1$-complete: Direct embeddings and black-box simulation}, volume={325}, DOI={<a href="https://doi.org/10.4230/LIPIcs.ITCS.2025.85">10.4230/LIPIcs.ITCS.2025.85</a>}, number={85}, booktitle={16th Innovations in Theoretical Computer Science (ITCS)}, author={Rudolph, Dorian and Gharibian, Sevag and Nagaj, Daniel}, year={2025}, pages={1–24} } D. Rudolph, S. Gharibian, D. Nagaj, in: 16th Innovations in Theoretical Computer Science (ITCS), 2025, pp. 1–24. Rudolph, D., Gharibian, S., & Nagaj, D. (2025). Quantum 2-SAT on low dimensional systems is $\mathsf{QMA}_1$-complete: Direct embeddings and black-box simulation. 16th Innovations in Theoretical Computer Science (ITCS), 325(85), 1–24. <a href="https://doi.org/10.4230/LIPIcs.ITCS.2025.85">https://doi.org/10.4230/LIPIcs.ITCS.2025.85</a> 502722024-01-07T20:09:13Z2025-02-11T07:21:23Z