2026-07-23T08:35:18Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25388 2026-03-19T13:04:23Z ddc:004 open_access

Two Bases Suffice for QMA ₁-Completeness Ma, Henry Natarajan, Anand quantum complexity theory Hamiltonian complexity Quantum Merlin Arthur (QMA) QMA₁ quantum satisfiability problem We introduce a basis-restricted variant of the Quantum-k-Sat problem, in which each term in the input Hamiltonian is required to be diagonal in either the standard or Hadamard basis. Our main result is that the Quantum-6-Sat problem with this basis restriction is already QMA₁-complete, defined with respect to a natural gateset. Our construction is based on the Feynman-Kitaev circuit-to-Hamiltonian construction, with a modified clock encoding that interleaves two clocks in the standard and Hadamard bases. In light of the central role played by CSS codes and the uncertainty principle in the proof of the NLTS theorem of Anshu, Breuckmann, and Nirkhe (STOC '23), we hope that the CSS-like structure of our Hamiltonians will make them useful for progress towards a quantum PCP theorem. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Henry Ma and Anand Natarajan 2026 Is Part Of LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2026.101 urn:nbn:de:0030-drops-253880 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.101 eng https://creativecommons.org/licenses/by/4.0/legalcode