论文标题
用于旅行推销员问题的可实现的基于气体的量子算法
A Realizable GAS-based Quantum Algorithm for Traveling Salesman Problem
论文作者
论文摘要
本文提出了基于Grover Adaptive Search（GAS）的旅行推销员问题（TSP）的量子算法，可以在IBM的Qiskit库上成功执行。在气体框架下，至少有两个基本困难限制了量子算法在组合优化问题中的应用。一个困难是量子算法提供的解决方案可能不可行。另一个困难是，当前量子计算机的量子数仍然非常有限，并且无法满足算法所需的量子数量的最低要求。为了应对上述困难，我们根据数学定理设计和改进了哈密顿循环检测（HCD）Oracle。在执行算法期间，它可以自动消除不可行的解决方案。另一方面，我们设计了一个锚登记策略来保存Qubits的使用情况。该策略充分考虑了量子计算的可逆性要求，克服了无法简单地覆盖或释放使用的量子位的困难。结果，我们成功地实现了IBM Qiskit的TSP的数值解决方案。对于七节点TSP，我们只需要31个QUBITS，获得最佳解决方案的成功率为86.71％。
The paper proposes a quantum algorithm for the traveling salesman problem (TSP) based on the Grover Adaptive Search (GAS), which can be successfully executed on IBM's Qiskit library. Under the GAS framework, there are at least two fundamental difficulties that limit the application of quantum algorithms for combinatorial optimization problems. One difficulty is that the solutions given by the quantum algorithms may not be feasible. The other difficulty is that the number of qubits of current quantum computers is still very limited, and it cannot meet the minimum requirements for the number of qubits required by the algorithm. In response to the above difficulties, we designed and improved the Hamiltonian Cycle Detection (HCD) oracle based on mathematical theorems. It can automatically eliminate infeasible solutions during the execution of the algorithm. On the other hand, we design an anchor register strategy to save the usage of qubits. The strategy fully considers the reversibility requirement of quantum computing, overcoming the difficulty that the used qubits cannot be simply overwritten or released. As a result, we successfully implemented the numerical solution to TSP on IBM's Qiskit. For the seven-node TSP, we only need 31 qubits, and the success rate in obtaining the optimal solution is 86.71%.
