Ground States of Random Spanning Trees on a D-Wave 2X

The performances of two D-Wave 2 machines (476 and 496 qubits) and of a 1097-qubit D-Wave 2X were investigated. Each chip has a Chimera interaction graph ${\cal G}$. Problem input consists of values for the fields $h_j$ and for the two-qubit interactions $J_{i,j}$ of an Ising spin-glass problem formulated on ${\cal G}$. Output is returned in terms of a spin configuration $\{s_j\}$, with $s_j$$=$$\pm 1$. We generated random spanning trees (RSTs) uniformly distributed over all spanning trees of ${\cal G}$. On the 476-qubit D-Wave 2, RSTs were generated on the full chip with $J_{i,j}=-1$ and $h_j=0$ and solved one thousand times. The distribution of solution energies and the average magnetization of each qubit were determined. On both the 476- and 1097-qubit machines, four identical spanning trees were generated on each quadrant of the chip. The statistical independence of these regions was investigated. In another study, on the D-Wave 2X, one hundred RSTs with random $J_{i,j}$$\in$$\{-1,1\}$ and $h_j=0$ were generated on the full chip. Each RST problem was solved one hundred times and the number of times the ground state energy was found was recorded. This procedure was repeated for square subgraphs, with dimensions ranging from $7$$\times$$7$ to $11$$\times$$11$.