2026-07-22T04:54:17Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17706 2024-03-06T11:00:22Z ddc:004 open_access

The Complexity of Translationally Invariant Problems Beyond Ground State Energies Watson, James D. Bausch, Johannes Gharibian, Sevag Complexity Quantum Computing Physics Constraint Satisfaction Combinatorial Reconfiguration Many-Body Physics The physically motivated quantum generalisation of k-SAT, the k-Local Hamiltonian (k-LH) problem, is well-known to be QMA-complete ("quantum NP"-complete). What is surprising, however, is that while the former is easy on 1D Boolean formulae, the latter remains hard on 1D local Hamiltonians, even if all constraints are identical [Gottesman, Irani, FOCS 2009]. Such "translation-invariant" systems are much closer in structure to what one might see in Nature. Moving beyond k-LH, what is often more physically interesting is the computation of properties of the ground space (i.e. "solution space") itself. In this work, we focus on two such recent problems: Simulating local measurements on the ground space (APX-SIM, analogous to computing properties of optimal solutions to MAX-SAT formulae) [Ambainis, CCC 2014], and deciding if the low energy space has an energy barrier (GSCON, analogous to classical reconfiguration problems) [Gharibian, Sikora, ICALP 2015]. These problems are known to be P^{QMA[log]}- and QCMA-complete, respectively, in the general case. Yet, to date, it is not known whether they remain hard in such simple 1D translationally invariant systems. In this work, we show that the 1D translationally invariant versions of both APX-SIM and GSCON are intractable, namely are P^{QMA_{EXP}}- and QCMA^{EXP}-complete ("quantum P^{NEXP}" and "quantum NEXP"), respectively. Each of these results is attained by giving a respective generic "lifting theorem". For APX-SIM we give a framework for lifting any abstract local circuit-to-Hamiltonian mapping H satisfying mild assumptions to hardness of APX-SIM on the family of Hamiltonians produced by H, while preserving the structural properties of H (e.g. translation invariance, geometry, locality, etc). Each result also leverages counterintuitive properties of our constructions: for APX-SIM, we compress the answers to polynomially many parallel queries to a QMA oracle into a single qubit. For GSCON, we show strong robustness, i.e. soundness even against adversaries acting on all but a single qudit in the system. Schloss Dagstuhl – Leibniz-Zentrum für Informatik James D. Watson and Johannes Bausch and Sevag Gharibian 2023 Is Part Of LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2023.54 urn:nbn:de:0030-drops-177065 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.54 eng https://creativecommons.org/licenses/by/4.0/legalcode