  Quantum approximate optimization algorithm (QAOA) is a promising variational
quantum algorithm for combinatorial optimization problems. However, the
implementation of QAOA is limited due to the requirement that the problems be
mapped to Ising Hamiltonians and the nonconvex optimization landscapes.
Although the Ising Hamiltonians for many NP hard problems have been obtained, a
general method to obtain the Ising Hamiltonians for constrained combinatorial
optimization problems (CCOPs) has not yet been investigated. In this paper, a
general method is introduced to obtain the Ising Hamiltonians for CCOPs and the
Metropolis-Hastings warm-starting algorithm for QAOA is presented which can
provably converge to the global optimal solutions. The effectiveness of this
method is demonstrated by tackling the minimum weight vertex cover (MWVC)
problem, the minimum vertex cover (MVC) problem, and the maximal independent
set problem as examples. The Ising Hamiltonian for the MWVC problem is obtained
first time by using this method. The advantages of the Metropolis-Hastings
warm-starting algorithm presented here is numerically analyzed through solving
30 randomly generated MVC cases with 1-depth QAOA.
