论文标题
NP优化问题的量子近似算法与约束
Quantum approximate algorithm for NP optimization problems with constraints
论文作者
论文摘要
量子近似优化算法（QAOA）是一个算法框架，用于查找与量子绝热算法（QAA）的近似值相结合的近似解决方案。在QAOA或QAA的上下文中解决与约束的组合优化问题时，需要找到一种将问题约束编码到该方案中的方法。在本文中，我们将不同的约束类型形式化为线性平等，线性不平等和任意形式。基于此，我们建议在QAOA框架中进行约束编码方案，以解决NP组合优化问题。实施的算法通过一些众所周知的NP优化问题的不同实例的测试结果证明了拟议方案的有效性和效率。我们认为，在QAOA的背景下，我们的工作导致了一个通用框架，可在QAOA，高质量的近似解决方案中，将问题与各种类型的约束结合在一起。
The Quantum Approximate Optimization Algorithm (QAOA) is an algorithmic framework for finding approximate solutions to combinatorial optimization problems, derived from an approximation to the Quantum Adiabatic Algorithm (QAA). In solving combinatorial optimization problems with constraints in the context of QAOA or QAA, one needs to find a way to encode problem constraints into the scheme. In this paper, we formalize different constraint types to linear equalities, linear inequalities, and arbitrary form. Based on this, we propose constraint-encoding schemes well-fitting into the QAOA framework for solving NP combinatorial optimization problems. The implemented algorithms demonstrate the effectiveness and efficiency of the proposed scheme by the testing results of varied instances of some well-known NP optimization problems. We argue that our work leads to a generalized framework for finding, in the context of QAOA, high-quality approximate solutions to combinatorial problems with various types of constraints.
