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

Au-Yeung, Rhonda; Chancellor, Nicholas; Halffmann, Pascal

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.

Citation

Au-Yeung, R., Chancellor, N., & Halffmann, P. (2023). NP-hard but no longer hard to solve? Using quantum computing to tackle optimization problems. Quantum Science and Technology, 2, Article 1128576. https://doi.org/10.3389/frqst.2023.1128576

• Journal Article Type: Article
• Acceptance Date: Feb 9, 2023
• Online Publication Date: Feb 23, 2023
• Publication Date: Feb 23, 2023
• Deposit Date: Mar 19, 2024
• Publicly Available Date: Mar 19, 2024
• Journal: Frontiers in Quantum Science and Technology
• Electronic ISSN: 2058-9565
• Publisher: IOP Publishing
• Peer Reviewed: Peer Reviewed
• Volume: 2
• Article Number: 1128576
• DOI: https://doi.org/10.3389/frqst.2023.1128576
• Keywords: quantum optimization, quantum computing, perspecitves, optimization algorithms, problem modeling
• Public URL: https://durham-repository.worktribe.com/output/2075785