  We study the Quantum Approximate Optimization Algorithm (QAOA) in the context
of the Max-Cut problem. Near-term (noisy) quantum devices are only able to
(accurately) execute QAOA at low circuit depths while QAOA requires a
relatively high circuit-depth in order to "see" the whole graph. We introduce a
classical pre-processing step that initializes QAOA with a biased superposition
of all possible cuts in the graph, referred to as a warm-start. In particular,
our initialization informs QAOA by a solution to a low-rank semidefinite
programming relaxation of the Max-Cut problem. Our experimental results show
that this variant of QAOA, called QAOA-Warm, is able to outperform standard
QAOA on lower circuit depths with less training time (in the optimization stage
for QAOA's variational parameters). We provide experimental evidence as well as
theoretical intuition on performance of the proposed framework.
