Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Optics Express

An Optical Solution For The Traveling Salesman Problem

Tobias J. Haist, Wolfgang Osten

Published Jan 1, 2007• 58 citations
Publisher

Abstract

We introduce an optical method based on white light interferometry in order to solve the well-known NP-complete traveling salesman problem. To our knowledge it is the first time that a method for the reduction of non-polynomial time to quadratic time has been proposed. We will show that this achievement is limited by the number of available photons for solving the problem. It will turn out that this number of photons is proportional to N(N) for a traveling salesman problem with N cities and that for large numbers of cities the method in practice therefore is limited by the signal-to-noise ratio. The proposed method is meant purely as a gedankenexperiment.

DOI
10.1364/oe.15.010473

Related papers

An Efficient Quantum Algorithm for the Traveling Salesman Problem

Anant Sharma, Nupur Deshpande, Sanchita Purohit Ghosh +2 more

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.

Quantum Information and Computation•Feb 22, 2025•3 citations

Travelling Salesman Problem in the Classical to Quantum Era: A Comparative Review of Algorithms and Computational Complexity

Istiyak Amin Santo, Siow Chun Lim, Md Serajun Nabi +3 more

The Travelling Salesman Problem (TSP) asks for the shortest tour that visits each city once and returns to the start. It is a classic NP-hard problem and a benchmark for optimization, logistics, and network design. This paper surveys classical, quantum, and hybrid algorithms for the TSP using clear, step-by-step explanations. We summarize how each method works, what it guarantees, and how it scales with the number of cities. We also discuss practical limits of current quantum hardware and outline open problems and promising research directions. While quantum techniques can speed up certain subroutines or offer strong heuristics, no known method solves general TSP in polynomial time. Our goal is to offer a readable yet rigorous map of the landscape for students and practitioners.

•Nov 12, 2025•1 citation

Efficient quantum algorithm for solving travelling salesman problem: An IBM quantum experience

Karthik Srinivasan, Saipriya Satyajit, Bikash K. Behera +1 more

The famous Travelling Salesman Problem (TSP) is an important category of optimization problems that is mostly encountered in various areas of science and engineering. Studying optimization problems motivates to develop advanced techniques more suited to contemporary practical problems. Among those, especially the NP hard problems provide an apt platform to demonstrate supremacy of quantum over classical technologies in terms of resources and time. TSP is one such NP hard problem in combinatorial optimization which takes exponential time order for solving by brute force method. Here we propose a quantum algorithm to solve the travelling salesman problem using phase estimation technique. We approach the problem by encoding the given distances between the cities as phases. We construct unitary operators whose eigenvectors are the computational basis states and eigenvalues are various combinations of these phases. Then we apply phase estimation algorithm to certain eigenstates which give us all the total distances possible for all the routes. After obtaining the distances we can search through this information using the quantum search algorithm for finding the minimum to find the least possible distance as well the route taken. This provides us a quadratic speedup over the classical brute force method for a large number of cities. In this paper, we illustrate an example of the travelling salesman problem by taking four cities and present the results by simulating the codes in the IBM's quantum simulator.

arXiv:1805.10928•May 28, 2018•113 citations

Ultra-fast wave-optical computing

Tobias J. Haist

I present a method for optical computing based on white-light interferometry. The problem to be solved is coded by optical path lengths and the superposition of all possible paths that a photon can travel is used for computing the solution. The solution itself is chosen by interference with the reference light. Several gedankenexperiments demonstrate how this method can be used for solving computational hard problems. Especially, I will introduce the basic principle with two maze-type puzzles and then concentrate on how the method can be employed for performing ultra-fast (sub-ps) digital-optical arithmetic with arbitrary precision.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Aug 28, 2008•2 citations

A silicon photonics quantum solver for the travelling salesman problem

Alessio Baldazzi, Stefano Azzini, Lorenzo Pavesi

We present a new variational quantum algorithm to solve the travelling salesman problem and its experimental validation for four-cities problems using a silicon photonics circuit with integrated photon-pair sources.

Conference on Lasers and Electro-Optics•Jan 1, 2026•0 citations

Solving the Traveling Salesman Problem Using Quantum Devices: QUBO and HOBO Formulations

G. V. Shuvalov, E. N. Krivtsova, M. A. Remnev +1 more

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.

Russian Microelectronics•Dec 1, 2025•0 citations
We introduce an optical method based on white light interferometry in order to solve the well-known NP-complete traveling salesman problem. To our knowledge it is the first time that a method for the reduction of non-polynomial time to quadratic time has been proposed. We will show that this achievement is limited by the number of available photons for solving the problem. It will turn out that this number of photons is proportional to N(N) for a traveling salesman problem with N cities and that for large numbers of cities the method in practice therefore is limited by the signal-to-noise ratio. The proposed method is meant purely as a gedankenexperiment.
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.
The Travelling Salesman Problem (TSP) asks for the shortest tour that visits each city once and returns to the start. It is a classic NP-hard problem and a benchmark for optimization, logistics, and network design. This paper surveys classical, quantum, and hybrid algorithms for the TSP using clear, step-by-step explanations. We summarize how each method works, what it guarantees, and how it scales with the number of cities. We also discuss practical limits of current quantum hardware and outline open problems and promising research directions. While quantum techniques can speed up certain subroutines or offer strong heuristics, no known method solves general TSP in polynomial time. Our goal is to offer a readable yet rigorous map of the landscape for students and practitioners.
The famous Travelling Salesman Problem (TSP) is an important category of optimization problems that is mostly encountered in various areas of science and engineering. Studying optimization problems motivates to develop advanced techniques more suited to contemporary practical problems. Among those, especially the NP hard problems provide an apt platform to demonstrate supremacy of quantum over classical technologies in terms of resources and time. TSP is one such NP hard problem in combinatorial optimization which takes exponential time order for solving by brute force method. Here we propose a quantum algorithm to solve the travelling salesman problem using phase estimation technique. We approach the problem by encoding the given distances between the cities as phases. We construct unitary operators whose eigenvectors are the computational basis states and eigenvalues are various combinations of these phases. Then we apply phase estimation algorithm to certain eigenstates which give us all the total distances possible for all the routes. After obtaining the distances we can search through this information using the quantum search algorithm for finding the minimum to find the least possible distance as well the route taken. This provides us a quadratic speedup over the classical brute force method for a large number of cities. In this paper, we illustrate an example of the travelling salesman problem by taking four cities and present the results by simulating the codes in the IBM's quantum simulator.
I present a method for optical computing based on white-light interferometry. The problem to be solved is coded by optical path lengths and the superposition of all possible paths that a photon can travel is used for computing the solution. The solution itself is chosen by interference with the reference light. Several gedankenexperiments demonstrate how this method can be used for solving computational hard problems. Especially, I will introduce the basic principle with two maze-type puzzles and then concentrate on how the method can be employed for performing ultra-fast (sub-ps) digital-optical arithmetic with arbitrary precision.
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.