论文标题
量子交替的操作员ANSATZ解决最小确切的盖子问题
Quantum Alternating Operator Ansatz for Solving the Minimum Exact Cover Problem
论文作者
论文摘要
量子交替运算符ANSATZ（QAOA+）是量子近似优化算法（QAOA）的扩展，其中搜索空间在求解约束的组合优化问题中较小。但是，QAOA+需要一个琐碎的可行解决方案作为初始状态，因此不能用于难以找到琐碎的可行解决方案的问题。为简单起见，我们将其称为非平凡的验证问题（NTFSP）。在本文中，我们以最低确切覆盖率（MEC）问题为例，研究如何将QAOA+应用于NTFSP。众所周知，确切的覆盖（EC）是MEC问题的可行空间，它没有微不足道的解决方案。为了克服上述问题，EC问题分为两个步骤来解决。首先，获得了脱节集，这等同于解决独立集。其次，在此基础上，解决了所有元素（即EC）的集合。换句话说，我们将MEC转换为多目标约束优化问题，其中可行的空间由易于找到的独立集组成。最后，我们还从数值实验中验证了算法的可行性。我们的方法为将QAOA+应用于NTFSP提供了可行的方法，并有望大大扩展其应用程序。
The Quantum Alternating Operator Ansatz (QAOA+) is an extension of the Quantum Approximate Optimization Algorithm (QAOA), where the search space is smaller in solving constrained combinatorial optimization problems. However, QAOA+ requires a trivial feasible solution as the initial state, so it cannot be used for problems that are difficult to find a trivial feasible solution. For simplicity, we call them as Non-Trivial-Feasible-Solution Problems (NTFSP). In this paper, we take the Minimum Exact Cover (MEC) problem as an example, studying how to apply QAOA+ to NTFSP. As we know, exact covering (EC) is the feasible space of MEC problem, which has no trivial solutions. To overcome the above problem, the EC problem is divided into two steps to solve. First, disjoint sets are obtained, which is equivalent to solving independent sets. Second, on this basis, the sets covering all elements (i.e., EC) are solved. In other words, we transform MEC into a multi-objective constrained optimization problem, where feasible space consists of independent sets that are easy to find. Finally, we also verify the feasibility of the algorithm from numerical experiments. Our method provides a feasible way for applying QAOA+ to NTFSP, and is expected to expand its application significantly.
