The Lie Algebra of XY-mixer Topologies and Warm Starting QAOA for Constrained Optimization

Abstract

The XY-mixer has widespread utilization in modern quantum computing, including in variational quantum algorithms, such as Quantum Alternating Operator Ansatz (QAOA). The XY ansatz is particularly useful for solving Cardinality Constrained Optimization tasks, a large class of important NP-hard problems. First, we give explicit decompositions of the dynamical Lie algebras (DLAs) associated with a variety of $XY$-mixer topologies. When these DLAs admit simple Lie algebra decompositions, they are efficiently trainable. An example of this scenario is a ring $XY$-mixer with arbitrary $R_Z$ gates. Conversely, when we allow for all-to-all $XY$-mixers or include $R_{ZZ}$ gates, the DLAs grow exponentially and are no longer efficiently trainable. We provide numerical simulations showcasing these concepts on Portfolio Optimization, Sparsest $k$-Subgraph, and Graph Partitioning problems. These problems correspond to exponentially-large DLAs and we are able to warm-start these optimizations by pre-training on polynomial-sized DLAs by restricting the gate generators. This results in improved convergence to high quality optima of the original task, providing dramatic performance benefits in terms of solution sampling and approximation ratio on optimization tasks for both shared angle and multi-angle QAOA.

References in corpus (27)

• Variational Quantum Algorithms
• Noisy intermediate-scale quantum (NISQ) algorithms
• Connecting ansatz expressibility to gradient magnitudes and barren plateaus
• Bloch vectors for qudits
• Warm-starting quantum optimization
• Effect of barren plateaus on gradient-free optimization
• Diagnosing Barren Plateaus with Tools from Quantum Optimal Control
• Barren Plateaus in Variational Quantum Computing
• Exploiting symmetry in variational quantum machine learning
• Theory of overparametrization in quantum neural networks
• A Lie Algebraic Theory of Barren Plateaus for Deep Parameterized Quantum Circuits
• Performance comparison of optimization methods on variational quantum algorithms
• MAXCUT QAOA performance guarantees for p >1
• Observing ground-state properties of the Fermi-Hubbard model using a scalable algorithm on a quantum computer
• Theory for Equivariant Quantum Neural Networks
• Learning to Optimize Variational Quantum Circuits to Solve Combinatorial Problems
• Does provable absence of barren plateaus imply classical simulability?
• Constrained Quantum Optimization for Extractive Summarization on a Trapped-ion Quantum Computer
• Classical symmetries and the Quantum Approximate Optimization Algorithm
• The Quantum Alternating Operator Ansatz on Maximum k-Vertex Cover
• Warm-Started QAOA with Custom Mixers Provably Converges and Computationally Beats Goemans-Williamson's Max-Cut at Low Circuit Depths
• Quantum algorithms with local particle number conservation: noise effects and error correction
• Quantum Computational Phase Transition in Combinatorial Problems
• Classification of dynamical Lie algebras for translation-invariant 2-local spin systems in one dimension
• Numerical Evidence for Exponential Speed-up of QAOA over Unstructured Search for Approximate Constrained Optimization
• Lie-algebraic classical simulations for quantum computing
• Imposing Constraints on Driver Hamiltonians and Mixing Operators: From Theory to Practical Implementation

Cited by in corpus (1)

• Constrained Quantum Optimization via Iterative Warm-Start XY-Mixers