1. A benchmarking study of quantum algorithms for combinatorial optimization
- Author
-
Krishanu Sankar, Artur Scherer, Satoshi Kako, Sam Reifenstein, Navid Ghadermarzy, Willem B. Krayenhoff, Yoshitaka Inui, Edwin Ng, Tatsuhiro Onodera, Pooya Ronagh, and Yoshihisa Yamamoto
- Subjects
Physics ,QC1-999 ,Electronic computers. Computer science ,QA75.5-76.95 - Abstract
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 $$\widetilde{{{{\mathcal{O}}}}}\left(\sqrt{{2}^{n}}\right)$$ O ̃ 2 n scaling for DH-QMF. We conclude that the MFB-CIM outperforms DAQC and DH-QMF in solving MaxCut problems.
- Published
- 2024
- Full Text
- View/download PDF