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

被引：6

作者：

Hall, J. S. ^{[1
]}

Novotny, M. A. ^{[1
]}

Neuhaus, T. ^{[2
]}

Michielsen, Kristel ^{[2
]}

机构：

[1] Mississippi State Univ, 75 BS Hood Dr, Mississippi State, MS 39762 USA

[2] Res Ctr Julich, Julich Supercomp Ctr, Inst Adv Simulat, D-52425 Julich, Germany

来源：

PROCEEDINGS OF THE 28TH WORKSHOP ON COMPUTER SIMULATION STUDIES IN CONDENSED MATTER PHYSICS (CSP2015) | 2015年 / 68卷

基金：

美国国家科学基金会;

关键词：

D-Wave; Spanning Tree; Chimera; Quantum Computer; Quantum Computing;

D O I：

10.1016/j.phpro.2015.07.109

中图分类号：

O59 [应用物理学];

学科分类号：

摘要：

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 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) = +/- 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 J(i,j) = {- 1,1} and h(j) = 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. (C) 2015 The Authors. Published by Elsevier B.V.

引用

页码：56 / 60

页数：5

共 11 条

[1]

[Anonymous], 2011, QUANTUM COMPUTING GE, DOI DOI 10.1063/PT.3.1442

[2] Discrete optimization using quantum annealing on sparse Ising models [J].

Bian, Zhengbing ;

Chudak, Fabian ;

Israel, Robert ;

Lackey, Brad ;

Macready, William G. ;

Roy, Aidan .

FRONTIERS IN PHYSICS, 2014, 2 :1-10

[3]

Boixo S, 2014, NAT PHYS, V10, P218, DOI [10.1038/nphys2900, 10.1038/NPHYS2900]

[4] GENERATING RANDOM SPANNING-TREES [J].

BRODER, A .

30TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, 1989, :442-447

[5]

Hen I, ARXIV150201663V2

[6] Quantum annealing with manufactured spins [J].

Johnson, M. W. ;

Amin, M. H. S. ;

Gildert, S. ;

Lanting, T. ;

Hamze, F. ;

Dickson, N. ;

Harris, R. ;

Berkley, A. J. ;

Johansson, J. ;

Bunyk, P. ;

Chapple, E. M. ;

Enderud, C. ;

Hilton, J. P. ;

Karimi, K. ;

Ladizinsky, E. ;

Ladizinsky, N. ;

Oh, T. ;

Perminov, I. ;

Rich, C. ;

Thom, M. C. ;

Tolkacheva, E. ;

Truncik, C. J. S. ;

Uchaikin, S. ;

Wang, J. ;

Wilson, B. ;

Rose, G. .

NATURE, 2011, 473 (7346) :194-198

[7] Entanglement in a Quantum Annealing Processor [J].

Lanting, T. ;

Przybysz, A. J. ;

Smirnov, A. Yu. ;

Spedalieri, F. M. ;

Amin, M. H. ;

Berkley, A. J. ;

Harris, R. ;

Altomare, F. ;

Boixo, S. ;

Bunyk, P. ;

Dickson, N. ;

Enderud, C. ;

Hilton, J. P. ;

Hoskinson, E. ;

Johnson, M. W. ;

Ladizinsky, E. ;

Ladizinsky, N. ;

Neufeld, R. ;

Oh, T. ;

Perminov, I. ;

Rich, C. ;

Thom, M. C. ;

Tolkacheva, E. ;

Uchaikin, S. ;

Wilson, A. B. ;

Rose, G. .

PHYSICAL REVIEW X, 2014, 4 (02)

[8] CHOOSING A SPANNING TREE FOR THE INTEGER LATTICE UNIFORMLY [J].

PEMANTLE, R .

ANNALS OF PROBABILITY, 1991, 19 (04) :1559-1574

[9] A case study in programming a quantum annealer for hard operational planning problems [J].

Rieffel, Eleanor G. ;

Venturelli, Davide ;

O'Gorman, Bryan ;

Do, Minh B. ;

Prystay, Elicia M. ;

Smelyanskiy, Vadim N. .

QUANTUM INFORMATION PROCESSING, 2015, 14 (01) :1-36

[10] Defining and detecting quantum speedup [J].

Ronnow, Troels F. ;

Wang, Zhihui ;

Job, Joshua ;

Boixo, Sergio ;

Isakov, Sergei V. ;

Wecker, David ;

Martinis, John M. ;

Lidar, Daniel A. ;

Troyer, Matthias .

SCIENCE, 2014, 345 (6195) :420-424

← 1 2 →