A Quantitative Framework for Comparing Classical and Quantum Algorithms for the Traveling Salesman Problem

• URL: http://arxiv.org/abs/2607.24581v1
• Date: Mon, 27 Jul 2026 15:49:25 GMT
• Title: A Quantitative Framework for Comparing Classical and Quantum Algorithms for the Traveling Salesman Problem
• Abstract summary: The Traveling Salesman Problem is a classical NP-hard problem with significant implications in logistics, circuit design, and operations research.<n>This paper presents a comparative study of four approaches to solving the Traveling Salesman Problem.<n>We implement each technique and evaluate them on graphs of varying sizes to analyze performance, solution quality, and scalability.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Traveling Salesman Problem is a classical NP-hard problem with significant implications in logistics, circuit design, and operations research. This paper presents a comparative study of four approaches to solving the Traveling Salesman Problem: brute-force enumeration, a 2-approximation algorithm using minimum spanning trees, simulated annealing, and the Quantum Approximate Optimization Algorithm. We implement each technique and evaluate them on graphs of varying sizes to analyze performance, solution quality, and scalability. In doing so, we have also developed an open-source framework that allows researchers and practitioners to explore, test and extend these methods.

Related papers

• Gradient Descent Algorithm Survey [0.0]
  This article concentrates on five major algorithms: SGD, Mini-batch SGD, Momentum, Adam, and Lion.<n>It systematically analyzes the core advantages, limitations, and key practical recommendations of each algorithm.
  arXiv  Detail & Related papers  (2025-11-25T09:30:44Z)
• Training Neural Networks at Any Scale [57.048948400182354]
  This article reviews modern optimization methods for training neural networks with an emphasis on efficiency and scale.<n>We present state-of-the-art optimization algorithms under a unified algorithmic template that highlights the importance of adapting to the structures in the problem.
  arXiv  Detail & Related papers  (2025-11-14T10:58:07Z)
• Position: We Need An Algorithmic Understanding of Generative AI [7.425924654036041]
  This position paper proposes AlgEval: a framework for systematic research into the algorithms that LLMs learn and use.<n>AlgEval aims to uncover algorithmic primitives, reflected in latent representations, attention, and inference-time compute, and their algorithmic composition to solve task-specific problems.
  arXiv  Detail & Related papers  (2025-07-10T08:38:47Z)
• A Robust Algorithm for Non-IID Machine Learning Problems with Convergence Analysis [2.4462606119036456]
  We propose an improved numerical algorithm for solving minimax problems based on nonsmooth optimization, quadratic programming and iterative process.<n>Such an algorithm can be widely applied in various fields such as robust optimization, imbalanced learning, etc.
  arXiv  Detail & Related papers  (2025-07-01T14:41:59Z)
• Benchmarking of quantum and classical SDP relaxations for QUBO formulations of real-world logistics problems [0.4636927061010061]
  We provide a vast experimental study of semidefinite programming relaxations of Quadratic unconstrained binary optimization problems.<n>We test on QUBO reformulations of industry-based instances of the (open) vehicle routing problem and the (affinity-based) slotting problem.
  arXiv  Detail & Related papers  (2025-03-13T18:51:45Z)
• Theoretical Analysis of Quality Diversity Algorithms for a Classical Path Planning Problem [12.1622929638257]
  We study the behaviour of Quality diversity (QD) algorithms for a classical planning problem seeking several solutions.<n>Our results show that Map-Elites QD algorithms are able to compute a shortest path for each pair of nodes efficiently in parallel.
  arXiv  Detail & Related papers  (2024-12-16T04:58:32Z)
• On the Convergence of Distributed Stochastic Bilevel Optimization Algorithms over a Network [55.56019538079826]
  Bilevel optimization has been applied to a wide variety of machine learning models. Most existing algorithms restrict their single-machine setting so that they are incapable of handling distributed data. We develop novel decentralized bilevel optimization algorithms based on a gradient tracking communication mechanism and two different gradients.
  arXiv  Detail & Related papers  (2022-06-30T05:29:52Z)
• Neural Combinatorial Optimization: a New Player in the Field [69.23334811890919]
  This paper presents a critical analysis on the incorporation of algorithms based on neural networks into the classical optimization framework. A comprehensive study is carried out to analyse the fundamental aspects of such algorithms, including performance, transferability, computational cost and to larger-sized instances.
  arXiv  Detail & Related papers  (2022-05-03T07:54:56Z)
• Amortized Implicit Differentiation for Stochastic Bilevel Optimization [53.12363770169761]
  We study a class of algorithms for solving bilevel optimization problems in both deterministic and deterministic settings. We exploit a warm-start strategy to amortize the estimation of the exact gradient. By using this framework, our analysis shows these algorithms to match the computational complexity of methods that have access to an unbiased estimate of the gradient.
  arXiv  Detail & Related papers  (2021-11-29T15:10:09Z)
• An Overview and Experimental Study of Learning-based Optimization Algorithms for Vehicle Routing Problem [49.04543375851723]
  Vehicle routing problem (VRP) is a typical discrete optimization problem. Many studies consider learning-based optimization algorithms to solve VRP. This paper reviews recent advances in this field and divides relevant approaches into end-to-end approaches and step-by-step approaches.
  arXiv  Detail & Related papers  (2021-07-15T02:13:03Z)
• Active Model Estimation in Markov Decision Processes [108.46146218973189]
  We study the problem of efficient exploration in order to learn an accurate model of an environment, modeled as a Markov decision process (MDP) We show that our Markov-based algorithm outperforms both our original algorithm and the maximum entropy algorithm in the small sample regime.
  arXiv  Detail & Related papers  (2020-03-06T16:17:24Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.