We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
A benchmarking study of quantum algorithms for combinatorial optimization.
- Authors
Sankar, Krishanu; Scherer, Artur; Kako, Satoshi; Reifenstein, Sam; Ghadermarzy, Navid; Krayenhoff, Willem B.; Inui, Yoshitaka; Ng, Edwin; Onodera, Tatsuhiro; Ronagh, Pooya; Yamamoto, Yoshihisa
- Abstract
We study the performance scaling of three quantum algorithms for combinatorial optimization: measurement-feedback coherent Ising machines (MFB-CIM), discrete adiabatic quantum computation (DAQC), and the Dürr–Høyer algorithm for quantum minimum finding (DH-QMF) that is based on Grover's search. We use MaxCut problems as a reference for comparison, and time-to-solution (TTS) as a practical measure of performance for these optimization algorithms. For each algorithm, we analyze its performance in solving two types of MaxCut problems: weighted graph instances with randomly generated edge weights attaining 21 equidistant values from −1 to 1; and randomly generated Sherrington–Kirkpatrick (SK) spin glass instances. We empirically find a significant performance advantage for the studied MFB-CIM in comparison to the other two algorithms. We empirically observe a sub-exponential scaling for the median TTS for the MFB-CIM, in comparison to the almost exponential scaling for DAQC and the proven O ̃ 2 n scaling for DH-QMF. We conclude that the MFB-CIM outperforms DAQC and DH-QMF in solving MaxCut problems.
- Subjects
OPTIMIZATION algorithms; COMBINATORIAL optimization; WEIGHTED graphs; QUANTUM computing; SPIN glasses; BENCHMARKING (Management)
- Publication
NPJ Quantum Information, 2024, Vol 10, Issue 1, p1
- ISSN
2056-6387
- Publication type
Article
- DOI
10.1038/s41534-024-00856-3