Quantum 2-SAT on Low Dimensional Systems is QMA_1-Complete

Learn about groundbreaking research in quantum complexity theory through this conference talk that explores the complexity transition points in Quantum Satisfiability (QSAT) problems. Delve into two major findings: the QMA_1-completeness of (2,5)-QSAT and the QMA_1-hardness of (3,d)-QSAT on one-dimensional systems. Discover novel approaches including a direct embedding method combining clock construction with 2D circuit-to-Hamiltonian construction, and a black-box reduction technique for embedding arbitrary 1D Hamiltonians into effective 1D QSAT instances. Explore the implications of these findings for quantum complexity theory, including a new simplified analytic proof utilizing Unitary Labelled Graphs and a "Nullspace Connection Lemma" that improves soundness analysis. Presented at the 19th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2024), this talk advances understanding of quantum computational complexity and its fundamental boundaries.