How Can a Quantum Computer Solve the Traveling Salesperson Problem?

The traveling salesperson problem (TSP) asks for the shortest route that visits a set of cities exactly once. Solving it classically requires huge computational power because the number of possible routes grows exponentially. In a recent paper, researchers propose a way to encode the TSP on a quantum computer using amplitude encoding. In practice, the information about all cities is stored in a quantum state with a number of qubits that grows only logarithmically with the number of cities, so a small qubit count can represent a huge problem.

To evaluate the route length, instead of summing expectation values of several quantum operators (the usual method), the authors apply a nonlinear function to those expectation values. This yields the cost function directly from the quantum computer’s probability distribution. They tested the approach with a variational quantum eigensolver (VQE), which mixes a parametrized quantum circuit with a classical optimizer. The VQE successfully found the shortest route on various graphs, showing that the method works across a wide range of optimization hyper‑parameters. In short, the study hints that future quantum computers could tackle complex optimization tasks with far fewer resources than classical machines.

Amplitude encoding exploits the ability of qubits to simultaneously represent 2^n states, where n is the number of qubits. By encoding cities in a logarithmic basis, the register size shrinks dramatically compared to a traditional binary encoding. The proposed nonlinear cost function relies on a combination of projection operators that, once measured, yield a probability distribution p(i) associated with each route i. The expected route length is then Σ_i L_i p(i), where L_i is the length of route i. However, instead of directly computing Σ_i L_i p(i), the authors apply a nonlinear transformation f(⟨O⟩) that emphasizes low‑cost configurations, improving VQE convergence. The VQE uses a parametrized ansatz, typically a series of rotation gates and pairwise entanglement, optimized via gradient‑based or Bayesian search methods. Key hyper‑parameters include ansatz depth, classical optimizer learning rate, and the number of measurement shots for expectation estimation. Results show that across a wide range of these parameters, VQE converges to the optimal solution, indicating robustness against noise and hardware imperfections. This approach paves the way for implementations on NISQ devices, where qubit reduction and error tolerance are essential for scalability.