Accepted author manuscript, 321 KB, PDF document
Available under license: CC BY-NC: Creative Commons Attribution-NonCommercial 4.0 International License
Final published version
Final published version
Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Conference contribution/Paper › peer-review
Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Conference contribution/Paper › peer-review
}
TY - GEN
T1 - Reducing Binary Quadratic Forms for More Scalable Quantum Annealing
AU - Hahn, Georg
AU - Djidjev, Hristo
AU - Djidjev, Hristo N.
PY - 2017
Y1 - 2017
N2 - Recent advances in the development of commercial quantum annealers such as the D-Wave 2X allow solving NP-hard optimization problems that can be expressed as quadratic unconstrained binary programs. However, the relatively small number of available qubits (around 1000 for the D-Wave 2X quantum annealer) poses a severe limitation to the range of problems that can be solved. This paper explores the suitability of preprocessing methods for reducing the sizes of the input programs and thereby the number of qubits required for their solution on quantum computers. Such methods allow us to determine the value of certain variables that hold in either any optimal solution (called strong persistencies) or in at least one optimal solution (weak persistencies). We investigate preprocessing methods for two important NP-hard graph problems, the computation of a maximum clique and a maximum cut in a graph. We show that the identification of strong and weak persistencies for those two optimization problems is very instance-specific, but can lead to substantial reductions in the number of variables.
AB - Recent advances in the development of commercial quantum annealers such as the D-Wave 2X allow solving NP-hard optimization problems that can be expressed as quadratic unconstrained binary programs. However, the relatively small number of available qubits (around 1000 for the D-Wave 2X quantum annealer) poses a severe limitation to the range of problems that can be solved. This paper explores the suitability of preprocessing methods for reducing the sizes of the input programs and thereby the number of qubits required for their solution on quantum computers. Such methods allow us to determine the value of certain variables that hold in either any optimal solution (called strong persistencies) or in at least one optimal solution (weak persistencies). We investigate preprocessing methods for two important NP-hard graph problems, the computation of a maximum clique and a maximum cut in a graph. We show that the identification of strong and weak persistencies for those two optimization problems is very instance-specific, but can lead to substantial reductions in the number of variables.
KW - MAXIMUM CLIQUE
M3 - Conference contribution/Paper
SN - 9781538615546
SP - 138
EP - 145
BT - Rebooting Computing (ICRC), 2017 IEEE International Conference on
PB - IEEE
T2 - IEEE International Conference on Rebooting Computing (ICRC)
Y2 - 8 November 2017 through 9 November 2017
ER -