Quantum Optimization Algorithms
This work addresses optimization challenges in quantum computing, but it is incremental as it builds on existing algorithms like QAOA and VQE without introducing major new paradigms.
The paper discusses the Quantum Approximate Optimization Algorithm (QAOA) and its implementation for solving optimization problems like Maximum Cut, showing potential for exponential quantum speedups in industrially relevant applications. It also covers extensions like incorporating constraints with Grover mixers and generalizing to the Variational Quantum Eigensolver (VQE) for the NISQ era.
Quantum optimization allows for up to exponential quantum speedups for specific, possibly industrially relevant problems. As the key algorithm in this field, we motivate and discuss the Quantum Approximate Optimization Algorithm (QAOA), which can be understood as a slightly generalized version of Quantum Annealing for gate-based quantum computers. We delve into the quantum circuit implementation of the QAOA, including Hamiltonian simulation techniques for higher-order Ising models, and discuss parameter training using the parameter shift rule. An example implementation with Pennylane source code demonstrates practical application for the Maximum Cut problem. Further, we show how constraints can be incorporated into the QAOA using Grover mixers, allowing to restrict the search space to strictly valid solutions for specific problems. Finally, we outline the Variational Quantum Eigensolver (VQE) as a generalization of the QAOA, highlighting its potential in the NISQ era and addressing challenges such as barren plateaus and ansatz design.