In this paper, we consider a method for solving difficult combinatorial optimization problems on real quantum computers. We focus on the traveling salesman problem as a representative problem for a group of problems where the solution is represented by a permutation. Typically, existing algorithmic solutions use binary matrices to store this permutation – the QUBO (quadratic unconstrained binary optimization) model. We propose a new way of encoding permutations on quantum computers, using a significantly smaller number of qubits than binary matrix encodings. Our method allows for significant performance improvements for any problem whose input or solution is a permutation. We demonstrate an example implementation of the traveling salesman problem on the IQM quantum computers: IQM Spark 5-qubit ‘ODRA-5’ computer and IQM Radiance ‘Garnet’ 20-qubit computer.
In this paper, we consider a method for solving difficult combinatorial optimization problems on real quantum computers. We focus on the traveling salesman problem as a representative problem for a group of problems where the solution is represented by a permutation. Typically, existing algorithmic solutions use binary matrices to store this permutation – the QUBO (quadratic unconstrained binary optimization) model. We propose a new way of encoding permutations on quantum computers, using a significantly smaller number of qubits than binary matrix encodings. Our method allows for significant performance improvements for any problem whose input or solution is a permutation. We demonstrate an example implementation of the traveling salesman problem on the IQM quantum computers: IQM Spark 5-qubit ‘ODRA-5’ computer and IQM Radiance ‘Garnet’ 20-qubit computer.
Abstract The traveling salesman problem (TSP) forms the foundation for many logistics and optimization tasks. At the same time, this problem is NP-hard and requires significant computational resources. Quantum computing promises to substantially accelerate computations or increase solution accuracy. The TSP can be conveniently mapped onto the quadratic unconstrained binary optimization (QUBO) formulation, which in turn can be solved using variational quantum eigensolver (VQE) and quantum approximate optimization algorithm (QAOA) methods, but this mapping requires a quadratic number of qubits. The higher-order binary optimization (HOBO) formulation requires significantly fewer qubits, but it contains higher-order terms. In our work, we thoroughly investigate both formulations and provide a practical recipe for solving the TSP. We give a comprehensive study and compare in detail QUBO and HOBO formulations.
This study explores quantum computing for combinatorial optimization, focusing on the Traveling Salesman Problem (TSP). Using Qiskit, the Quantum Approximate Optimization Algorithm (QAOA) is implemented on simulators and quantum hardware, and compared with classical optimization using Gurobi. TSP instances are encoded as Quadratic Unconstrained Binary Optimization (QUBO) problems derived from the Miller–Tucker–Zemlin formulation, with quadratic penalties enforcing degree and subtour constraints. Results indicate that QAOA consistently generates feasible tours, but classical branch-and-bound methods achieve better solution quality and runtime. On Noisy Intermediate-Scale Quantum (NISQ) devices, performance degrades with problem size due to sensitivity to parameter tuning, penalty scaling, and hardware noise. Among the tested classical optimizers, COBYLA provides the best balance of efficiency and noise tolerance. Overall, this work establishes a reproducible quantum-classical workflow, provides performance baselines, and identifies critical factors such as encoding design, optimizer choice, and error mitigation for improving near-term quantum heuristic performance.
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.
This thesis explores quantum computing for combinatorial optimization through the Traveling Salesman Problem (TSP), which aims to find a minimum-cost Hamiltonian cycle visiting each city exactly once. Using Qiskit, we implement the Quantum Approximate Optimization Algorithm (QAOA) on both simulators and quantum hardware, and compare its performance with that of classical exact optimization via the Gurobi solver. TSP instances are encoded as Quadratic Unconstrained Binary Optimization (QUBO) problems derived from the Miller–Tucker–Zemlin formulation, with degree and subtour constraints embedded using quadratic penalties. Results indicate that QAOA consistently generates feasible tours, but classical branch-and-bound solvers outperform it in both solution quality and runtime. On Noisy Intermediate-Scale Quantum (NISQ) devices, the optimality gap grows with problem size, reflecting sensitivity to variational parameter tuning, penalty scaling, and hardware noise. Among classical optimizers for QAOA, COBYLA offers the most effective tradeoff between efficiency and noise tolerance. Overall, this work establishes a reproducible quantum-classical workflow, provides performance baselines, and identifies critical factors such as encoding design, optimizer choice, and error mitigation for improving near-term quantum heuristic performance.
The traveling salesman problem is a well-known NP-hard problem in combinatorial optimization. This paper shows how to solve it on an Ising Hamiltonian based quantum annealer by casting it as a quadratic unconstrained binary optimization (QUBO) problem. Results of practical experiments are also presented using D-Wave’s 5,000 qubit Advantage 1.1 quantum annealer and the performance is compared to a classical solver. It is found the quantum annealer can only handle a problem size of 8 or less nodes and its performance is subpar compared to the classical solver both in terms of time and accuracy.
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.