Ising Hamiltonians for Constrained Combinatorial Optimization Problems and the Metropolis-Hastings Warm-Starting Algorithm
arXiv:2307.08980 · doi:10.1002/qute.202300101
Abstract
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.
References in corpus (21)
- Quantum Computing in the NISQ era and beyond
- A variational eigenvalue solver on a quantum processor
- Variational Quantum Algorithms
- Ising formulations of many NP problems
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- A Quantum Approximate Optimization Algorithm
- Quantum Annealing and Analog Quantum Computation
- Quantum Computation by Adiabatic Evolution
- Digitized adiabatic quantum computing with a superconducting circuit
- Warm-starting quantum optimization
- Digitized-counterdiabatic quantum approximate optimization algorithm
- MAXCUT QAOA performance guarantees for p >1
- Portfolio Optimization with Digitized-Counterdiabatic Quantum Algorithms
- Digitized-Counterdiabatic Quantum Optimization
- Progress toward favorable landscapes in quantum combinatorial optimization
- Expectation Values from the Single-Layer Quantum Approximate Optimization Algorithm on Ising Problems
- Quantum Algorithms for Scientific Computing and Approximate Optimization
- Quantum Annealing with Trigger Hamiltonians: Application to 2-SAT and Nonstoquastic Problems
- An Exact Algorithm for Minimum Weight Vertex Cover Problem in Large Graphs
- Max-cut Clustering Utilizing Warm-Start QAOA and IBM Runtime
- Monte Carlo Search for Very Hard KSAT Realizations for Use in Quantum Annealing