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

The Tunnelling Salesman: Truncated Variational Approximations for Quantum Mechanical Global Optimization

Oliver B. Downs, Hagai T. Attias, Chris J. C. Burges, Robert Rounthwaite

Published Oct 1, 2002• 0 citations
OpenAlex

Abstract

In this work we present a novel method for global optimization, exploiting the mathematics of quantum mechanics, and in particular the tunnelling phenomenon. We consider a quantum mechanical system with a single particle in a potential specified by the cost function of our optimization problem. We assume the groundstate of the system is localised to the global minimum of the potential function, a condition which can be assured by choosing the particle mass sufficiently large. We then approximate this groundstate using a variational approach to optimise an expansion in terms of a truncated basis set of harmonic oscillator wavefunctions. We show how to encode integer factoring and travelling salesman problems in terms of finding the global minimum of a quartic polynomial cost function. We demonstrate our quantum algorithm on oneand two-dimensional toy problems, and apply it to factoring biprimes with 10 bits. Introduction The state of the art in global optimization for general problems is simulated annealing and its derivatives. The algorithm can be viewed in the physical context of a classical thermal system. This inspires the novel approach presented here, in which we draw upon intuition from non-classical physical systems which obey quantum mechanics (QM), and in particular exhibit the phenomenon of quantum tunnelling. In QM, a potential function V (x) describes the energy terrain experienced by a particle, which may contain multiple minima separated by barriers. Combined with a term describing the kinetic energy of the particle, it defines the Hamiltonian operator: Ĥ = − 2 2m ∇2 + V (1) QM captures all available information on the state of the particle in a (complex) wave function ψ(x). For instance, |ψ(x)|2 is the probability distribution over the position x of the particle. To obtain ψ(x) one solves the eigenvalue problem Ĥψ = Eψ (2) known as the Schroedinger equation, where E is the energy. The solution is a set of wave functions termed eigenstates, and a matching set of energies. The eigenstate with the lowest energy is the ground state, ψ. By choosing the particle’s mass sufficiently large, the probability density associated with the ground state wave function becomes localized to the global minimum of the potential. Hence, a given optimization problem involving the minimization of a cost function can be restated as the problem of finding the ground state of the QM system with a potential specified by that cost function. In particular, computationally ‘hard’ integer problems, including factoring [1] and the travelling salesman problem, can be cast as QM problems involving a quartic polynomial potential, [3]. However, solving the Schroedinger equation exactly for these potentials is generally an analytically intractable problem. In our approach we approximate the groundstate of such a system using a method based on perturbation theory.

Related papers

Quantum Tunneling Parameter in Global Optimization

Teturo Itami

Quantum tunneling that helps particles escape from local minima has been applied in “quantum annealing” method to global optimization of nonlinear functions. To control size of kinetic energy of quantum particles, we form a “quantum tunneling parameter” QT≡m/HR2, where HR corresponds to a physical constant h, Planck's constant divided by 2π, that determines the lowest eigenvalue of quantum particles with mass m. Assumptions on profiles of the function V(x) around its minimum point x0, harmonic oscillator type and square well type, make us possible to write down analytical formulae of the kinetic energy K in terms of QT. The formulae tell that we can make quantum expectation value of particle coordinates x approximate to the minimum point x0 in QT→∞. For systems where we have almost degenerate eigenvalues, examination working with our QT, that x→x0 in QT→∞, is analytically shown also efficient. Similar results that x→x0 under QT→∞ are also obtained when we utilize random-walk quantum Monte Carlo method to represent tunneling phenomena according to conventional quantum annealing.

Transactions of the Society of Instrument and Control Engineers•Jan 1, 2010•1 citation

Quantum Annealing Approach for Selective Traveling Salesman Problem

Thinh V. Le, Manh V. Nguyen, Sri Khandavilli +2 more

