Classical approximation schemes for the ground-state energy of quantum and classical ising spin hamiltonians on planar graphs

Nikhil Bansal, Sergey Bravyi, Barbara M. Terhal

Research output: Contribution to journalArticleScientificpeer-review

12 Citations (Scopus)

Abstract

We describe a classical approximation algorithm for evaluating the ground state energy of the classical Ising Hamiltonian with linear terms on an arbitrary planar graph. The running time of the algorithm grows linearly with the number of spins and exponentially with 1/ε, where ε is the worst-case relative error. This result contrasts the well known fact that exact computation of the ground state energy for the two-dimensional Ising spin glass model is NP-hard. We also present a classical approximation algorithm for the quantum Local Hamiltonian Problem or Quantum Ising Spin Glass problem on a planar graph with bounded degree which is known to be a QMA-complete problem. Using a different technique we find a classical approximation algorithm for the quantum Ising spin glass problem on the simplest planar graph with unbounded degree, the star graph.
Original languageEnglish
Pages (from-to)701-720
Number of pages20
JournalQuantum Information and Computation
Volume9
Issue number7-8
Publication statusPublished - 2009
Externally publishedYes

Fingerprint Dive into the research topics of 'Classical approximation schemes for the ground-state energy of quantum and classical ising spin hamiltonians on planar graphs'. Together they form a unique fingerprint.

Cite this