NP-hard but no longer hard to solve? Using quantum computing to tackle optimization problems

Rhonda Au-Yeung, Nicholas Chancellor, Pascal Halffmann

Research output: Contribution to journalArticlepeer-review

21 Downloads (Pure)

Abstract

In the last decade, public and industrial research funding has moved quantum computing from the early promises of Shor’s algorithm through experiments to the era of noisy intermediate scale quantum devices (NISQ) for solving real-world problems. It is likely that quantum methods can efficiently solve certain (NP-) hard optimization problems where classical approaches fail. In our perspective, we examine the field of quantum optimization, that is, solving optimization problems using quantum computers. We provide an entry point to quantum optimization for researchers from each topic, optimization or quantum computing, by demonstrating advances and obstacles with a suitable use case. We give an overview on problem formulation, available algorithms, and benchmarking. Although we show a proof-of-concept rather than a full benchmark between classical and quantum methods, this gives an idea of the current quality and capabilities of quantum computers for optimization problems. All observations are incorporated in a discussion on some recent quantum optimization breakthroughs, current status, and future directions.
Original languageEnglish
Article number1128576
Number of pages9
JournalFrontiers in Quantum Science and Technology
Volume2
DOIs
Publication statusPublished - 23 Feb 2023

Keywords

  • quantum computing (QC)
  • quantum optimization
  • perspecitves
  • optimization algorithms
  • problem modeling

Fingerprint

Dive into the research topics of 'NP-hard but no longer hard to solve? Using quantum computing to tackle optimization problems'. Together they form a unique fingerprint.

Cite this