---
res:
  bibo_abstract:
  - "Despite the fundamental role the Quantum Satisfiability (QSAT) problem has\r\nplayed
    in quantum complexity theory, a central question remains open: At which\r\nlocal
    dimension does the complexity of QSAT transition from \"easy\" to \"hard\"?\r\nHere,
    we study QSAT with each constraint acting on a $k$-dimensional and\r\n$l$-dimensional
    qudit pair, denoted $(k,l)$-QSAT. Our first main result shows\r\nthat, surprisingly,
    QSAT on qubits can remain $\\mathsf{QMA}_1$-hard, in that\r\n$(2,5)$-QSAT is $\\mathsf{QMA}_1$-complete.
    In contrast, $2$-SAT on qubits is\r\nwell-known to be poly-time solvable [Bravyi,
    2006]. Our second main result\r\nproves that $(3,d)$-QSAT on the 1D line with
    $d\\in O(1)$ is also\r\n$\\mathsf{QMA}_1$-hard. Finally, we initiate the study
    of 1D $(2,d)$-QSAT by\r\ngiving a frustration-free 1D Hamiltonian with a unique,
    entangled ground state.\r\n  Our first result uses a direct embedding, combining
    a novel clock\r\nconstruction with the 2D circuit-to-Hamiltonian construction
    of [Gosset, Nagaj,\r\n2013]. Of note is a new simplified and analytic proof for
    the latter (as\r\nopposed to a partially numeric proof in [GN13]). This exploits
    Unitary Labelled\r\nGraphs [Bausch, Cubitt, Ozols, 2017] together with a new \"Nullspace
    Connection\r\nLemma\", allowing us to break low energy analyses into small patches
    of\r\nprojectors, and to improve the soundness analysis of [GN13] from\r\n$\\Omega(1/T^6)$
    to $\\Omega(1/T^2)$, for $T$ the number of gates. Our second\r\nresult goes via
    black-box reduction: Given an arbitrary 1D Hamiltonian $H$ on\r\n$d'$-dimensional
    qudits, we show how to embed it into an effective null-space\r\nof a 1D $(3,d)$-QSAT
    instance, for $d\\in O(1)$. Our approach may be viewed as a\r\nweaker notion of
    \"simulation\" (\\`a la [Bravyi, Hastings 2017], [Cubitt,\r\nMontanaro, Piddock
    2018]). As far as we are aware, this gives the first\r\n\"black-box simulation\"-based
    $\\mathsf{QMA}_1$-hardness result, i.e. for\r\nfrustration-free Hamiltonians.@eng"
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Dorian
      foaf_name: Rudolph, Dorian
      foaf_surname: Rudolph
  - foaf_Person:
      foaf_givenName: Sevag
      foaf_name: Gharibian, Sevag
      foaf_surname: Gharibian
      foaf_workInfoHomepage: http://www.librecat.org/personId=71541
    orcid: 0000-0002-9992-3379
  - foaf_Person:
      foaf_givenName: Daniel
      foaf_name: Nagaj, Daniel
      foaf_surname: Nagaj
  bibo_doi: 10.4230/LIPIcs.ITCS.2025.85
  bibo_issue: '85'
  bibo_volume: 325
  dct_date: 2025^xs_gYear
  dct_language: eng
  dct_title: 'Quantum 2-SAT on low dimensional systems is $\mathsf{QMA}_1$-complete:  Direct
    embeddings and black-box simulation@'
...