Constrained mixers for the quantum approximate optimization algorithm

Abstract

The quantum approximate optimization algorithm/quantum alternating operator ansatz (QAOA) is a heuristic to find approximate solutions of combinatorial optimization problems. Most literature is limited to quadratic problems without constraints. However, many practically relevant optimization problems do have (hard) constraints that need to be fulfilled. In this article, we present a framework for constructing mixing operators that restrict the evolution to a subspace of the full Hilbert space given by these constraints; We generalize the "XY"-mixer designed to preserve the subspace of "one-hot" states to the general case of subspaces given by a number of computational basis states. We expose the underlying mathematical structure which reveals more of how mixers work and how one can minimize their cost in terms of number of CX gates, particularly when Trotterization is taken into account. Our analysis also leads to valid Trotterizations for "XY"-mixer with fewer CX gates than is known to date. In view of practical implementations, we also describe algorithms for efficient decomposition into basis gates. Several examples of more general cases are presented and analyzed.

References in corpus (7)

• Variational Quantum Algorithms
• A Quantum Approximate Optimization Algorithm
• Noise-Induced Barren Plateaus in Variational Quantum Algorithms
• Training variational quantum algorithms is NP-hard
• Warm-starting quantum optimization
• Efficient encoding of the weighted MAX k-CUT on a quantum computer using QAOA
• Fundamental limitations on optimization in variational quantum algorithms

Cited by in corpus (24)

• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Barren Plateaus in Variational Quantum Computing
• Benchmarking the performance of portfolio optimization with QAOA
• Alignment between Initial State and Mixer Improves QAOA Performance for Constrained Optimization
• Approaches to Constrained Quantum Approximate Optimization
• Encoding-Independent Optimization Problem Formulation for Quantum Computing
• Encoding trade-offs and design toolkits in quantum algorithms for discrete optimization: coloring, routing, scheduling, and other problems
• Performance Analysis of Multi-Angle QAOA for p > 1
• Convergence of Digitized-Counterdiabatic QAOA: circuit depth versus free parameters
• Multi-Objective Optimization and Network Routing with Near-Term Quantum Computers
• Towards Optimizations of Quantum Circuit Simulation for Solving Max-Cut Problems with QAOA
• Quantum Computing for Discrete Optimization: A Highlight of Three Technologies
• Analytical results for the Quantum Alternating Operator Ansatz with Grover Mixer
• Efficient Quantum Circuits based on the Quantum Natural Gradient
• LX-mixers for QAOA: Optimal mixers restricted to subspaces and the stabilizer formalism
• Inequality constraints in variational quantum circuits with qudits
• Optimization via Quantum Preconditioning
• IF-QAOA: A Penalty-Free Approach to Accelerating Constrained Quantum Optimization
• Constraint-Aware Quantum Optimization via Hamming Weight Operators
• Approximate Quadratization of High-Order Hamiltonians for Combinatorial Quantum Optimization
• Quantum Simulation-Based Optimization for Cooling System Design
• Constrained Quantum Optimization via Iterative Warm-Start XY-Mixers
• Efficient QAOA Architecture for Solving Multi-Constrained Optimization Problems
• Encodings of the weighted MAX k-CUT on qubit systems