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

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