1. Benchmark Study of Quantum Algorithms for Combinatorial Optimization: Unitary versus Dissipative
- Author
-
Sankar, Krishanu, Scherer, Artur, Kako, Satoshi, Reifenstein, Sam, Ghadermarzy, Navid, Krayenhoff, Willem B., Inui, Yoshitaka, Ng, Edwin, Onodera, Tatsuhiro, Ronagh, Pooya, and Yamamoto, Yoshihisa
- Subjects
Quantum Physics ,FOS: Physical sciences ,Quantum Physics (quant-ph) - 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\"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
- Published
- 2021
- Full Text
- View/download PDF