Novel implementation of variational quantum imaginary time evolution for solving general quantum unconstrained binary optimization problems

Quadratic unconstrained binary optimization (QUBO) represents many classical optimization challenges. The Quantum Approximate Optimization Algorithm (QAOA), as well as host of variants, aim to solve these problems on near term quantum computers. We present a new method based on a variational ansatz, coupled with a novel implementation of Variational Quantum Imaginary Time (VarQITE), that solves a variety of QUBO problems with meager cost. Using intuition based on QAOA, we design an ansatz with circuit depth that scales quadratically in qubit size, with parameters that can be optimized straightforwardly via VarQITE, avoiding problem agnostic classical optimizers. Unlike past implementations of VarQITE, updates require only energy evaluations that scale quadratically in qubit number. We present results for weighted MAXCUT problems ranging from 6-20 qubits with different graph types and show our algorithm achieves an approximation ratio of ~1. We find that the number of parameter updates to reach these results scales linearly in qubit number at the sizes we have simulated, and that the results are relatively insensitive to shot noise. Given the modest circuit depth, number of circuit evaluations, and shots required, this work represents a promising avenue for exploring quantum advantage for QUBO problems on near term computers.