A Study of Spanning Trees on a D-Wave Quantum Computer

Hall, J. S.; Michielsen, Kristel; Neuhaus, T.; Novotny, M. A.

doi:10.1016/j.phpro.2015.07.109

Journal Article

FZJ-2015-05452

A Study of Spanning Trees on a D-Wave Quantum Computer

Hall, J. S. ; Novotny, M. A. (Corresponding author) ; Neuhaus, T.FZJ* ; Michielsen, K.FZJ*

2015
Elsevier Amsterdam [u.a.]

Physics procedia 68, 56 - 60 (2015) [10.1016/j.phpro.2015.07.109]

This record in other databases:

Please use a persistent id in citations: http://hdl.handle.net/2128/9348 doi:10.1016/j.phpro.2015.07.109

Abstract: The performance of a 496 qubit D-Wave Two quantum computer was investigated for spanning tree problems. The chip has a Chimera interaction graph G, an 8x8 lattice of clusters of eight qubits. Problem input consists of values for the fields hj and for the two-qubit interactions Ji,j of an Ising spin-glass problem formulated on G. Output is returned in terms of a spin configuration {sj}, with sj = ±1. 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. One hundred RSTs with random Ji,j = {-1,1} and hj = 0 were generated on the full 8x8 graph G of the chip. Each RST problem was solved up to one hundred times and the number of times the ground state energy was found was recorded. This procedure was repeated for square subgraphs G′, thereby providing results for portions of the chip with dimensions ranging from 2x2 to 8x8.

Classification: