  Quantum computing may provide advantage in solving classical optimization
problems. One promising algorithm is the quantum approximate optimization
algorithm (QAOA). There have been many proposals for improving this algorithm,
such as using an initial state informed by classical approximation solutions. A
variation of QAOA called ADAPT-QAOA constructs the ansatz dynamically and can
speed up convergence. However, it faces the challenge of frequently converging
to excited states which correspond to local minima in the energy landscape,
limiting its performance. In this work, we propose to start ADAPT-QAOA with an
initial state inspired by a classical approximation algorithm. Through
numerical simulations we show that this new algorithm can reach the same
accuracy with fewer layers than the standard QAOA and the original ADAPT-QAOA.
It also appears to be less prone to the problem of converging to excited
states.

Quantum Physics