$XY$-mixers: analytical and numerical results for QAOA

Abstract

The Quantum Alternating Operator Ansatz (QAOA) is a promising gate-model meta-heuristic for combinatorial optimization. Applying the algorithm to problems with constraints presents an implementation challenge for near-term quantum resources. This work explores strategies for enforcing hard constraints by using $XY$-Hamiltonians as mixing operators (mixers). Despite the complexity of simulating the $XY$ model, we demonstrate that for problems represented through one-hot-encoding, certain classes of the mixer Hamiltonian can be implemented without Trotter error in depth $O(\kappa )$ where $\kappa$ is the number of assignable colors. We also specify general strategies for implementing QAOA circuits on all-to-all connected hardware graphs and linearly connected hardware graphs inspired by fermionic simulation techniques. Performance is validated on graph coloring problems that are known to be challenging for a given classical algorithm. The general strategy of using $XY$-mixers is borne out numerically, demonstrating a significant improvement over the general $X$-mixer, and moreover the generalized $W$-state yields better performance than easier-to-generate classical initial states when $XY$ mixers are used.

Updated to journal version. Detailed W-state generating unitaries in Appendix C.1

References in corpus (26)

• The theory of variational hybrid quantum-classical algorithms
• Perfect state transfer in quantum spin networks
• Scalable Quantum Simulation of Molecular Energies
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Quantum Simulation of Electronic Structure with Linear Depth and Connectivity
• Quantum Approximate Optimization Algorithm for MaxCut: A Fermionic View
• QAOA for Max-Cut requires hundreds of qubits for quantum speed-up
• Low Depth Quantum Simulation of Electronic Structure
• Concrete Categorical Model of a Quantum Circuit Description Language with Measurement
• Unsupervised Machine Learning on a Hybrid Quantum Computer
• Quantum circuits for strongly correlated quantum systems
• Quantum algorithms to simulate many-body physics of correlated fermions
• Optimizing Variational Quantum Algorithms using Pontryagin's Minimum Principle
• Near-optimal quantum circuit for Grover's unstructured search using a transverse field
• Application of fermionic marginal constraints to hybrid quantum algorithms
• Compiling quantum circuits to realistic hardware architectures using temporal planners
• Sequential Generation of Matrix-Product States in Cavity QED
• Quantum Algorithms for Fixed Qubit Architectures
• Network Community Detection On Small Quantum Computers
• Schumacher's quantum data compression as a quantum computation
• Stabilisers as a design tool for new forms of Lechner-Hauke-Zoller Annealer
• Efficient quantum algorithm for preparing molecular-system-like states on a quantum computer
• Fourier transform of fermionic systems and the spectral tensor network
• A quantum alternating operator ansatz with hard and soft constraints for lattice protein folding
• Finding cliques by quantum adiabatic evolution
• Comparing and Integrating Constraint Programming and Temporal Planning for Quantum Circuit Compilation

Cited by in corpus (107)

