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...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autor principal:	Siddharth Jain
Formato:	article
Lenguaje:	EN
Publicado:	Frontiers Media S.A. 2021
Materias:	traveling salesman problem QUBO D-wave quantum annealing combinatorial optimization Physics QC1-999
Acceso en línea:	https://doaj.org/article/cc7e03592a4a4f5ca99dc77e5a613591
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:cc7e03592a4a4f5ca99dc77e5a613591
record_format	dspace
spelling	oai:doaj.org-article:cc7e03592a4a4f5ca99dc77e5a6135912021-11-12T17:06:10ZSolving the Traveling Salesman Problem on the D-Wave Quantum Computer2296-424X10.3389/fphy.2021.760783https://doaj.org/article/cc7e03592a4a4f5ca99dc77e5a6135912021-11-01T00:00:00Zhttps://www.frontiersin.org/articles/10.3389/fphy.2021.760783/fullhttps://doaj.org/toc/2296-424XThe 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.Siddharth JainFrontiers Media S.A.articletraveling salesman problemQUBOD-wavequantum annealingcombinatorial optimizationPhysicsQC1-999ENFrontiers in Physics, Vol 9 (2021)
institution	DOAJ
collection	DOAJ
language	EN
topic	traveling salesman problem QUBO D-wave quantum annealing combinatorial optimization Physics QC1-999
spellingShingle	traveling salesman problem QUBO D-wave quantum annealing combinatorial optimization Physics QC1-999 Siddharth Jain Solving the Traveling Salesman Problem on the D-Wave Quantum Computer
description	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.
format	article
author	Siddharth Jain
author_facet	Siddharth Jain
author_sort	Siddharth Jain
title	Solving the Traveling Salesman Problem on the D-Wave Quantum Computer
title_short	Solving the Traveling Salesman Problem on the D-Wave Quantum Computer
title_full	Solving the Traveling Salesman Problem on the D-Wave Quantum Computer
title_fullStr	Solving the Traveling Salesman Problem on the D-Wave Quantum Computer
title_full_unstemmed	Solving the Traveling Salesman Problem on the D-Wave Quantum Computer
title_sort	solving the traveling salesman problem on the d-wave quantum computer
publisher	Frontiers Media S.A.
publishDate	2021
url	https://doaj.org/article/cc7e03592a4a4f5ca99dc77e5a613591
work_keys_str_mv	AT siddharthjain solvingthetravelingsalesmanproblemonthedwavequantumcomputer
_version_	1718430342205931520

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

Ejemplares similares