Recursive greedy initialization of the quantum approximate optimization algorithm with guaranteed improvement

Abstract

The quantum approximate optimization algorithm (QAOA) is a variational quantum algorithm, where a quantum computer implements a variational ansatz consisting of $p$ layers of alternating unitary operators and a classical computer is used to optimize the variational parameters. For a random initialization, the optimization typically leads to local minima with poor performance, motivating the search for initialization strategies of QAOA variational parameters. Although numerous heuristic initializations exist, an analytical understanding and performance guarantees for large $p$ remain evasive. We introduce a greedy initialization of QAOA which guarantees improving performance with an increasing number of layers. Our main result is an analytic construction of $2p+1$ transition states - saddle points with a unique negative curvature direction - for QAOA with $p+1$ layers that use the local minimum of QAOA with $p$ layers. Transition states connect to new local minima, which are guaranteed to lower the energy compared to the minimum found for $p$ layers. We use the GREEDY procedure to navigate the exponentially increasing with $p$ number of local minima resulting from the recursive application of our analytic construction. The performance of the GREEDY procedure matches available initialization strategies while providing a guarantee for the minimal energy to decrease with an increasing number of layers $p$.

arXiv comment15 pages, 9 figures, updated to be close to published version

References in corpus (18)

• Quantum Computing in the NISQ era and beyond
• A variational eigenvalue solver on a quantum processor
• Hardware-efficient Variational Quantum Eigensolver for Small Molecules and Quantum Magnets
• Parameterized quantum circuits as machine learning models
• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• Quantum Approximate Optimization Algorithm for MaxCut: A Fermionic View
• Warm-starting quantum optimization
• Quantum annealing initialization of the quantum approximate optimization algorithm
• Optimal Protocols in Quantum Annealing and QAOA Problems
• Parameter Concentration in Quantum Approximate Optimization
• Counterdiabaticity and the quantum approximate optimization algorithm
• Scaling of the quantum approximate optimization algorithm on superconducting qubit based hardware
• MAXCUT QAOA performance guarantees for p >1
• Avoiding barren plateaus via transferability of smooth solutions in Hamiltonian Variational Ansatz
• Graph neural network initialisation of quantum approximate optimisation
• Beating classical heuristics for the binary paint shop problem with the quantum approximate optimization algorithm
• Bounds on approximating Max $k$XOR with quantum and classical local algorithms
• Investigating Quantum Approximate Optimization Algorithms under Bang-bang Protocols

Cited by in corpus (13)

• Quantum approximate optimization via learning-based adaptive optimization
• Warm-Started QAOA with Custom Mixers Provably Converges and Computationally Beats Goemans-Williamson's Max-Cut at Low Circuit Depths
• Iterative Layerwise Training for Quantum Approximate Optimization Algorithm
• Performance Analysis of Multi-Angle QAOA for p > 1
• Trainability Barriers in Low-Depth QAOA Landscapes
• Variational Quantum Multi-Objective Optimization
• Toward a Theory of Phase Transitions in Quantum Control Landscapes
• Quantum Computing for Discrete Optimization: A Highlight of Three Technologies
• Evaluating the Practicality of Quantum Optimization Algorithms for Prototypical Industrial Applications
• Evaluating the Limits of QAOA Parameter Transfer at High-Rounds on Sparse Ising Models With Geometrically Local Cubic Terms
• Lower bounds on the number of rounds of the quantum approximate optimization algorithm required for guaranteed approximation ratios
• Approximate Quadratization of High-Order Hamiltonians for Combinatorial Quantum Optimization
• Role of overparametrization in quantum approximate optimization