Solving the Traveling Salesman Problem on the D-Wave Quantum Computer
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 prese...
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | article |
| Lenguaje: | EN |
| Publicado: |
Frontiers Media S.A.
2021
|
| Materias: | |
| Acceso en línea: | https://doaj.org/article/cc7e03592a4a4f5ca99dc77e5a613591 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| Sumario: | 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. |
|---|