Polynomial-time algorithm for simulation of weakly interacting quantum spin systems

Understand

We describe an algorithm that computes the ground state energy and correlation functions for 2-local Hamiltonians in which interactions between qubits are weak compared to single-qubit terms.

• The running time of the algorithm is polynomial in the number of qubits and the required precision.
• Specifically, we consider Hamiltonians of the form $H=H_0+\epsilon V$, where H_0 describes non-interacting qubits, V is a perturbation that involves arbitrary two-qubit interactions on a graph of bounded degree, and $\epsilon$ is a small parameter.
• The algorithm works if $|\epsilon|$ is below a certain threshold value that depends only upon the spectral gap of H_0, the maximal degree of the graph, and the maximal norm of the two-qubit interactions.