2012/03/17 by Jijiang Yan, Dave Bacon, Yan, Jijiang +1 · 2 citations
Computer Science · Mathematics · Physics and Astronomy · #Differential Equations and Boundary Problems #FOS: Physical sciences #Matrix Theory and Algorithms #Quantum Physics (quant-ph) #Spectral Theory in Mathematical Physics #quant-ph
paper · pdf · doi:10.48550/arxiv.1203.3906
6 pages
arxiv created 2012/03/17 · openalex publication_date 2012/03/17 · arxiv updated 2012/03/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a Hamiltonian that is a sum of commuting few-body terms, the commuting Hamiltonian problem is to determine if there exists a quantum state that is the simultaneous eigenstate of all of these terms that minimizes each term individually. This problem is known to be in the complexity class quantum Merlin-Arthur, but is widely thought to not be complete for this class. Here we show that a limited form of this problem when the individual terms are all made up of tensor products of Pauli matrices is efficiently solvable on a classical computer and thus in the complexity class P. The problem can be thought of as the classical XOR-SAT problem over a symplectic vector space. This class of problems includes instance Hamiltonians whose ground states possess topological entanglement, thus showing that such entanglement is not always a barrier for the more general problem.