  We present a variational quantum algorithm for solving combinatorial
optimization problems with linear-depth circuits. Our algorithm uses an ansatz
composed of Hamiltonian generators designed to control each term in the target
combinatorial function, along with parameter updates following a modified
version of quantum imaginary time evolution. We evaluate this ansatz in
numerical simulations that target solutions to the MAXCUT problem. The state
evolution is shown to closely mimic imaginary time evolution, and its
optimal-solution convergence is further improved using adaptive transformations
of the classical Hamiltonian spectrum, while resources are minimized by pruning
optimized gates that are close to the identity. With these innovations, the
algorithm consistently converges to optimal solutions, with interesting
highly-entangled dynamics along the way. This performant and resource-minimal
approach is a promising candidate for potential quantum computational
advantages on near-term quantum computing hardware.
