.png){kind=icon}
.png){kind=icon}
Return
A benchmarking study of quantum algorithms for combinatorial optimization
.png){kind=icon}
OA
AI
DOI：10.1038/s41534-024-00856-3.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 & uuml;rr-H & oslash;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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\widetilde{{{{\mathcal{O}}}}}\left(\sqrt{{2}<^>{n}}\right)$$\end{document} scaling for DH-QMF. We conclude that the MFB-CIM outperforms DAQC and DH-QMF in solving MaxCut problems.
Keywords:
NETWORK
SEARCH
Journal
IF:
8.3
Papers:
1.4K
Citations:
8.1K