Complexity classification of product state problems for local Hamiltonians

DOI10.4230/LIPICS.ITCS.2025.63MaRDI QIDQ7296707zbMATH OpenFDO

Authors John Kallaugher, Ojas Parekh, Kevin E. Thompson, Yipu Wang, Justin Yirka

Publication date 14 July 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ITCS.2025.63

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A dichotomy theorem for maximum generalized satisfiability problems.
• A generalized Grothendieck inequality and nonlocal correlations that require high entanglement
• A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
• Approximating the little Grothendieck problem over the orthogonal and unitary groups
• Approximation algorithms for QMA-complete problems
• Approximation algorithms for quantum many-body problems
• Boolean constraint satisfaction: Complexity results for optimization problems with arbitrary weights
• Complexity classification of local Hamiltonian problems
• Complexity classifications of Boolean constraint satisfaction problems
• Computational Complexity
• Consistency of Local Density Matrices Is QMA-Complete
• Graphs and geometry
• scientific article; zbMATH DE number 1944141 (Why is no real title available?)
• scientific article; zbMATH DE number 1559517 (Why is no real title available?)
• scientific article; zbMATH DE number 1776257 (Why is no real title available?)
• scientific article; zbMATH DE number 7650098 (Why is no real title available?)
• scientific article; zbMATH DE number 7758361 (Why is no real title available?)
• scientific article; zbMATH DE number 7740929 (Why is no real title available?)
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Normal Forms for Skew-Symmetric Matrices and Hamiltonian Systems with First Integrals Linear in Momenta
• On complexity of the quantum Ising model
• On the Total Edge-Length of a Tetrahedron
• Problems of distance geometry and convex properties of quadratic maps
• Product-state approximations to quantum states
• QMA-hardness of consistency of local density matrices with applications to quantum zero-knowledge
• Quantum Hamiltonian Complexity
• THE 2-LOCAL HAMILTONIAN PROBLEM ENCOMPASSES NP
• The Approximability of Three-valued MAX CSP
• The complexity of finite-valued CSPs
• The complexity of satisfiability problems
• The positive semidefinite Grothendieck problem with rank constraint
• The theory of quantum information
• Tight hardness of the non-commutative Grothendieck problem
• Unique games hardness of quantum max-cut, and a conjectured vector-valued Borell's inequality
• Universal quantum Hamiltonians

This page was built for publication: Complexity classification of product state problems for local Hamiltonians

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7296707)