Graph Minor Embeddings for D-Wave Computer Architecture

Show simple item record

dc.contributor.author Yang, Z en
dc.contributor.author Dinneen, MJ en
dc.date.accessioned 2017-02-07T03:37:18Z en
dc.date.available 2017-02-07T03:37:18Z en
dc.date.issued 2016 en
dc.identifier.citation CDMTCS Research Reports CDMTCS-503 (2016) en
dc.identifier.issn 1178-3540 en
dc.identifier.uri http://hdl.handle.net/2292/31760 en
dc.description.abstract The D-Wave system architecture is designed to deal with quantum annealing to solve computational problems. To run or solve a problem by the D-Wave hardware, we need to rst transform the problem into an Ising or Quadratic Unconstrained Binary Optimization (QUBO) instance, then embed Hamiltonians (logical qubit relationships) onto the actual D-Wave hardware which is currently based on Chimera graphs (physical qubit couplings). In order to have better performance of D-Wave's quantum annealing, an efficient algorithm to nd good embeddings needs to be obtained. In this paper, we present some heuristic algorithms for minor embedding an arbitrary guest graph onto a host Chimera graph. Our implementations show these new algorithms are practical for sparse graphs with hundreds of vertices. In general, for a given minor embedding, we tried to minimize the maximum number physical qubits representing by any logical qubit and/or the total number of physical qubits used. en
dc.publisher Department of Computer Science, The University of Auckland, New Zealand en
dc.relation.ispartofseries CDMTCS Research Report Series en
dc.rights Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher. en
dc.rights.uri https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm en
dc.source.uri https://www.cs.auckland.ac.nz/research/groups/CDMTCS/researchreports/index.php en
dc.title Graph Minor Embeddings for D-Wave Computer Architecture en
dc.type Technical Report en
dc.subject.marsden Fields of Research en
dc.rights.holder The author(s) en
dc.rights.accessrights http://purl.org/eprint/accessRights/OpenAccess en


Files in this item

Find Full text

This item appears in the following Collection(s)

Show simple item record

Share

Search ResearchSpace


Browse

Statistics