Benchmark Study of Quantum Algorithms for Combinatorial Optimization: Unitary versus Dissipative
| Autor: | Sankar, Krishanu, Scherer, Artur, Kako, Satoshi, Reifenstein, Sam, Ghadermarzy, Navid, Krayenhoff, Willem B., Inui, Yoshitaka, Ng, Edwin, Onodera, Tatsuhiro, Ronagh, Pooya, Yamamoto, Yoshihisa |
|---|---|
| Rok vydání: | 2021 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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\"urr-Hoyer algorithm for quantum minimum finding (DH-QMF) that is based on Grover's search. We use MaxCut problems as our reference for comparison, and time-to-solution (TTS) as a practical measure of performance for these optimization algorithms. We empirically observe a $\Theta(2^{\sqrt{n}})$ scaling for the median TTS for MFB-CIM, in comparison to the exponential scaling with the exponent $n$ for DAQC and the provable $\widetilde{\mathcal O}\left(\sqrt{2^n}\right)$ scaling for DH-QMF. We conclude that these scaling complexities result in a dramatic performance advantage for MFB-CIM in comparison to the other two algorithms for solving MaxCut problems. Comment: 24 pages, 20 figures |
| Databáze: | arXiv |
| Externí odkaz: |
|