the complexity of quantum spin systems on a two dimensional square lattice

• DOI: 10.5555/2016985.2016987
• Publication Date: 2008-11-01
• Authors: Barbara M. Terhal; Roberto I. Oliveira
• Keywords: Quantum Physics; 0103 physical sciences; FOS: Physical sciences; Quantum Physics (quant-ph); 01 natural sciences

The problem 2-LOCAL HAMILTONIAN has been shown to be complete for the quantum computational class QMA. In this paper we show that this important problem remains QMA-complete when the interactions of the 2-local Hamiltonian are between qubits on a two-dimensional (2-D) square lattice. Our results are partially derived with novel perturbation gadgets that employ mediator qubits which allow us to manipulate k-local interactions. As a side result, we obtain that quantum adiabatic computation using 2-local interactions restricted to a 2-D square lattice is equivalent to the circuit model of quantum computation. Our perturbation method also shows how any stabilizer space associated with a k-local stabilizer (for constant k) can be generated as an approximate ground-space of a 2-local Hamiltonian.