Compiling Planning into Quantum Optimization Problems: A Comparative Study
Compiling Planning into Quantum Optimization Problems: A Comparative Study
复制标题
将规划编译成量子优化问题：比较研究
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
J. Frank
中科院分区：
文献类型：
--
作者：
B. O’Gorman;E. Rieffel;M. Do;D. Venturelli;J. Frank
摘要：解决规划问题的一种方法是将它们编译成另一个问题，对于这个问题，可以使用强大的现成求解器;常见的目标包括SAT，CSP和MILP。最近，一种新的优化技术已经变得可用：量子退火（QA）。QA将编码为二次无约束二进制优化（QUBO）的问题实例作为输入。早期的量子退火机现已上市，未来几十年可能会建造更复杂的量子退火机。特定的量子退火硬件实现具有特定的约束，限制了每个可以作为输入的QUBO的类型。在本文中，我们将规划社区介绍到将规划问题编译到量子退火硬件中所涉及的关键步骤：独立于硬件的步骤，映射和依赖于硬件的步骤，嵌入。在描述了两种方法来映射一般的规划问题QUBO，我们提供了初步的结果，从运行早期的量子退火机上的参数化家庭的硬规划问题。结果表明，不同的映射可能会导致性能上的实质性差异，即使结果实例的许多表面特征是相似的。我们还提供了一些见解，从这个早期的研究，并建议未来的工作方向。
Abstract : One approach to solving planning problems is to compile them to another problem for which powerful off-the-shelf solvers are available; common targets include SAT, CSP, and MILP. Recently, a novel optimization technique has become available: quantum annealing (QA). QA takes as input problem instances encoded as Quadratic Unconstrained Binary Optimization (QUBO). Early quantum annealers are now available, and more sophisticated quantum annealers will likely be built over the next decades. Specific quantum annealing hardware implementations have specific constraints, restricting the types of QUBOs each can take as input. In this paper, we introduce the planning community to the key steps involved in compiling planning problems to quantum annealing hardware: a hardware-independent step, mapping, and a hardware-dependent step, embedding. After describing two approaches to mapping general planning problems to QUBO, we provide preliminary results from running an early quantum annealer on a parameterized family of hard planning problems. The results show that different mappings can lead to a substantial difference in performance, even when many superficial features of the resulting instances are similar. We also provide some insights gained from this early study, and suggest directions for future work.