Solving the Traveling Salesman Problem on the D-Wave Quantum Computer
Siddharth Jain
Abstract
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.
Topics & Concepts
Quadratic unconstrained binary optimizationTravelling salesman problemQuantumIsing modelSolverQubitQuadratic assignment problemHamiltonian (control theory)Quantum annealingQuantum computerComputer scienceMathematical optimizationQuadratic equationOptimization problemCombinatorial optimizationBinary numberMathematicsStatistical physicsPhysicsQuantum mechanicsGeometryArithmeticQuantum Computing Algorithms and ArchitectureQuantum Information and CryptographyQuantum-Dot Cellular Automata