Investigations of a D-Wave Two: Ground States of Random Spanning Trees*

The performance of a 496 qubit D-Wave Two quantum computer was investigated for two problems. The chip has a Chimera interaction graph G, an 8x8 lattice of clusters of 8 qubits. 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 G. Output is returned in terms of a spin configuration $\{s_j\}$, with $s_j$$=$$\pm 1$. We investigated spanning tree problems. A tree is a connected, undirected subgraph of G that contains no cycles, and a spanning tree is a tree which includes all of the vertices of G. We generated random spanning trees (RSTs), uniformly distributed over all spanning trees of G. In the first study, 100 RSTs with random $J_{i,j}$$\in$$\{-1,1\}$ and $h_j=0$ were generated on the full 8x8 graph G of the chip. Each RST problem was solved up to 100 times and the number of times the ground state energy was found was recorded. This procedure was repeated for square subgraphs G', with dimensions ranging from 2x2 to 7x7. In the second study, the ground state was randomly chosen to be $s_j$$=$$\pm 1$, the $J_{i,j}$ and $h_j$ strengths were calculated from a quadratic Hamiltonian that had the given ground state, and the probability that the D-Wave Two found the ground state was measured.