Optimizing QUBO on a quantum computer by mimicking imaginary time evolution
Yahui Chai, Alice Di Tucci · New Journal of Physics · 2026
Abstract We propose a hybrid quantum–classical algorithm for solving quadratic unconstrained binary optimization (QUBO) problems using an imaginary time evolution-mimicking circuit (ITEMC). The circuit parameters are optimized to mimic short-time ITE, using only single- and two-qubit expectation values. This significantly reduces the measurement overhead by avoiding full energy evaluation. By updating the initial state based on results from last step iteratively, the algorithm quickly converges to the low-energy solutions. With a pre-sorting step that optimizes quantum gate ordering based on QUBO coefficients, the convergence is further improved. Our classical simulations achieve approximation ratios above 99 % up to 150 qubits. Furthermore, the linear scaling of entanglement entropy with system size suggests that the circuit is challenging to simulate classically using tensor networks. We also demonstrate hardware runs on IBM’s device for 40, 60, and 80 qubits, and obtain solutions compatible with that from simulated annealing.