A Realizable GAS-based Quantum Algorithm for Traveling Salesman Problem
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%.
Jieao Zhu Yihuai Gao Hansen Wang Tiefu Li Hao Wu