• Variational Quantum Algorithms
• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Warm-starting quantum optimization
• Diagnosing Barren Plateaus with Tools from Quantum Optimal Control
• Noise Resilience of Variational Quantum Compiling
• Challenges and Opportunities in Quantum Optimization
• Avoiding local minima in variational quantum eigensolvers with the natural gradient optimizer
• Solving Vehicle Routing Problem Using Quantum Approximate Optimization Algorithm
• Quantum Algorithm Implementations for Beginners
• Hybrid quantum-classical algorithms in the noisy intermediate-scale quantum era and beyond
• Parameter Concentration in Quantum Approximate Optimization
• Grover Mixers for QAOA: Shifting Complexity from Mixer Design to State Preparation
• Implementation of the XY interaction family with calibration of a single pulse
• Benchmarking the performance of portfolio optimization with QAOA
• Constrained Quantum Optimization for Extractive Summarization on a Trapped-ion Quantum Computer
• Error mitigation for variational quantum algorithms through mid-circuit measurements
• Empirical performance bounds for quantum approximate optimization
• Efficient encoding of the weighted MAX k-CUT on a quantum computer using QAOA
• Quantum Hamiltonian-Based Models and the Variational Quantum Thermalizer Algorithm
• The Quantum Alternating Operator Ansatz on Maximum k-Vertex Cover
• Multi-block ADMM Heuristics for Mixed-Binary Optimization on Classical and Quantum Computers
• A perspective on protein structure prediction using quantum computers
• Quantum Annealing vs. QAOA: 127 Qubit Higher-Order Ising Problems on NISQ Computers
• Constrained mixers for the quantum approximate optimization algorithm
• Quantum unary approach to option pricing
• Training Saturation in Layerwise Quantum Approximate Optimisation
• A Divide-and-Conquer Approach to Dicke State Preparation
• Combinatorial optimisation via highly efficient quantum walks
• Unbalanced penalization: A new approach to encode inequality constraints of combinatorial problems for quantum optimization algorithms
• Alignment between Initial State and Mixer Improves QAOA Performance for Constrained Optimization
• Low depth mechanisms for quantum optimization
• Short-Depth Circuits for Dicke State Preparation
• Constrained Optimization via Quantum Zeno Dynamics
• Exploiting Symmetry Reduces the Cost of Training QAOA
• Warm-Started QAOA with Custom Mixers Provably Converges and Computationally Beats Goemans-Williamson's Max-Cut at Low Circuit Depths
• Comparative study of variations in quantum approximate optimization algorithms for the Traveling Salesman Problem
• An entanglement perspective on the quantum approximate optimization algorithm
• An Expressive Ansatz for Low-Depth Quantum Approximate Optimisation
• Quantum algorithms with local particle number conservation: noise effects and error correction
• Character randomized benchmarking for non-multiplicity-free groups with applications to subspace, leakage, and matchgate randomized benchmarking
• Applying quantum approximate optimization to the heterogeneous vehicle routing problem
• Analytical Framework for Quantum Alternating Operator Ansätze
• Approaches to Constrained Quantum Approximate Optimization
• Quantifying the efficiency of state preparation via quantum variational eigensolvers
• Threshold-Based Quantum Optimization
• Numerical Evidence for Exponential Speed-up of QAOA over Unstructured Search for Approximate Constrained Optimization
• A native measurement-based QAOA algorithm, applied to the MAX K-CUT problem
• Provable bounds for noise-free expectation values computed from noisy samples
• Entanglement Production and Convergence Properties of the Variational Quantum Eigensolver
• Encoding-Independent Optimization Problem Formulation for Quantum Computing
• Fermionic Quantum Approximate Optimization Algorithm
• Quantum algorithms for scientific computing
• High-Round QAOA for MAX $k$-SAT on Trapped Ion NISQ Devices
• Avoiding local minima in Variational Quantum Algorithms with Neural Networks
• Encoding trade-offs and design toolkits in quantum algorithms for discrete optimization: coloring, routing, scheduling, and other problems
• Calibrating the Classical Hardness of the Quantum Approximate Optimization Algorithm
• Mixer-Phaser Ansätze for Quantum Optimization with Hard Constraints
• QED driven QAOA for network-flow optimization
• Fair Sampling Error Analysis on NISQ Devices
• Efficient Quantum Simulation of QCD Jets on the Light Front
• Parity Quantum Optimization: Encoding Constraints
• Performance Analysis of Multi-Angle QAOA for p > 1
• Multi-Objective Optimization and Network Routing with Near-Term Quantum Computers
• Robustness of Variational Quantum Algorithms against stochastic parameter perturbation
• Trainability Barriers in Low-Depth QAOA Landscapes
• From Ansätze to Z-gates: a NASA View of Quantum Computing
• Approximating under the Influence of Quantum Noise and Compute Power
• Progress towards analytically optimal angles in quantum approximate optimisation
• Implementing Jastrow--Gutzwiller operators on a quantum computer using the cascaded variational quantum eigensolver algorithm
• Amplitude amplification-inspired QAOA: Improving the success probability for solving 3SAT
• Prog-QAOA: Framework for resource-efficient quantum optimization through classical programs
• Planning for Compilation of a Quantum Algorithm for Graph Coloring
• Analytical results for the Quantum Alternating Operator Ansatz with Grover Mixer
• Quantum approximate optimization algorithm with random and subgraph phase operators
• Systematic study on the dependence of the warm-start quantum approximate optimization algorithm on approximate solutions
• Diagrammatic Analysis for Parameterized Quantum Circuits
• Efficient Quantum Circuits based on the Quantum Natural Gradient
• A framework for optimal quantum spatial search using alternating phase-walks
• A quantum algorithm to count weighted ground states of classical spin Hamiltonians
• Compressed space quantum approximate optimization algorithm for constrained combinatorial optimization
• LX-mixers for QAOA: Optimal mixers restricted to subspaces and the stabilizer formalism
• Inductive Construction of Variational Quantum Circuit for Constrained Combinatorial Optimization
• Out of the Loop: Structural Approximation of Optimisation Landscapes and non-Iterative Quantum Optimisation
• Experimental Demonstration of Fermionic QAOA with One-Dimensional Cyclic Driver Hamiltonian
• Depth scaling of unstructured search via quantum approximate optimization
• Lower Bounds on Circuit Depth of the Quantum Approximate Optimization Algorithm
• The Lie Algebra of XY-mixer Topologies and Warm Starting QAOA for Constrained Optimization
• IF-QAOA: A Penalty-Free Approach to Accelerating Constrained Quantum Optimization
• Biased Degenerate Ground-State Sampling of Small Ising Models with Converged QAOA
• A Cyclic Layerwise QAOA Training
• Dual Map Framework for Noise Characterization of Quantum Computers
• Freedom of mixer rotation-axis improves performance in the quantum approximate optimization algorithm
• Quick design of feasible tensor networks for constrained combinatorial optimization
• Predict and Conquer: Navigating Algorithm Trade-offs with Quantum Design Automation
• An Analysis of the Quantum Approximation Optimisation Algorithm
• Efficient QAOA Architecture for Solving Multi-Constrained Optimization Problems
• Role of overparametrization in quantum approximate optimization
• Quantum approximate optimization of finite-state bosonic systems
• Resource-Efficient Quantum Optimization via Higher-Order Encoding
• Constrained Quantum Optimization via Iterative Warm-Start XY-Mixers
• Encodings of the weighted MAX k-CUT on qubit systems
• Electric Power Demand Portfolio Optimization by Fermionic QAOA with Self-Consistent Local Field Modulation
• Topological and geometric patterns in optimal bang-bang protocols for variational quantum algorithms: application to the $XXZ$ model on the square lattice
• Universal Euler-Cartan Circuits for Quantum Field Theories
• Synthesis of Energy-Conserving Quantum Circuits with XY interaction
• Expanding the reach of quantum optimization with fermionic embeddings
• Investigating layer-selective transfer learning of QAOA parameters for Max-Cut problem