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

Understand

We describe an efficient 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/epsilon, where epsilon 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 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.