A Caltech Library Service

Computational overhead of locality reduction in binary optimization problems

Valiante, Elisabetta and Hernandez, Maritza and Barzegar, Amin and Katzgraber, Helmut G. (2021) Computational overhead of locality reduction in binary optimization problems. Computer Physics Communications . Art. No. 108102. ISSN 0010-4655. doi:10.1016/j.cpc.2021.108102.

[img] PDF - Accepted Version
See Usage Policy.

[img] PDF (arXiv) - Accepted Version
See Usage Policy.


Use this Persistent URL to link to this item:


Recently, there has been considerable interest in solving optimization problems by mapping these onto a binary representation, sparked mostly by the use of quantum annealing machines. Such binary representation is reminiscent of a discrete physical two-state system, such as the Ising model. As such, physics-inspired techniques—commonly used in fundamental physics studies—are ideally suited to solve optimization problems in a binary format. While binary representations can be often found for paradigmatic optimization problems, these typically result in k-local higher-order unconstrained binary optimization cost functions. In this work, we discuss the effects of locality reduction needed for the majority of the currently available quantum and quantum-inspired solvers that can only accommodate 2-local (quadratic) cost functions. General locality reduction approaches require the introduction of ancillary variables which cause an overhead over the native problem. Using a parallel tempering Monte Carlo solver on Microsoft Azure Quantum, as well as k-local binary problems with planted solutions, we show that post reduction to a corresponding 2-local representation the problems become considerably harder to solve. We further quantify the increase in computational hardness introduced by the reduction algorithm by measuring the variation of number of variables, statistics of the coefficient values, and the population annealing entropic family size. Our results demonstrate the importance of avoiding locality reduction when solving optimization problems.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Valiante, Elisabetta0000-0003-3820-7851
Barzegar, Amin0000-0001-6346-8047
Katzgraber, Helmut G.0000-0003-3341-9943
Alternate Title:Scaling overhead of locality reduction in binary optimization problems
Additional Information:© 2021 Elsevier B.V. Received 10 January 2021, Revised 6 July 2021, Accepted 15 July 2021, Available online 24 July 2021. The review of this paper was arranged by Prof. Weigel Martin. The work of H. G. K. was performed before joining Amazon Web Services. We thank the two anonymous referees for their insightful comments and valuable suggestions that allowed us to considerably improve our analysis. We thank Marko Bucyk for his careful editing and reviewing of the manuscript. H. G. K. would like to thank David Poulin for inspiring discussions and dedicate this manuscript to him. The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.
Group:AWS Center for Quantum Computing
Record Number:CaltechAUTHORS:20210817-163653912
Persistent URL:
Official Citation:Elisabetta Valiante, Maritza Hernandez, Amin Barzegar, Helmut G. Katzgraber, Computational overhead of locality reduction in binary optimization problems, Computer Physics Communications, Volume 269, 2021, 108102, ISSN 0010-4655,
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:110292
Deposited By: Tony Diaz
Deposited On:18 Aug 2021 21:50
Last Modified:18 Aug 2021 21:50

Repository Staff Only: item control page