We present a compact quantum encoding of the Traveling Salesperson Problem (TSP) based on a time-register representation of tours. A candidate route is represented as a sequence of $n$ city labels over discrete time steps, with one fixed start city and the remaining cities encoded in binary registers. We describe three ingredients of the construction: uniform route generation over the route register, a reversible oracle for marking valid tours, and a phase oracle that encodes the total tour cost. The validity oracle distinguishes permutations of the non-start cities from invalid assignments, while the cost oracle accumulates the contribution of the start edge, intermediate transitions, and return edge into a tour-dependent phase. This yields a coherent superposition of candidate routes with feasibility and tour-length information embedded directly in the quantum state. The number of qubits required is $\Order{n\log_2(n)}$ and the circuit depth scales quadratically in $n$. The encoding is compatible with amplitude amplification or spectral filtering techniques such as the quantum singular value transform (QSVT) or Grover's algorithm. However, due to the exponentially small fraction of valid tours, the overall complexity remains exponential even when combined with amplitude amplification.
We present a compact quantum encoding of the Traveling Salesperson Problem (TSP) based on a time-register representation of tours. A candidate route is represented as a sequence of n city labels over discrete time steps, with one fixed start city and the remaining cities encoded in binary registers. We describe three ingredients of the construction: uniform route generation over the route register, a reversible oracle for marking valid tours, and a phase oracle that encodes the total tour cost. The validity oracle distinguishes permutations of the non-start cities from invalid assignments, while the cost oracle accumulates the contribution of the start edge, intermediate transitions, and return edge into a tour-dependent phase. This yields a coherent superposition of candidate routes with feasibility and tour-length information embedded directly in the quantum state. The number of qubits required is \Ordernlog2(n) and the circuit depth scales quadratically in n. The encoding is compatible with amplitude amplification or spectral filtering techniques such as the quantum singular value transform (QSVT) or Grover's algorithm. However, due to the exponentially small fraction of valid tours, the overall complexity remains exponential even when combined with amplitude amplification.
The traveling salesperson problem (TSP) is “if a traveling salesman wishes to visit exactly once each of a list ofmcities (where the cost of traveling from cityito cityjiscij) and then return to the home city, what is the least costly route the traveling salesman can take [1]?” The TSP is an NP-Complete problem. This paper introduces a solution to the TSP using Grover's quantum algorithm. This paper also introduces a quantum algorithm to the minimum (and maximum) spanning tree problem. The full circuit implementation is presented using the open-source Qiskit environment [2]. This paper provides the number of qubits required, the quantum depth, and the quantum volume of the algorithm for the TSP. This paper also shows how to solve the minimum (and maximum) spanning tree using Grover's algorithm.
Combinatorial optimization problems involve find-ing an optimal solution from a finite set of feasible solutions.Dynamic Programming attempts to solve a combinatorial prob-lem by performing an exhaustive search over the entire domain of the problem.In many such cases, this exhaustive search is not effective or tractable.Travelling salesperson problem is an important combinatorial optimization problem in which the salesperson is given N cities to travel with the condition that he has to travel each city exactly once and return to the origin.Among the finite set of feasible routes, the salesperson has to choose an optimal route with shortest total distance.The route can be optimal either by cost or by distance.The classical algorithm which attempts to find the shortest distance/cost to travel all the cities run in exponential time complexity.For small number of cities, the classical algorithm is effective and feasible but as the number of cities increase, the number of possible routes and the time required to compute them grows exponentially.However, addressing this problem by implementing quantum computing significantly reduces the time required to compute these routes.A quantum algorithm is required to run on a quantum computer to obtain meaningful results as quantum computers use Quantum Bits which differ from the bits used by a classical computer.A.
The Traveling Salesman Problem (TSP) is a classical NP-hard problem in combinatorial optimization, where determining the shortest route among a set of cities becomes computationally prohibitive as the problem size increases. This work explores quantum computing as an alternative approach to address this complexity. Unlike existing methods that primarily rely on quantum annealing, we propose a quantum iterative framework integrating Quantum Phase Estimation (QPE) and Grover's search algorithm. Route costs are encoded as quantum phases, enabling QPE to efficiently evaluate them, while Amplitude Amplification, implemented via the Grover-Long algorithm, iteratively refines the solution space toward the optimal route. A proof-of-concept case study on a small-scale TSP instance demonstrates the feasibility of this approach and its potential for scaling to larger optimization problems. Furthermore, under an expectation-based analysis, the algorithm exhibits an expected computational complexity of O(εm2log2(m)log2(1/ε)) which depends on the error tolerance parameter ε. This estimation omits the initialization term, which we expect future refinements to render subdominant to Phase Estimation.
Abstract We propose an amplitude encoding of the traveling salesperson problem along with a method for calculating the cost function. Our encoding requires a number of qubits which grows logarithmically with the number of cities. We propose to calculate the cost function classically based on the probability distribution extracted from measuring the quantum computer. This is in contrast from the typical method of evaluating the cost function by taking the expectation value of a quantum operator. 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.
The Quantum Approximate Optimization Algorithm (QAOA) and its derived variants are widely in use for approximating combinatorial optimization problem instances on gate-based Noisy Intermediate Scale Quantum (NISQ) computers. Commonly, circuits required for QAOA are constructed by first reformulating a given problem as a Quadratic Unconstrained Binary Optimization (QUBO) problem. It is then straightforward to synthesize a QAOA circuit from QUBO equations. In this work, we illustrate a more qubit-efficient circuit construction for combinatorial optimization problems by the example of the Traveling Salesperson Problem (TSP). Conventionally, the qubit encoding in QAOA for the TSP describes a tour using a sequence of nodes, where each node is written as a 1-hot binary vector. We propose to encode TSP tours by selecting edges included in the tour. Removing certain redundancies, the number of required qubits can be reduced by a linear factor compared to the aforementioned conventional encoding. We examined implementations of both QAOA encoding variants in terms of their approximation quality and runtime. Our experiments show that for small instances results are just as accurate using our proposed encoding, whereas the number of required classical optimizer iterations increases only slightly.
The Travelling Salesman Problem (TSP) is a classic combinatorial optimisation problem which is NP-hard in optimisation form and NP-complete as a decision problem. The standard question asks for the shortest tour that visits every city exactly once and returns to the origin. This paper studies a threshold-fraction variant, which we call the robust TSP, formulated as a promise problem: given a distance threshold K and a promised fraction p, decide whether at least a fraction p of all tours have total length at most K, or whether no such tour exists. We show that Grover's quantum search algorithm decides this problem using O(1/p) oracle queries, independent of the number of cities N, with each query implemented by a quantum circuit of polynomial size in N. For any fixed robustness level p, the total runtime is therefore polynomial in N. Measured in oracle queries, the quantum algorithm offers a quadratic improvement in the dependence on 1/p over classical random sampling, which needs Θ(1/p) samples; because each quantum query is costly, however, it is faster in total running time only when p is very small (roughly below N−4), where the number of queries is no longer constant. We describe the problem formulation, detail the oracle construction (edge-length loading, sequential quantum addition, and threshold comparison), and analyse the query complexity to achieve the required result.