Benchmark Study of Quantum Algorithms for Combinatorial Optimization: Unitary versus Dissipative*

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.