2026-07-22T06:32:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22691 2026-04-17T05:32:22Z ddc:004 open_access

Complexity Classification of Product State Problems for Local Hamiltonians Kallaugher, John Parekh, Ojas Thompson, Kevin Wang, Yipu Yirka, Justin quantum complexity quantum algorithms local hamiltonians Product states, unentangled tensor products of single qubits, are a ubiquitous ansatz in quantum computation, including for state-of-the-art Hamiltonian approximation algorithms. A natural question is whether we should expect to efficiently solve product state problems on any interesting families of Hamiltonians. We completely classify the complexity of finding minimum-energy product states for Hamiltonians defined by any fixed set of allowed 2-qubit interactions. Our results follow a line of work classifying the complexity of solving Hamiltonian problems and classical constraint satisfaction problems based on the allowed constraints. We prove that estimating the minimum energy of a product state is in 𝖯 if and only if all allowed interactions are 1-local, and NP-complete otherwise. Equivalently, any family of non-trivial two-body interactions generates Hamiltonians with NP-complete product-state problems. Our hardness constructions only require coupling strengths of constant magnitude. A crucial component of our proofs is a collection of hardness results for a new variant of the Vector Max-Cut problem, which should be of independent interest. Our definition involves sums of distances rather than squared distances and allows linear stretches. We similarly give a proof that the original Vector Max-Cut problem is NP-complete in 3 dimensions. This implies hardness of optimizing product states for Quantum Max-Cut (the quantum Heisenberg model) is NP-complete, even when every term is guaranteed to have positive unit weight. Schloss Dagstuhl – Leibniz-Zentrum für Informatik John Kallaugher and Ojas Parekh and Kevin Thompson and Yipu Wang and Justin Yirka 2025 Is Part Of LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2025.63 urn:nbn:de:0030-drops-226910 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.63 eng https://creativecommons.org/licenses/by/4.0/legalcode