.png){kind=icon}
返回
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}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
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.
Keyword:
NETWORK
SEARCH
期刊
IF:
8.3
论文数:
1.4K
被引数:
8.1K
机构
引用论文
Patients’ experiences of care quality and satisfaction during hospital stay: a qualitative study
PREAI
分享收藏
Efficient sampling of ground and low-energy Ising spin configurations with a coherent Ising machineOAAI
OAAI分享收藏Network of time-multiplexed optical parametric oscillators as a coherent Ising machine.png)
NATURE PHOTONICS
NATURE PHOTONICSIF32.9
PREAI
分享收藏
查看更多内容