3-local Hamiltonian is QMA-complete

Julia Kempe, Oded Regev

Research output: Contribution to journalArticle

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 languageEnglish (US)
Pages (from-to)258-264
Number of pages7
JournalQuantum Information and Computation
Volume3
Issue number3
StatePublished - 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
  • Physics and Astronomy(all)
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of '3-local Hamiltonian is QMA-complete'. Together they form a unique fingerprint.

  • Cite this