| Title: |
Two Bases Suffice for QMA ₁-Completeness |
| Authors: |
Ma, Henry; Natarajan, Anand |
| Contributors: |
Henry Ma and Anand Natarajan |
| Publisher Information: |
Schloss Dagstuhl – Leibniz-Zentrum für Informatik |
| Publication Year: |
2026 |
| Collection: |
DROPS - Dagstuhl Research Online Publication Server (Schloss Dagstuhl - Leibniz Center for Informatics ) |
| Subject Terms: |
quantum complexity theory; Hamiltonian complexity; Quantum Merlin Arthur (QMA); QMA₁; quantum satisfiability problem |
| Description: |
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. |
| Document Type: |
article in journal/newspaper; conference object |
| File Description: |
application/pdf |
| Language: |
English |
| Relation: |
Is Part Of LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026); https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.101 |
| DOI: |
10.4230/LIPIcs.ITCS.2026.101 |
| Availability: |
https://doi.org/10.4230/LIPIcs.ITCS.2026.101; https://nbn-resolving.org/urn:nbn:de:0030-drops-253880; https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.101 |
| Rights: |
https://creativecommons.org/licenses/by/4.0/legalcode |
| Accession Number: |
edsbas.EA38FA2D |
| Database: |
BASE |