3-Local Hamiltonian is QMA-complete
classification
🪐 quant-ph
cs.CC
keywords
hamiltonianlocalqma-completeproblemalreadybeenherekitaev
read the original abstract
It has been shown by Kitaev that the 5-local Hamiltonian problem is QMA-complete. Here we reduce the locality of the problem by showing that 3-local Hamiltonian is already QMA-complete.
This paper has not been read by Pith yet.
Forward citations
Cited by 2 Pith papers
-
The Guided Local Hamiltonian Problem for Stoquastic Hamiltonians
The Guided Local Hamiltonian problem for stoquastic Hamiltonians is promise BPP-hard (even 2-local on lattices), BQP-hard under fixed local constraints, and admits a deterministic classical approximation algorithm whe...
-
On the Complexity of the Succinct State Local Hamiltonian Problem
The succinct state 2-local Hamiltonian problem for qubit Hamiltonians is promise-MA-complete.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.