Quantum annealing of the Traveling Salesman Problem

Abstract

We propose a path-integral Monte Carlo quantum annealing scheme for the symmetric Traveling Salesman Problem, based on a highly constrained Ising-like representation, and we compare its performance against standard thermal Simulated Annealing. The Monte Carlo moves implemented are standard, and consist in restructuring a tour by exchanging two links (2-opt moves). The quantum annealing scheme, even with a drastically simple form of kinetic energy, appears definitely superior to the classical one, when tested on a 1002 city instance of the standard TSPLIB.

5 pages, 2 figures

Cited by in corpus (69)

• Quantum Annealing and Analog Quantum Computation
• Mathematical Foundation of Quantum Annealing
• Efficient partition of integer optimization problems with one-hot encoding
• Quantum Annealing: An Overview
• Adiabatic quantum dynamics of a random Ising chain across its quantum critical point
• Optimization by Quantum Annealing: Lessons from hard 3-SAT cases
• Improving solutions by embedding larger subproblems in a D-Wave quantum annealer
• Quantum Annealing for Constrained Optimization
• Benchmarking Quantum Annealing Controls with Portfolio Optimization
• A cross-disciplinary introduction to quantum annealing-based algorithms
• Unconstrained Binary Models of the Travelling Salesman Problem Variants for Quantum Optimization
• Driver Hamiltonians for constrained optimization in quantum annealing
• Optimization by Quantum Annealing: Lessons from Simple Cases
• Convergence theorems for quantum annealing
• Scaling analysis and instantons for thermally-assisted tunneling and Quantum Monte Carlo simulations
• Scalable Emulation of Sign-Problem$-$Free Hamiltonians with Room Temperature p-bits
• Quantum speedup of the Travelling Salesman Problem for bounded-degree graphs
• Comparative study of variations in quantum approximate optimization algorithms for the Traveling Salesman Problem
• Convergence of Quantum Annealing with Real-Time Schrodinger Dynamics
• Benchmark test of Black-box optimization using D-Wave quantum annealer
• Optimized annealing of traveling salesman problem from the nth-nearest-neighbor distribution
• Quantum annealing of the random-field Ising model by transverse ferromagnetic interactions
• Quantum Annealing in a Kinetically Constrained System
• Demonstration of tunable three-body interactions between superconducting qubits
• Simulated quantum annealing as a simulator of non-equilibrium quantum dynamics
• A dissipative environment may improve the quantum annealing performances of the ferromagnetic p-spin model
• Constrained quantum annealing of graph coloring
• Direct comparison of quantum and simulated annealing on a fully-connected Ising ferromagnet
• Quantum annealing speedup over simulated annealing on random Ising chains
• The Travelling Salesman Problem and Adiabatic Quantum Computation: An Algorithm
• Experimental analysis of quantum annealers and hybrid solvers using benchmark optimization problems
• Quantum annealing of an Ising spin-glass by Green's function Monte Carlo
• Quantum heuristic algorithm for traveling salesman problem
• Monte Carlo studies of quantum and classical annealing on a double-well
• A Quantum Annealing Approach for Dynamic Multi-Depot Capacitated Vehicle Routing Problem
• Quantum Annealing - Foundations and Frontiers
• Standard quantum annealing outperforms adiabatic reverse annealing with decoherence
• Supplementing Recurrent Neural Networks with Annealing to Solve Combinatorial Optimization Problems
• Optimizing adiabatic quantum pathways via a learning algorithm
• Two-dimensional Ising model with competing interactions and its application to clusters and arrays of $\pi$-rings and adiabatic quantum computing
• Optimization in random field Ising models by quantum annealing
• Deep learning optimal quantum annealing schedules for random Ising models
• Quantum annealing for hard 2-SAT problems : Distribution and scaling of minimum energy gap and success probability
• Approaching the Ground State of a Quantum Spin Glass using a Zero-Temperature Quantum Monte Carlo
• Ising Machines for Diophantine Problems in Physics
• Quantum annealing approach to Ionic Diffusion in Solid
• Efficient quantum and simulated annealing of Potts models using a half-hot constraint
• The relationship between minimum gap and success probability in adiabatic quantum computing
• Localization in the constrained quantum annealing of graph coloring
• Message-passing algorithm of quantum annealing with nonstoquastic Hamiltonian
• Path-Integral Quantum Monte Carlo simulation with Open-Boundary Conditions
• Two-Step Quantum Search Algorithm for Solving Traveling Salesman Problems
• Difference between quantum annealing by imaginary-time and real-time Schrödinger equation of Grover's search
• QUBO Decision Tree: Annealing Machine Extends Decision Tree Splitting
• A method to reduce the rejection rate in Monte Carlo Markov Chains
• Quantum wavefunction annealing of spin glasses
• Boosting quantum annealing performance through direct polynomial unconstrained binary optimization
• Microscopics of Quantum Annealing in the Disordered Dipolar Ising Ferromagnet LiHo${}_x$Y${}_{1-x}$F${}_4$
• Improving quantum annealing by engineering the coupling to the environment
• Limits of Short-Time Evolution of Local Hamiltonians
• Quantum Annealing for Semi-Supervised Learning
• Development of research network on Quantum Annealing Computation and Information using Google Scholar data
• Non-classical Role of Potential Energy in Adiabatic Quantum Annealing
• Finding Hadamard matrices by a quantum annealing machine
• Assessing the quantumness of the annealing dynamics via Leggett Gargs inequalities: a weak measurement approach
• Quantum speed-up for solving the one-dimensional Hubbard model using quantum annealing
• Quantum-inspired search method for low-energy states of classical Ising Hamiltonians
• A Quantum Annealing Approach to Reduce Covid-19 Spread on College Campuses
• Gaussian Amplitude Amplification for Quantum Pathfinding