论文标题
部分可观测时空混沌系统的无模型预测
Open-Shop Scheduling With Hard Constraints
论文作者
论文摘要
将硬性约束优化问题编码为各种量子算法通常是一项具有挑战性的任务。在这项工作中，我们为开放购物计划问题（OSSP）提供了一个解决方案，我们通过严格地采用经典问题的对称性来实现这些解决方案。 Hadfield等人的量子交替的操作员Ansatz（QAOA）最近给出了一种既定的方法，用于编码密切相关的旅行销售人员问题（TSP）的硬性约束。对于包含TSP作为特殊情况的OSSP，我们表明，类似构造的混合器的所需属性可以直接链接到一个纯粹的经典对象：具有可行性的比特值排列。我们还概述了为这些问题构造类似QAOA的混合物的通用方法。我们进一步提出了一种新的变分量子算法，该算法更自然地结合了基础组的结构，并在IBM Q系统ONE上实现了一个小的OSSP实例的新算法。与QAOA不同，我们的算法允许从上面达到每个可行解决方案所需的数量和域：如果要分发$ j $ jobs，我们最多需要$ j（j -1）^{2} / {2} / {2} $参数。
Encoding hard constrained optimization problems into a variational quantum algorithm often turns out to be a challenging task. In this work, we provide a solution for the class of open-shop scheduling problems (OSSP), which we achieve by rigorously employing the symmetries of the classical problem. An established approach for encoding the hard constraints of the closely related traveling salesperson problem (TSP) into mixer Hamiltonians was recently given by Hadfield et al.'s Quantum Alternating Operator Ansatz (QAOA). For OSSP, which contains TSP as a special case, we show that desired properties of similarly constructed mixers can be directly linked to a purely classical object: the group of feasibility-preserving bit value permutations. We also outline a generic way to construct QAOA-like-mixers for these problems. We further propose a new variational quantum algorithm that incorporates the underlying group structure more naturally, and implement our new algorithm for a small OSSP instance on an IBM Q System One. Unlike the QAOA, our algorithm allows bounding the amount and the domain of parameters necessary to reach every feasible solution from above: If $J$ jobs should be distributed, we need at most $J (J - 1)^{2} / {2}$ parameters.
