Practical integer-to-binary mapping for quantum annealers
Practical integer-to-binary mapping for quantum annealers
复制标题
量子退火器的实用整数到二进制映射
DOI：
10.1007/s11128-019-2213-x
复制
发表时间：
2017
影响因子：
2.5
通讯作者：
Pooya Ronagh
中科院分区：
文献类型：
--
作者：
S. Karimi;Pooya Ronagh
量子退火硬件的最新进展和这一领域的大量研究表明，量子退火器有可能有效地解决无约束二进制二次规划问题。自然，人们可能希望将这些机器的应用领域扩展到一般离散变量的问题。在本文中，我们探讨了利用量子退火器来解决有界整数域上的无约束二次规划问题的可能性。我们提出了一种方法将整数变量编码成二进制变量，从而将无约束整数二次规划问题表示为无约束二进制二次规划问题。为了尊重目前开发的量子退火机的一些限制，我们提出了一种整数编码，称为有界系数编码，其中我们限制了编码中出现的系数的大小。此外，我们提出了一种算法，用于找到上界的系数的编码使用的机器和原始整数问题的系数的精度。我们的实验表明，这种方法是更有弹性的量子退火机的噪声相比，传统的方法编码的整数在基地2。此外，我们进行时间到解决方案的各种整数编码策略的分析，相对于整数规划问题的大小，并观察到良好的性能，从有界系数编码相对于一元和二进制编码。
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.