On complexity of the quantum Ising model
arXiv:1410.0703
Abstract
We study complexity of several problems related to the Transverse field Ising Model (TIM). First, we consider the problem of estimating the ground state energy known as the Local Hamiltonian Problem (LHP). It is shown that the LHP for TIM on degree-3 graphs is equivalent modulo polynomial reductions to the LHP for general k-local `stoquastic' Hamiltonians with any constant . This result implies that estimating the ground state energy of TIM on degree-3 graphs is a complete problem for the complexity class StoqMA - an extension of the classical class MA. As a corollary, we complete the complexity classification of 2-local Hamiltonians with a fixed set of interactions proposed recently by Cubitt and Montanaro. Secondly, we study quantum annealing algorithms for finding ground states of classical spin Hamiltonians associated with hard optimization problems. We prove that the quantum annealing with TIM Hamiltonians is equivalent modulo polynomial reductions to the quantum annealing with a certain subclass of k-local stoquastic Hamiltonians. This subclass includes all Hamiltonians representable as a sum of a k-local diagonal Hamiltonian and a 2-local stoquastic Hamiltonian.
arXiv comment48 pages, 8 figures
References in corpus (10)
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- Quantum annealing with more than one hundred qubits
- Computational Complexity of interacting electrons and fundamental limitations of Density Functional Theory
- Topological Entanglement Entropy of a Bose-Hubbard Spin Liquid
- The power of quantum systems on a line
- Simulation of Many-Body Hamiltonians using Perturbation Theory with Bounded-Strength Interactions
- Universal Signatures of Fractionalized Quantum Critical Points
- Cavity method for quantum spin glasses on the Bethe lattice
- Complexity classification of local Hamiltonian problems
- Perturbative gadgets without strong interactions