Toward Quantum Gate-Model Heuristics for Real-World Planning Problems
Toward Quantum Gate-Model Heuristics for Real-World Planning Problems
复制标题
针对现实世界规划问题的量子门模型启发式
DOI：
--
复制
发表时间：
2020
影响因子：
--
通讯作者：
Zhihui Wang
中科院分区：
文献类型：
--
作者：
T. Stollenwerk;Stuart Hadfield;Zhihui Wang
许多具有挑战性的调度，规划和资源分配问题都带有真实世界的输入数据和硬问题约束，并简化为在组合定义的可行集上优化成本函数，例如图的着色。为了解决量子计算机使用量子近似优化算法的问题，我们提出了新的有效的量子交替算子animals（QAOA）的弦图的适当着色的优化问题的建设。作为我们的主要应用程序，我们考虑的航班登机口分配问题，其中航班被分配到机场登机口，以尽量减少所有乘客的总过境时间，和可行的分配对应于适当的图形着色的冲突图从输入数据中派生的实例。我们利用经典算法和图论的思想来证明我们的构造具有将量子态演化限制在可行子空间的理想特性，并且满足大多数问题参数制度的特定可达性条件。利用经典的预处理，我们表明，我们总是可以找到并构造一个合适的初始量子（叠加）态有效。我们详细展示了我们的构造，包括对一组通用的基本量子门的显式分解，我们使用它来将所需的资源缩放绑定为输入参数的低次多项式。特别是，我们得到新的QAOA混合运营商，并表明其实施成本是相称的QAOA相位运营商的飞行门分配。包括一些量子电路图，使得我们的构造可以用作模板，用于开发和实现量子门模型方法，用于更广泛的潜在影响力的现实世界应用。
Many challenging scheduling, planning, and resource allocation problems come with real-world input data and hard problem constraints, and reduce to optimizing a cost function over a combinatorially defined feasible set, such as colorings of a graph. Toward tackling such problems with quantum computers using quantum approximate optimization algorithms, we present novel efficient quantum alternating operator ansatz (QAOA) constructions for optimization problems over proper colorings of chordal graphs. As our primary application, we consider the flight-gate assignment problem, where flights are assigned to airport gates as to minimize the total transit time of all passengers, and feasible assignments correspond to proper graph colorings of a conflict graph derived instancewise from the input data. We leverage ideas from classical algorithms and graph theory to show our constructions have the desirable properties of restricting quantum state evolution to the feasible subspace, and satisfying a particular reachability condition for most problem parameter regimes. Using classical preprocessing we show that we can always find and construct a suitable initial quantum (superposition) state efficiently. We show our constructions in detail, including explicit decompositions to a universal set of basic quantum gates, which we use to bound the required resource scaling as low-degree polynomials of the input parameters. In particular, we derive novel QAOA mixing operators and show that their implementation cost is commensurate with that of the QAOA phase operator for flight-gate assignment. A number of quantum circuit diagrams are included such that our constructions may be used as a template toward development and implementation of quantum gate-model approaches for a wider variety of potentially impactful real-world applications.