Saved in:
| Main Authors: | , , , , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2105.03528 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909457974296576 |
|---|---|
| author | Sankar, Krishanu Scherer, Artur Kako, Satoshi Reifenstein, Sam Ghadermarzy, Navid Krayenhoff, Willem B. Inui, Yoshitaka Ng, Edwin Onodera, Tatsuhiro Ronagh, Pooya Yamamoto, Yoshihisa |
| author_facet | Sankar, Krishanu Scherer, Artur Kako, Satoshi Reifenstein, Sam Ghadermarzy, Navid Krayenhoff, Willem B. Inui, Yoshitaka Ng, Edwin Onodera, Tatsuhiro Ronagh, Pooya Yamamoto, Yoshihisa |
| contents | 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-Hoyer 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{O}\left(\sqrt{2^n}\right)$ scaling for DH-QMF. We conclude that the MFB-CIM outperforms DAQC and DH-QMF in solving MaxCut problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2105_03528 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | A Benchmarking Study of Quantum Algorithms for Combinatorial Optimization Sankar, Krishanu Scherer, Artur Kako, Satoshi Reifenstein, Sam Ghadermarzy, Navid Krayenhoff, Willem B. Inui, Yoshitaka Ng, Edwin Onodera, Tatsuhiro Ronagh, Pooya Yamamoto, Yoshihisa Quantum Physics 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-Hoyer 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{O}\left(\sqrt{2^n}\right)$ scaling for DH-QMF. We conclude that the MFB-CIM outperforms DAQC and DH-QMF in solving MaxCut problems. |
| title | A Benchmarking Study of Quantum Algorithms for Combinatorial Optimization |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2105.03528 |