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.
Original language | English (US) |
---|---|
Pages (from-to) | 258-264 |
Number of pages | 7 |
Journal | Quantum Information and Computation |
Volume | 3 |
Issue number | 3 |
State | Published - May 2003 |
Keywords
- Complete problems
- Local Hamiltonian problem
- QMA
ASJC Scopus subject areas
- Theoretical Computer Science
- Statistical and Nonlinear Physics
- Nuclear and High Energy Physics
- Mathematical Physics
- General Physics and Astronomy
- Computational Theory and Mathematics