Scaling Overhead of Locality Reduction in Binary Optimization Problems

By Elisabetta Valiante, Maritza Hernandez, Amin Barzegar, & Helmut G. Katzgraber
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 solvers such as the D-Wave quantum annealer, the Fujitsu Digital Annealer, or the Toshiba Simulated Bifurcation Machine 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 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 entropic family size. Our results demonstrate the importance of avoiding locality reduction when solving optimization problems.

Most Recent Papers

Quantum Multiple Kernel Learning

By Seyed Shakib Vedaie, Moslem Noori, Jaspreet S. Oberoi, Barry C. Sanders, & Ehsan Zahedinejad Kernel methods play an important role in machine learning applications due to their conceptual simplicity and superior performance on numerous machine learning tasks....

Quantum Algorithms for Solving Dynamic Programming Problems

By Pooya RonaghWe present a general quantum algorithm for solving finite-horizon dynamic programming problems. Up to polylogarithmic factors, our algorithm provides a quadratic quantum advantage in terms of the number of states of a given dynamic programming problem....