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

arXiv:quant-ph/0012112

Quantum simulated annealing

Steve Huntsman

Published Dec 20, 2000• 1 citation
arXivHTMLPDF

Abstract

The question of whether or not quantum computers can efficiently solve NP-complete problems is open, although indications are that BQP does not contain NP. Still, many of these problems are natural candidates for solution on quantum computers. We outline a thermodynamical formalism for the traveling salesman problem which allows for its expected polytime solution on a quantum computer with probability arbitrarily close to unity, given sufficient energy resources and subject to a weak nondegeneracy constraint on the distances. Applications to other problems are also discussed.

DOI
10.48550/arxiv.quant-ph/0012112

Related papers

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•11 citations

Study of Quantum Annealing and the type of related applications

Akash Kalluvilayil Venugopalan, R. K. Karishmah, Ranjith Pillai +3 more

Most of the modern day computations are considered as an NP-hard like solving a puzzle or traveling salesman problem. Over the decades, engineers are exploring for many approaches of solution, out of which Quantum Annealing has depicted the efficacy. In this paper, we do a review study of Quantum Annealing (i.e., an approach to find the global mini-mum of a particular function that can provide better heuristics for the NP-hard optimization problem) and discussed briefly about quantum computers. Not only that, we also showcase few applications of quantum annealing which include scheduling problem, lung cancer detection, coherence in quantum annealer, and clustering.

IEEE Pune Section International Conference (PuneCon)•Dec 16, 2021•7 citations

Quantum Computing, Ising Formulation, and the Traveling Salesman Problem

Omer Gurevich, Maor Matityahu, Tal Mor

Ising formulation is important for many NP problems (Lucas, 2014). This formulation enables implementing novel quantum computing methods including Quantum Approximate Optimization Algorithm and Variational Quantum Eigensolver (VQE). Here, we investigate closely the traveling salesman problem (TSP). First, we present some non-trivial issues related to Ising model view versus a realistic salesman. Then, focusing on VQE we discuss and clarify the use of: a.-- Conventional VQE and how it is relevant as a novel SAT-solver; b.-- Qubit efficiency and its importance in the Noisy Intermediate Scale Quantum-era; and c.-- the relevance and importance of a novel approach named Discrete Quantum Exhaustive Search (Alfassi, Meirom, and Mor, 2024), for enhancing VQE and other methods using mutually unbiased bases. The approach we present here in details can potentially be extended for analyzing approximating and solving various other NP complete problems. Our approach can also be extended beyond the Ising model and beyond the class NP, for example to the class Quantum Merlin Arthur (QMA) of problems, relevant for quantum chemistry and for general spin problems.

quant-pharXiv:2512.24308•Dec 31, 2025•0 citations

Designing Adiabatic Quantum Optimization: A Case Study for the Traveling Salesman Problem

Bettina Heim, Ethan Brown, Dave Wecker +1 more

With progress in quantum technology more sophisticated quantum annealing devices are becoming available. While they offer new possibilities for solving optimization problems, their true potential is still an open question. As the optimal design of adiabatic algorithms plays an important role in their assessment, we illustrate the aspects and challenges to consider when implementing optimization problems on quantum annealing hardware based on the example of the traveling salesman problem (TSP). We demonstrate that tunneling between local minima can be exponentially suppressed if the quantum dynamics are not carefully tailored to the problem. Furthermore we show that inequality constraints, in particular, present a major hurdle for the implementation on analog quantum annealers. We finally argue that programmable digital quantum annealers can overcome many of these obstacles and can - once large enough quantum computers exist - provide an interesting route to using quantum annealing on a large class of problems.

arXiv:1702.06248•Feb 21, 2017•11 citations

Towards Efficiently Solving Quantum Traveling Salesman Problem

Debabrata Goswami, Harish Karnick, Prateek Jain +1 more

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.

arXiv:quant-ph/0411013•Nov 2, 2004•1 citation

Small Traveling Salesman Problems

Richard H. Warren

