NP-hard but no longer hard to solve? Using quantum computing to tackle optimization problems
NP-hard but no longer hard to solve? Using quantum computing to tackle optimization problems
复制标题
DOI：
10.3389/frqst.2023.1128576
复制
发表时间：
2022-12
期刊：
影响因子：
--
通讯作者：
Rhonda Au-Yeung;N. Chancellor;Pascal Halffmann
中科院分区：
文献类型：
--
作者：
Rhonda Au-Yeung;N. Chancellor;Pascal Halffmann
在过去的十年中，公共和工业研究资金已经将量子计算从 Shor 算法的早期承诺通过实验转移到了用于解决现实世界问题的嘈杂的中型量子设备 (NISQ) 时代。量子方法很可能可以有效地解决经典方法无法解决的某些（NP-）硬优化问题。从我们的角度来看，我们研究量子优化领域，即使用量子计算机解决优化问题。我们通过合适的用例展示进展和障碍，为每个主题（优化或量子计算）的研究人员提供量子优化的切入点。我们概述了问题表述、可用算法和基准测试。尽管我们展示了概念验证，而不是经典方法和量子方法之间的完整基准，但这给出了量子计算机当前用于优化问题的质量和能力的想法。所有观察结果都纳入对最近的一些量子优化突破、当前状态和未来方向的讨论中。
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.