dc.contributor.author |
Dinneen, MJ |
en |
dc.contributor.author |
Hua, R |
en |
dc.date.accessioned |
2017-02-07T03:37:16Z |
en |
dc.date.available |
2017-02-07T03:37:16Z |
en |
dc.date.issued |
2016 |
en |
dc.identifier.citation |
CDMTCS Research Reports CDMTCS-495 (2016) |
en |
dc.identifier.issn |
1178-3540 |
en |
dc.identifier.uri |
http://hdl.handle.net/2292/31752 |
en |
dc.description.abstract |
We provide efficient quadratic unconstrained binary optimization (QUBO) formulations for the Dominating Set and Edge Cover combinatorial problems suitable for adiabatic quantum computers, which are viewed as a real-world enhanced model of simulated annealing (e.g. a type of genetic algorithm with quantum tunneling). The number of qubits (dimension of QUBO matrices) required to solve these set cover problems are O(n+n lg n) and O(m+n lg n) respectively, where n is the number of vertices and m is the number of edges. We also extend our formulations for the Minimum Vertex-Weighted Dominating Set problem and Minimum Edge-Weighted Edge Cover problem. Experimental results for the Dominating Set and Edge Cover problems using a D-Wave Systems quantum computer with 1098 active qubit-coupled processors are also provided for a selection of known common graphs. |
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 |
Formulating Graph Covering Problems for Adiabatic Quatumn Computers |
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 |
dc.relation.isnodouble |
1125731 |
* |