Quantum computing has paved a new way for faster and more efficient solutions to large-scale, real-world optimization problems that are challenging for classical computing systems. For instance, selective traveling salesman problem (sTSP) that is famous in such fields as logistic optimization and has attracted increasing attention from the research community, however, is known as an NP-Hard problem. Solving the sTSP is, therefore, extremely complex because the optimization function potentially comes with an exponential number of variables that cannot be solved in polynomial time in general. To this end, we propose a quantum annealing framework for time-bounded and near-optimal solutions for the sTSP, overcoming hardware limits of near-term quantum devices. In particular, we put forth an efficient Hamiltonian (QUBO) to encode the complex decision-making for the sTSP on noisy intermediate-scale quantum (NISQ) annealer. Furthermore, experimental results we obtained on the D-Wave 2000$Q$quantum hardware demonstrate that the optimal solutions for several instances can be attained.

International Conference on Communications•May 28, 2023•13 citations

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

Variational Quantum Approach for the Multiple Traveling Salesman Problem Optimisation

Yannis Spyridis, Athanasios Gkelias, Vasileios Argyriou

The Multiple Traveling Salesman Problem (m-TSP) is a well-known combinatorial optimisation problem with diverse applications in various fields, including transportation, logistics, and network design. The m-TSP involves finding the optimal routes for multiple salesmen to visit a set of cities, minimising the total travel distance while ensuring that each city is visited exactly once. Traditional computational approaches struggle to efficiently solve large-scale instances of the m-TSP due to its inherent complexity. In recent years, quantum computing has emerged as a promising field for tackling combinatorial optimisation problems. In this study, we investigate the application of the Quantum Approximate Optimisation Algorithm (QAOA) to solve the m-TSP, leveraging the inherent parallelism and quantum computational power to potentially obtain high-quality solutions.

International Conference on Distributed Computing in Smart Systems and the Internet of Things (DCOSS-IoT)•Jun 1, 2023•7 citations

An innovative method to escape local minima using quantum system degeneracy in Simulated Annealing

Simulated Annealing (SA) is often used to provide satisfactory solutions to solving combinatorial problems. However, the SA is limited by its tendency to get stuck in local minima, which often prevents the global optimal solution from being reached for large or very complex problems. To overcome this obstacle, we present a new method inspired by the properties of degenerate quantum systems, named Degenerate Quantum Simulated Annealing (SA-DQS). This innovative approach exploits the coexistence of several quantum states of the same energy; this multiplicity of states is advantageous because it allows to finding of several solutions with identical energies, thus increasing the chances of discovering and building a promising solution among them, and of getting out of the traps of local minima more efficiently. The traveling salesman problem (TSP) is used as an application benchmark to validate the effectiveness of SA-DQS. Compared to standard simulated annealing (SA-S), SA-DQS showed superior performance on multiple instances of TSP. On average, the solutions provided by SA-DQS are equal to or closer to the optimum known in TSPLIB, in addition, it also offers a shorter computation time compared to that of other heuristic methods.

ARPN Journal of Engineering and Applied Sciences•Jan 25, 2025•1 citation

Simulated Quantum Annealing Can Be Exponentially Faster Than Classical Simulated Annealing

Elizabeth Crosson, Aram W. Harrow

Can quantum computers solve optimization problems much more quickly than classical computers? One major piece of evidence for this proposition has been the fact that Quantum Annealing (QA) finds the minimum of some cost functions exponentially more quickly than classical Simulated Annealing (SA). One such cost function is the simple “Hamming weight with a spike” function in which the input is an n-bit string and the objective function is simply the Hamming weight, plus a tall thin barrier centered around Hamming weight n/4. While the global minimum of this cost function can be found by inspection, it is also a plausible toy model of the sort of local minima that arise in realworld optimization problems. It was shown by Farhi, Goldstone and Gutmann [1] that for this example SA takes exponential time and QA takes polynomial time, and the same result was generalized by Reichardt [2] to include barriers with width nζ and height nαfor ζ + α ≤ 1/2. This advantage could be explained in terms of quantummechanical “tunneling.” Our work considers a classical algorithm known as Simulated Quantum Annealing (SQA) which relates certain quantum systems to classical Markov chains. By proving that these chains mix rapidly, we show that SQA runs in polynomial time on the Hamming weight with spike problem in much of the parameter regime where QA achieves an exponential advantage over SA. While our analysis only covers this toy model, it can be seen as evidence against the prospect of exponential quantum speedup using tunneling. Our technical contributions include extending the canonical path method for analyzing Markov chains to cover the case when not all vertices can be connected by low-congestion paths. We also develop methods for taking advantage of warm starts and for relating the quantum state in QA to the probability distribution in SQA. These techniques may be of use in future studies of SQA or of rapidly mixing Markov chains in general.

