# Computational Complexity of random Transverse-Ising Chain

It is well known that many NP-hard classical problems can be mapped to a spin-configuration Ising problem (see for example https://arxiv.org/pdf/1302.5843.pdf)

However, what I would like to know is what is the complexity of finding the ground state energy when extra transverse fields are added. For example, consider a $$n$$-qubit system interacting under the Hamiltonian: $$\begin{equation} H = \sum_{\langle i,j \rangle \in E} J_{ij} \sigma_i^z \sigma_j^z + \sum_{i=1}^n h_i \sigma_i^x \end{equation}$$ where $$E$$ corresponds to the set of edges (i.e. whether node $$i$$ and $$j$$ are connected) and $$J_{ij}$$ and $$h_i$$ are coupling strength coefficients. More importantly, what I am mostly interested is what happens when the Hamiltonian above is restricted to nearest-neighbor interactions:

$$\begin{equation} H = \sum_{i=1}^n J_{ij} \sigma_i^z \sigma_{i+1}^z + \sum_{i=1}^n h_i \sigma_i^x \end{equation}$$

Is finding the ground state energy as hard as in a qubit-system where the connections are described by a graph $$G$$ (for example a 3-regular graph). Also, do we know if these random Transverse Ising Chains are gapped? For example can an Adiabatic Quantum Computer solve these kind of problems?

• If your first Hamiltonian is on a 3-local graph, is your second Hamiltonian on a (two-local) cycle graph? Feb 25 at 3:15