Graph states as ground states of many-body spin-$1∕2$ Hamiltonians

We consider the problem of whether graph states can be ground states of local interaction Hamiltonians. For Hamiltonians acting on $n$ qubits that involve at most two-body interactions, we show that no $n$-qubit graph state can be the exact, nondegenerate ground state. We determine for any graph state the minimal $d$ such that it is the nondegenerate ground state of a $d$-body interaction Hamiltonian, while we show for $d^{\prime }$-body Hamiltonians $H$ with $d^{\prime }<d$ that the resulting ground state can only be close to the graph state at the cost of $H$ having a small energy gap relative to the total energy. When allowing for ancilla particles, we show how to utilize a gadget construction introduced in the context of the $k$-local Hamiltonian problem, to obtain $n$-qubit graph states as nondegenerate (quasi)ground states of a two-body Hamiltonian acting on $n^{\prime }>n$ spins.

Figure 1

(Color online) Interaction diagram of a two-body Hamiltonian with the linear cluster state as the ground state. The original qubits are shown in dark gray and the light gray qubits are the added ancilla qubits.

Figure 2

(Color online) Illustration of the reduction of (a) a single four-qubit interaction term ${\sigma }_x^{\left(i\right)}{\sigma }_z^{\left(i_a\right)}{\sigma }_z^{\left(i_b\right)}{\sigma }_z^{\left(i_c\right)}$ to (b) two three-body terms ${\sigma }_x^{\left(i\right)}{\sigma }_z^{\left(i_a\right)}{\sigma }_x^{\left(i_7\right)}$ and ${\sigma }_z^{\left(i_b\right)}{\sigma }_z^{\left(i_c\right)}{\sigma }_x^{\left(i_7\right)}$ using one ancilla qubit $i_7$ and a strong single body term, $\mid 1⟩⟨1{\mid }^{\left(i_7\right)}$. (c) Further reduction to two-qubit interactions of each of the three-body terms with help of three ancilla particles $(i_1,i_2,i_3)$ and $(i_4,i_5,i_6)$, respectively.