This paper illustrates fundamental principles about small traveling salesman problems (TSPs) which are a current application for quantum annealing computers.The 2048 qubit, quantum annealing computer manufactured by D-Wave Systems is estimated to be able to solve all TSPs on 8 cities, which advances a recent 4-city result on a quantum simulator.Additionally, the D-Wave quantum computer is expected to find all optimal tours for each TSP.To prepare for this, we show the expected quantum output for 5,000 randomly generated TSPs on 6, 8 and 10 cities.The examples in the TSPLIB have 14 or more cities.These are too large for the current quantum annealing processors.We have included an annotated bibliography about solving the TSP on a quantum computer.

Journal of Advances in Applied Mathematics•Apr 12, 2017•13 citations
The question of whether or not quantum computers can efficiently solve NP-complete problems is open, although indications are that BQP does not contain NP. Still, many of these problems are natural candidates for solution on quantum computers. We outline a thermodynamical formalism for the traveling salesman problem which allows for its expected polytime solution on a quantum computer with probability arbitrarily close to unity, given sufficient energy resources and subject to a weak nondegeneracy constraint on the distances. Applications to other problems are also discussed.
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.
Most of the modern day computations are considered as an NP-hard like solving a puzzle or traveling salesman problem. Over the decades, engineers are exploring for many approaches of solution, out of which Quantum Annealing has depicted the efficacy. In this paper, we do a review study of Quantum Annealing (i.e., an approach to find the global mini-mum of a particular function that can provide better heuristics for the NP-hard optimization problem) and discussed briefly about quantum computers. Not only that, we also showcase few applications of quantum annealing which include scheduling problem, lung cancer detection, coherence in quantum annealer, and clustering.
Ising formulation is important for many NP problems (Lucas, 2014). This formulation enables implementing novel quantum computing methods including Quantum Approximate Optimization Algorithm and Variational Quantum Eigensolver (VQE). Here, we investigate closely the traveling salesman problem (TSP). First, we present some non-trivial issues related to Ising model view versus a realistic salesman. Then, focusing on VQE we discuss and clarify the use of: a.-- Conventional VQE and how it is relevant as a novel SAT-solver; b.-- Qubit efficiency and its importance in the Noisy Intermediate Scale Quantum-era; and c.-- the relevance and importance of a novel approach named Discrete Quantum Exhaustive Search (Alfassi, Meirom, and Mor, 2024), for enhancing VQE and other methods using mutually unbiased bases. The approach we present here in details can potentially be extended for analyzing approximating and solving various other NP complete problems. Our approach can also be extended beyond the Ising model and beyond the class NP, for example to the class Quantum Merlin Arthur (QMA) of problems, relevant for quantum chemistry and for general spin problems.
With progress in quantum technology more sophisticated quantum annealing devices are becoming available. While they offer new possibilities for solving optimization problems, their true potential is still an open question. As the optimal design of adiabatic algorithms plays an important role in their assessment, we illustrate the aspects and challenges to consider when implementing optimization problems on quantum annealing hardware based on the example of the traveling salesman problem (TSP). We demonstrate that tunneling between local minima can be exponentially suppressed if the quantum dynamics are not carefully tailored to the problem. Furthermore we show that inequality constraints, in particular, present a major hurdle for the implementation on analog quantum annealers. We finally argue that programmable digital quantum annealers can overcome many of these obstacles and can - once large enough quantum computers exist - provide an interesting route to using quantum annealing on a large class of problems.
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.
This paper illustrates fundamental principles about small traveling salesman problems (TSPs) which are a current application for quantum annealing computers.The 2048 qubit, quantum annealing computer manufactured by D-Wave Systems is estimated to be able to solve all TSPs on 8 cities, which advances a recent 4-city result on a quantum simulator.Additionally, the D-Wave quantum computer is expected to find all optimal tours for each TSP.To prepare for this, we show the expected quantum output for 5,000 randomly generated TSPs on 6, 8 and 10 cities.The examples in the TSPLIB have 14 or more cities.These are too large for the current quantum annealing processors.We have included an annotated bibliography about solving the TSP on a quantum computer.