Two remarks on the local Hamiltonian problem
classification
🪐 quant-ph
keywords
hamiltonianlocalproblemrestrictionsbqp-completecompletedemonstratedkarp
read the original abstract
In this note we present two natural restrictions of the local Hamiltonian problem which are BQP-complete under Karp reduction. Restrictions complete for QCMA, QMA_1, and MA were demonstrated previously.
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.