Solving NP-hard Problems with Quantum Annealing

Jehn Ruey Jiang, Chun Wei Chu

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

1 Scopus citations

Abstract

Quadratic unconstrained binary optimization (QUBO) formulas of quantum annealing (QA) algorithms are classified into four categories. QA algorithms using different QUBO formulas solve specific NP-hard problems as examples of the classification. The NP-hard problems solved are the subset sum, the vertex cover, the graph coloring, and the traveling salesperson problems. The QA algorithms are compared with their classical counterparts in terms of the quality of the solution and the time to the solution. Based on the comparison results, observations and suggestions are given for each QUBO formula category, so that proper actions can be adopted to improve the performance of QA algorithms. Compared with classical algorithms, QA algorithms are competitive in the current noisy intermediate-scale quantum (NISQ) era and beyond.

Original languageEnglish
Title of host publicationProceedings of the 4th IEEE Eurasia Conference on IoT, Communication and Engineering 2022, ECICE 2022
EditorsTeen-Hang Meen
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages406-411
Number of pages6
ISBN (Electronic)9781665482080
DOIs
StatePublished - 2022
Event4th IEEE Eurasia Conference on IoT, Communication and Engineering, ECICE 2022 - Yunlin, Taiwan
Duration: 28 Oct 202230 Oct 2022

Publication series

NameProceedings of the 4th IEEE Eurasia Conference on IoT, Communication and Engineering 2022, ECICE 2022

Conference

Conference4th IEEE Eurasia Conference on IoT, Communication and Engineering, ECICE 2022
Country/TerritoryTaiwan
CityYunlin
Period28/10/2230/10/22

Keywords

  • NP-hard problem
  • noisy intermediate-scale quantum
  • quadratic unconstrained binary optimization
  • quantum annealing
  • quantum computer
  • smart manufacturing

Fingerprint

Dive into the research topics of 'Solving NP-hard Problems with Quantum Annealing'. Together they form a unique fingerprint.

Cite this