We have decided to discontinue the publication of preprints on our preprint server as of 1 March 2024. The publication culture within mathematics has changed so much due to the rise of repositories such as ArXiV (www.arxiv.org) that we are encouraging all institute members to make their preprints available there. An institute's repository in its previous form is, therefore, unnecessary. The preprints published to date will remain available here, but we will not add any new preprints here.
MiS Preprint
29/2024
Ising Hamiltonians for constrained combinatorial optimization problems and Metropolis-Hastings warm-starting algorithm
Hui-Min Li, Jin-Min Liang, Zhi-Xi Wang and Shao-Ming Fei
Abstract
Quantum approximate optimization algorithm (QAOA) is an 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, we introduce a general method to obtain the Ising Hamiltonians for CCOPs and present the Metropolis-Hastings warm-starting algorithm for QAOA which can provably converge to the global optimal solutions. We demonstrate the effectiveness of our method 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 our method. The advantages of the Metropolis-Hastings warm-starting algorithm we presented is numerically analyzed through solving 30 randomly generated MVC cases with 1-depth QAOA.
