REVIEW 5 cited by
The Complexity of the Local Hamiltonian Problem
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
The Complexity of the Local Hamiltonian Problem
read the original abstract
The k-local Hamiltonian problem is a natural complete problem for the complexity class QMA, the quantum analog of NP. It is similar in spirit to MAX-k-SAT, which is NP-complete for k<=2. It was known that the problem is QMA-complete for any k <= 3. On the other hand 1-local Hamiltonian is in P, and hence not believed to be QMA-complete. The complexity of the 2-local Hamiltonian problem has long been outstanding. Here we settle the question and show that it is QMA-complete. We provide two independent proofs; our first proof uses only elementary linear algebra. Our second proof uses a powerful technique for analyzing the sum of two Hamiltonians; this technique is based on perturbation theory and we believe that it might prove useful elsewhere. Using our techniques we also show that adiabatic computation with two-local interactions on qubits is equivalent to standard quantum computation.
Forward citations
Cited by 5 Pith papers
-
Convergence rates of Sum-of-Hermitian-Squares Hierarchies for the Pauli algebra
Explicit convergence rates for noncommutative SOS hierarchies on the Pauli algebra are bounded using smallest roots of Krawtchouk polynomials.
-
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...
-
Non-Hermitian Quantum Adiabatic Algorithm
A history-decoupled Hamiltonian mapping makes non-Hermitian adiabatic quantum optimization pseudospectrally stable, achieving polynomial-time (per configuration) evolution on the CK maximum-independent-set benchmarks.
-
Universality of Quantum Gates in Particle and Symmetry Constrained Subspaces
Hardware-efficient gates are universal for state preparation in particle-number and symmetry-constrained subspaces because commutators generate Pauli Z projectors that span the full so(w) and su(w) algebras.
-
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.