Physics – Quantum Physics
Scientific paper
2005-04-07
Quant. Inf, Comp. Vol. 8, No. 10, pp. 0900-0924 (2008)
Physics
Quantum Physics
19 pages, 12 figures; v2 has 23 pages, 12 figures and some additional results in an appendix. The presentation in v3 is change
Scientific paper
The problem 2-LOCAL HAMILTONIAN has been shown to be complete for the quantum computational class QMA, see quant-ph/0406180. 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.
Oliveira Roberto
Terhal Barbara M.
No associations
LandOfFree
The complexity of quantum spin systems on a two-dimensional square lattice does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The complexity of quantum spin systems on a two-dimensional square lattice, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The complexity of quantum spin systems on a two-dimensional square lattice will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-362762