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 (50)

• Quantum Computing in the NISQ era and beyond
• Quantum Machine Learning
• Variational Quantum Algorithms
• Ising formulations of many NP problems
• The Physical Implementation of Quantum Computation
• Quantum Annealing in the Transverse Ising Model
• Barren plateaus in quantum neural network training landscapes
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Noisy intermediate-scale quantum (NISQ) algorithms
• Quantum Circuit Learning
• Adiabatic Quantum Computing
• Quantum Convolutional Neural Networks
• Quantum Computing with Very Noisy Devices
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Exact and Approximate Unitary 2-Designs: Constructions and Applications
• Connecting ansatz expressibility to gradient magnitudes and barren plateaus
• Defining and detecting quantum speedup
• Bloch vectors for qudits
• Random Quantum Circuits are Approximate 2-designs
• 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
• $XY$-mixers: analytical and numerical results for QAOA
• 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
• Deterministic Preparation of Dicke States
• 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
• Quantum Annealing for Constrained Optimization
• Learning to Optimize Variational Quantum Circuits to Solve Combinatorial Problems
• Domain wall encoding of discrete variables for quantum annealing and QAOA
• 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
• Driver Hamiltonians for constrained optimization in quantum annealing
• 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
• Efficient solvability of Hamiltonians and limits on the power of some quantum computational models
• Quantum algorithms with local particle number conservation: noise effects and error correction
• Constrained quantum annealing of graph coloring
• 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
• A Quantum N-Queens Solver
• 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