arXiv:1601.03030•Annual Symposium on Foundations of Computer Science•Oct 1, 2016•128 citations
In this work we present a novel method for global optimization, exploiting the mathematics of quantum mechanics, and in particular the tunnelling phenomenon. We consider a quantum mechanical system with a single particle in a potential specified by the cost function of our optimization problem. We assume the groundstate of the system is localised to the global minimum of the potential function, a condition which can be assured by choosing the particle mass sufficiently large. We then approximate this groundstate using a variational approach to optimise an expansion in terms of a truncated basis set of harmonic oscillator wavefunctions. We show how to encode integer factoring and travelling salesman problems in terms of finding the global minimum of a quartic polynomial cost function. We demonstrate our quantum algorithm on oneand two-dimensional toy problems, and apply it to factoring biprimes with 10 bits. Introduction The state of the art in global optimization for general problems is simulated annealing and its derivatives. The algorithm can be viewed in the physical context of a classical thermal system. This inspires the novel approach presented here, in which we draw upon intuition from non-classical physical systems which obey quantum mechanics (QM), and in particular exhibit the phenomenon of quantum tunnelling. In QM, a potential function V (x) describes the energy terrain experienced by a particle, which may contain multiple minima separated by barriers. Combined with a term describing the kinetic energy of the particle, it defines the Hamiltonian operator: Ĥ = − 2 2m ∇2 + V (1) QM captures all available information on the state of the particle in a (complex) wave function ψ(x). For instance, |ψ(x)|2 is the probability distribution over the position x of the particle. To obtain ψ(x) one solves the eigenvalue problem Ĥψ = Eψ (2) known as the Schroedinger equation, where E is the energy. The solution is a set of wave functions termed eigenstates, and a matching set of energies. The eigenstate with the lowest energy is the ground state, ψ. By choosing the particle’s mass sufficiently large, the probability density associated with the ground state wave function becomes localized to the global minimum of the potential. Hence, a given optimization problem involving the minimization of a cost function can be restated as the problem of finding the ground state of the QM system with a potential specified by that cost function. In particular, computationally ‘hard’ integer problems, including factoring [1] and the travelling salesman problem, can be cast as QM problems involving a quartic polynomial potential, [3]. However, solving the Schroedinger equation exactly for these potentials is generally an analytically intractable problem. In our approach we approximate the groundstate of such a system using a method based on perturbation theory.
Quantum tunneling that helps particles escape from local minima has been applied in “quantum annealing” method to global optimization of nonlinear functions. To control size of kinetic energy of quantum particles, we form a “quantum tunneling parameter” QT≡m/HR2, where HR corresponds to a physical constant h, Planck's constant divided by 2π, that determines the lowest eigenvalue of quantum particles with mass m. Assumptions on profiles of the function V(x) around its minimum point x0, harmonic oscillator type and square well type, make us possible to write down analytical formulae of the kinetic energy K in terms of QT. The formulae tell that we can make quantum expectation value of particle coordinates x approximate to the minimum point x0 in QT→∞. For systems where we have almost degenerate eigenvalues, examination working with our QT, that x→x0 in QT→∞, is analytically shown also efficient. Similar results that x→x0 under QT→∞ are also obtained when we utilize random-walk quantum Monte Carlo method to represent tunneling phenomena according to conventional quantum annealing.
Quantum computing has paved a new way for faster and more efficient solutions to large-scale, real-world optimization problems that are challenging for classical computing systems. For instance, selective traveling salesman problem (sTSP) that is famous in such fields as logistic optimization and has attracted increasing attention from the research community, however, is known as an NP-Hard problem. Solving the sTSP is, therefore, extremely complex because the optimization function potentially comes with an exponential number of variables that cannot be solved in polynomial time in general. To this end, we propose a quantum annealing framework for time-bounded and near-optimal solutions for the sTSP, overcoming hardware limits of near-term quantum devices. In particular, we put forth an efficient Hamiltonian (QUBO) to encode the complex decision-making for the sTSP on noisy intermediate-scale quantum (NISQ) annealer. Furthermore, experimental results we obtained on the D-Wave 2000QQQquantum hardware demonstrate that the optimal solutions for several instances can be attained.
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.
The Multiple Traveling Salesman Problem (m-TSP) is a well-known combinatorial optimisation problem with diverse applications in various fields, including transportation, logistics, and network design. The m-TSP involves finding the optimal routes for multiple salesmen to visit a set of cities, minimising the total travel distance while ensuring that each city is visited exactly once. Traditional computational approaches struggle to efficiently solve large-scale instances of the m-TSP due to its inherent complexity. In recent years, quantum computing has emerged as a promising field for tackling combinatorial optimisation problems. In this study, we investigate the application of the Quantum Approximate Optimisation Algorithm (QAOA) to solve the m-TSP, leveraging the inherent parallelism and quantum computational power to potentially obtain high-quality solutions.
Simulated Annealing (SA) is often used to provide satisfactory solutions to solving combinatorial problems. However, the SA is limited by its tendency to get stuck in local minima, which often prevents the global optimal solution from being reached for large or very complex problems. To overcome this obstacle, we present a new method inspired by the properties of degenerate quantum systems, named Degenerate Quantum Simulated Annealing (SA-DQS). This innovative approach exploits the coexistence of several quantum states of the same energy; this multiplicity of states is advantageous because it allows to finding of several solutions with identical energies, thus increasing the chances of discovering and building a promising solution among them, and of getting out of the traps of local minima more efficiently. The traveling salesman problem (TSP) is used as an application benchmark to validate the effectiveness of SA-DQS. Compared to standard simulated annealing (SA-S), SA-DQS showed superior performance on multiple instances of TSP. On average, the solutions provided by SA-DQS are equal to or closer to the optimum known in TSPLIB, in addition, it also offers a shorter computation time compared to that of other heuristic methods.
Can quantum computers solve optimization problems much more quickly than classical computers? One major piece of evidence for this proposition has been the fact that Quantum Annealing (QA) finds the minimum of some cost functions exponentially more quickly than classical Simulated Annealing (SA). One such cost function is the simple “Hamming weight with a spike” function in which the input is an n-bit string and the objective function is simply the Hamming weight, plus a tall thin barrier centered around Hamming weight n/4. While the global minimum of this cost function can be found by inspection, it is also a plausible toy model of the sort of local minima that arise in realworld optimization problems. It was shown by Farhi, Goldstone and Gutmann [1] that for this example SA takes exponential time and QA takes polynomial time, and the same result was generalized by Reichardt [2] to include barriers with width nζ and height nαfor ζ + α ≤ 1/2. This advantage could be explained in terms of quantummechanical “tunneling.” Our work considers a classical algorithm known as Simulated Quantum Annealing (SQA) which relates certain quantum systems to classical Markov chains. By proving that these chains mix rapidly, we show that SQA runs in polynomial time on the Hamming weight with spike problem in much of the parameter regime where QA achieves an exponential advantage over SA. While our analysis only covers this toy model, it can be seen as evidence against the prospect of exponential quantum speedup using tunneling. Our technical contributions include extending the canonical path method for analyzing Markov chains to cover the case when not all vertices can be connected by low-congestion paths. We also develop methods for taking advantage of warm starts and for relating the quantum state in QA to the probability distribution in SQA. These techniques may be of use in future studies of SQA or of rapidly mixing Markov chains in general.