Efficient Encoding of the Traveling Salesperson Problem on a Quantum Computer

We propose an amplitude encoding of the traveling salesperson problem along with a method for calculating the cost function using a probability distribution obtained on a quantum computer. Our encoding requires a number of qubits that grows logarithmically with the number of cities. We propose to calculate the cost function using a nonlinear function of expectation values of quantum operators. This is in contrast to the typical method of evaluating the cost function by summing expectation values of quantum operators. We demonstrate our method using a variational quantum eigensolver algorithm to find the shortest route for a given graph. We find that there is a broad range in the hyperparameters of the optimization procedure for which the best route is found.