Abstract:

Exact cover problems are NP complete problems in combinatorial optimization， and it is difficult to solve them in polynomial time by using classical algorithms. In order to solve this problem， on the open source quantum computing framework qiskit， a quantum circuit solution based on Quantum Approximate Optimization Algorithm （QAOA） was proposed， and Constrained Optimization BY Linear Approximation （COBYLA） algorithm based on the simplex method was used to optimize the parameters in the quantum logic gates. Firstly， the classical Ising model was established through the mathematical model of the exact cover problem. Secondly， the classical Ising model was quantized by using the rotation variable in quantum theory， and then the Pauli rotation operator was used to replace the rotation variable to obtain the quantum Ising model and the problem Hamiltonian， which improved the speed of QAOA in finding the optimal solution. Finally， the expected expression of the problem Hamiltonian was obtained by the accumulation of the product of the unitary transformation with the mixed Hamiltonian as the generator and the unitary transformation with the problem Hamiltonian as the generator， and the generative quantum circuit was designed accordingly. In addition， the classical processor was used to optimize the parameters in the two unitary transformations to adjust the expected value of the problem Hamiltonian， thereby increasing the probability of solution. The circuit was simulated on qiskit， IBM’s open source quantum computing framework. Experimental results show that the proposed scheme can obtain the solution of the problem in polynomial time with a probability of 95.6%， which proves that the proposed quantum circuit can find a solution to the exact cover problem with a higher probability.

Key words: quantum approximate optimization algorithm, quantum circuit, Hamiltonian, unitary transformation, exact cover

摘要：

精确覆盖问题属于组合优化中的NP完全问题，使用经典算法难以在多项式时间范围内求解。为解决该问题，在开源量子计算框架qiskit上，提出基于量子近似优化算法（QAOA）的量子线路求解方案，并采用基于单纯形法的线性近似约束优化（COBYLA）算法对量子逻辑门中的参数进行优化。首先，通过精确覆盖问题的数学模型建立经典伊辛模型；其次，利用量子理论中的旋转变量对经典伊辛模型进行量子化，再用泡利旋转算子代替旋转变量，得到量子伊辛模型和问题哈密顿量，提高QAOA寻找最优的速度；最后，以混合哈密顿量为生成元的酉变换和问题哈密顿量为生成元的酉变换乘积的累积，得到问题哈密顿量期望的表达式，并由此设计生成量子线路。另外，通过经典处理器对两个酉变换中的参数进行优化，调整问题哈密顿量的期望值，从而提高求解的概率。该线路在IBM的开源量子计算框架qiskit上进行仿真实验，实验结果表明，所提方案能够在多项式时间内以95.6%的概率获得问题的解，验证了所提量子线路能够以较高的概率求得精确覆盖问题的解。

关键词: 量子近似优化算法, 量子线路, 哈密顿量, 酉变换, 精确覆盖