  This paper describes an application of the Quantum Approximate Optimisation
Algorithm (QAOA) to efficiently find approximate solutions for computational
problems contained in the polynomially bounded NP optimisation complexity class
(NPO PB). We consider a generalisation of the QAOA state evolution to
alternating quantum walks and solution-quality-dependent phase shifts, and use
the quantum walks to integrate the problem constraints of NPO problems. We
apply the recent concept of a hybrid quantum-classical variational scheme to
attempt finding the highest expectation value, which contains a high-quality
solution. The algorithm is applied to the problem of minimum vertex cover,
showing promising results using only a fixed and low number of optimisation
parameters.
