We use a few cookies

Essential cookies keep the library working. With your permission, we'd also like to use analytics to see what's useful and improve the experience. Read our Privacy Policy or Cookie Policy.

Skip to main content
Home/e-Resources/Physics/NP-hard but no longer hard to solve? Using quantum computing to tackle optimization problems
PeriodicalsPhysics

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

arXiv2022

Checking your access to this record.

Abstract & Overview

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 where we solve optimisation problems using quantum computers. We demonstrate this through a proper use case and discuss the current quality of quantum computers, their solver capabilities, and benchmarking difficulties. Although we show a proof-of-concept rather than a full benchmark, we use the results to emphasize the importance of using appropriate metrics when comparing quantum and classical methods. We conclude with discussion on some recent quantum optimization breakthroughs and the current status and future directions.

Cite this record

Rhonda Au-Yeung, Nicholas Chancellor, Pascal Halffmann (2022). NP-hard but no longer hard to solve? Using quantum computing to tackle optimization problems. arXiv. https://library.shubhaarti.com/content/31ab5fda-8e5e-476f-aa4d-eb2cc70a8b6d

Copy in another style

Au-Yeung, R., Chancellor, N., & Halffmann, P. (2022). NP-hard but no longer hard to solve? Using quantum computing to tackle optimization problems. arXiv. https://library.shubhaarti.com/content/31ab5fda-8e5e-476f-aa4d-eb2cc70a8b6d
Author names are used as deposited, so check their order before you submit.

Metadata is harvested from open-access indexes and can be incomplete. Check a citation against the published version before relying on it — see our open access & attribution policy.