Benchmark Study of Quantum Algorithms for Combinatorial Optimization: Unitary versus Dissipative
ORAL
Abstract
Recent advances in the development of quantum computing hardware raise important questions about the best computational approaches for practical applications. Is unitary evolution of a pure quantum state in a closed system better for various computational tasks than the dissipative dynamics of mixed states in an open system? And for what practical applications will each scheme be best suited?
We present the results of a numerical study estimating the scaling of three different quantum algorithms applied to instances of the NP-hard problem MaxCut. The first two algorithms are closed-system algorithms using qubits: discretized adiabatic quantum computation (DAQC) and Dürr–Høyer's quantum minimum finding (QMF). The third algorithm is a dissipative computation using a coherent Ising machine (CIM) involving a network of quantum oscillators and a measurement-feedback scheme. We observe that the CIM exhibits a time-to-solution scaling in the order of the exponential of the square root of the problem size, which is superior to the scaling of DAQC and QMF for this problem.
*Authors acknowledge the support of the NSF CIM Expedition award (CCF-1918549), Mike and Ophelia Lazaridis, and Innovation, Science and Economic Development Canada.
–
Publication: "Benchmark study of quantum algorithms for combinatorial optimization: Unitary versus dissipative," (2021). Manuscript currently under review with npj Quantum Information, preprint at arXiv:2105.03528
Presenters
-
Krishanu R Sankar
- 1QBit