Quantum imaginary time evolution and the unit-disk maximum independent set problem

Abstract

In this work we apply a procedure based on the quantum imaginary time evolution method to solve the unit-disk maximum independent set problem. Numerical simulations are performed for instances of six-, eight-, and ten-qubit graphs. We find that the failure probability of the procedure is relatively small and rapidly decreases with the number of shots. In addition, a theoretical upper bound for the failure probability of the procedure is obtained.