QAOA Algorithms for Traveling Salesman Problem Revisited

The traveling salesman problem is a traditionally NP-hard problem. Earlier quantum algorithm encodes the qubits based on vertices, while we encode the qubits based on edges, with a resources requirement halved. With edge encoding scheme, QAOA algorithm is demoed with small cases, on a classical enumlator, with the optimal solutions successfully found. The algorithm has polynomial complexity in terms of the number of quantum operations.