Practical integer-to-binary mapping for quantum annealers

Abstract

Recent advancements in quantum annealing hardware and numerous studies in this area suggest that quantum annealers have the potential to be effective in solving unconstrained binary quadratic programming problems. Naturally, one may desire to expand the application domain of these machines to problems with general discrete variables. In this paper, we explore the possibility of employing quantum annealers to solve unconstrained quadratic programming problems over a bounded integer domain. We present an approach for encoding integer variables into binary ones, thereby representing unconstrained integer quadratic programming problems as unconstrained binary quadratic programming problems. To respect some of the limitations of the currently developed quantum annealers, we propose an integer encoding, named bounded-coefficient encoding, in which we limit the size of the coefficients that appear in the encoding. Furthermore, we propose an algorithm for finding the upper bound on the coefficients of the encoding using the precision of the machine and the coefficients of the original integer problem. We experimentally show that this approach is far more resilient to the noise of the quantum annealers compared to traditional approaches for the encoding of integers in base two. In addition, we perform time-to-solution analysis of various integer encoding strategies with respect to the size of integer programming problems and observe favorable performance from the bounded-coefficient encoding relative to that of the unary and binary encodings.