2026-07-22T05:41:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22713 2026-04-17T05:32:40Z ddc:004 open_access

Quantum 2-SAT on Low Dimensional Systems Is QMAsubscript{1}-Complete: Direct Embeddings and Black-Box Simulation Rudolph, Dorian Gharibian, Sevag Nagaj, Daniel quantum complexity theory Quantum Merlin Arthur (QMA) Quantum Satisfiability Problem (QSAT) Hamiltonian simulation 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 d_A-dimensional and d_B-dimensional qudit pair, denoted (d_A×d_B)-QSAT. Our first main result shows that, surprisingly, QSAT on qubits can remain QMA_1-hard, in that (2×5)-QSAT is QMA_1-complete. (QMA_1 is a quantum analogue of MA with perfect completeness.) In contrast, (2×2)-QSAT (i.e. Quantum 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 ∈ O(1) is also QMA_1-hard. Finally, we initiate the study of (2×d)-QSAT on the 1D line by giving a frustration-free 1D Hamiltonian with a unique, entangled ground state. As implied by our title, our first result uses a direct embedding: We combine a novel clock construction with the 2D circuit-to-Hamiltonian construction of [Gosset and 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 Ω(1/T⁶) to Ω(1/T²), 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 1D (3×d)-QSAT instance, for d ∈ O(1). Our approach may be viewed as a weaker notion of "analog simulation" (à la [Bravyi, Hastings 2017], [Cubitt, Montanaro, Piddock 2018]). As far as we are aware, this gives the first "black-box simulation"-based QMA_1-hardness result. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dorian Rudolph and Sevag Gharibian and Daniel Nagaj 2025 Is Part Of LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2025.85 urn:nbn:de:0030-drops-227139 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.85 eng https://creativecommons.org/licenses/by/4.0/legalcode