We present a framework for efficiently solving Approximate Traveling Salesman Problem (Approximate TSP) for Quantum Computing Models. Existing representations of TSP introduce extra states which do not correspond to any permutation. We present an efficient and intuitive encoding for TSP in quantum computing paradigm. Using this representation and assuming a Gaussian distribution on tour-lengths, we give an algorithm to solve Approximate TSP (Euclidean) within BQP resource bounds. Generalizing this strategy for any distribution, we present an oracle based Quantum Algorithm to solve Approximate TSP. We present a realization of the oracle in the quantum counterpart of PP.
We present a framework for efficiently solving Approximate Traveling Salesman Problem (Approximate TSP) for Quantum Computing Models. Existing representations of TSP introduce extra states which do not correspond to any permutation. We present an efficient and intuitive encoding for TSP in quantum computing paradigm. Using this representation and assuming a Gaussian distribution on tour-lengths, we give an algorithm to solve Approximate TSP (Euclidean) within BQP resource bounds. Generalizing this strategy for any distribution, we present an oracle based Quantum Algorithm to solve Approximate TSP. We present a realization of the oracle in the quantum counterpart of PP.
Quantum search algorithms, such as Grover's algorithm, are anticipated to efficiently solve constrained combinatorial optimization problems. However, applying these algorithms to the traveling salesman problem (TSP) on a quantum circuit presents a significant challenge. Existing quantum search algorithms for the TSP typically assume that an initial state—an equal superposition of all feasible solutions satisfying the problem's constraints—is pre-prepared. The query complexity of preparing this state using brute-force methods scales exponentially with the factorial growth of feasible solutions, creating a significant hurdle in designing quantum circuits for large-scale TSPs. To address this issue, we propose a two-step quantum search (TSQS) algorithm that employs two sets of operators. In the first step, all the feasible solutions are amplified into their equal superposition state. In the second step, the optimal solution state is amplified from this superposition state. The TSQS algorithm demonstrates greater efficiency compared to conventional search algorithms that employ a single oracle operator for finding a solution within the encoded space. Encoded in the higher order unconstrained binary optimization representation, our approach significantly reduces the qubit requirements. This enables efficient initial state preparation through a unified circuit design, offering a quadratic speedup in solving the TSP without prior knowledge of feasible solutions.
Abstract The travelling salesman problem (TSP) is a popular NP-hard combinatorial optimization problem that requires finding the optimal way for a salesman to travel through different cities once and return to the initial city. The existing methods of solving TSPs on quantum systems are either gate-based or binary variable-based encoding. Both approaches are resource-expensive in terms of the number of qubits, while performing worse compared to existing classical algorithms, even for small-sized problems. A novel encoding scheme is needed to map the TSP problem onto a quantum system, which is addressed in this work. We introduce a distinct geometric approach to encode the TSP on a single qubit and present a quantum-inspired algorithm to solve the problem by invoking the principle of quantum superposition . The cities are represented as quantum states on the Bloch sphere, while the preparation of superposition states allows us to traverse multiple paths at once. The underlying framework of our algorithm is a quantum-inspired version of the classical Brachistochrone approach. Optimal control methods are employed to create a selective superposition of the quantum states to find the shortest route of a given TSP. The numerical simulations solve a sample of four to nine cities for which exact solutions are obtained. The algorithm can be implemented on any quantum platform capable of efficiently rotating a qubit and allowing state tomography measurements. For the TSP problem sizes considered in this work, our algorithm is more resource-efficient and accurate than existing quantum algorithms, with the potential for scalability.
Abstract The traveling salesman problem is the problem of finding out the shortest route in a network of cities, that a salesman needs to travel to cover all the cities, without visiting the same city more than once. This problem is known to be N P -hard with a brute-force complexity of O ( N N ) or O ( N 2 N ) for N number of cities. This problem is equivalent to finding out the shortest Hamiltonian cycle in a given graph, if at least one Hamiltonian cycle exists in it. Quantum algorithms for this problem typically provide with a quadratic speedup only, using Grover’s search, thereby having a complexity of O ( N N /2 ) or O ( N N ). We present a bounded-error quantum polynomial-time (BQP) algorithm for solving the problem, providing with an exponential speedup. The overall complexity of our algorithm is O ( N 3 log( N ) κ / ϵ + 1/ ϵ 3 ), where the errors ϵ are O (1/poly( N )), and κ is the not-too-large condition number of the matrix encoding all Hamiltonian cycles.
A hybrid quantum-classical framework is exploited to solve the Traveling Salesman Problem (TSP) based on a Quantum Approximate Optimization Algorithm (QAOA). To overcome the computational limitation of the Grover’s Search Algorithm (GSA) stemming from path encoding and arithmetic subroutines, a clustering-based strategy is employed to decompose a 16-city TSP into four 4-city subproblems, each of which can be solved with a 16-qubit budget. Intra-cluster solutions are optimized with QAOA, and are classically stitched to construct the global tour. Our results clearly validate the effectiveness of the hierarchical design of the algorithm, highlighting its feasibility for mid-scale quantum optimizations.
This paper introduces a novel edge-based encoding technique for solving the Traveling Salesman Problem (TSP) on a quantum computer, reducing the required number of qubits. For implementation in real quantum devices, we applied the subspace reduction encoding to further reduce the dimension of the TSP solution space. We attack the TSP for 4-, 5-, and 6-city instances in both simulators and real quantum computers across different encoding frameworks. Optimal solutions of the 4-city TSP instance are obtained on state-of-the art IQM quantum computer. Our study presents a comparative analysis between edge-based encoding scheme and the node-based encoding methodology in the literature. Our findings indicate that the proposed encoding scheme outperforms conventional methods in terms of statistical measures, quantum resource utilization, and computational efficiency when applied to smaller TSP instances.
The Traveling Salesman Problem (TSP) is a prototypical combinatorial optimization problem, but its quantum implementation is limited by the O(n^2)-qubit overhead of standard one-hot encodings. Here, we propose a resource-efficient variational quantum framework based on compact binary-register encoding, a permutation-preserving problem-inspired ansatz, and a complementary divide-and-conquer execution strategy. The compact encoding reduces the data-qubit requirement to O(n log n), while the divide-and-conquer formulation lowers the number of qubits required in each local hardware execution to the size of the largest subsystem. Numerical simulations on TSP instances with 4, 5, and 6 cities achieve best average success rates of 100%, 100%, and 95.5%, respectively. A local two-qubit implementation of the divide-and-conquer approximation is further evaluated for a 5-city TSP instance on SpinQ Gemini Pro and SpinQ Triangulum II NMR quantum computers. Taken together, the results indicate how compact encoding and divide-and-conquer execution with classical post-processing can be used to study small combinatorial optimization instances on resource-constrained quantum hardware.