Solving the Traveling Salesman Problem on the D-Wave Quantum Computer Article Swipe

PDF

Related Concepts

Quadratic unconstrained binary optimization Travelling salesman problem Quantum Ising model Solver Qubit Quadratic assignment problem Hamiltonian (control theory) Quantum annealing Quantum computer Computer science Mathematical optimization Quadratic equation Optimization problem Combinatorial optimization Binary number Mathematics Statistical physics Physics Quantum mechanics Geometry Arithmetic

Siddharth Jain ·

YOU? · · 2021 · Open Access · · DOI: https://doi.org/10.3389/fphy.2021.760783 · OA: W3211376115

The traveling salesman problem is a well-known NP-hard problem in combinatorial optimization. This paper shows how to solve it on an Ising Hamiltonian based quantum annealer by casting it as a quadratic unconstrained binary optimization (QUBO) problem. Results of practical experiments are also presented using D-Wave’s 5,000 qubit Advantage 1.1 quantum annealer and the performance is compared to a classical solver. It is found the quantum annealer can only handle a problem size of 8 or less nodes and its performance is subpar compared to the classical solver both in terms of time and accuracy.