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

• Variational Quantum Algorithms
• Ising formulations of many NP problems
• A Quantum Approximate Optimization Algorithm
• Noise-Induced Barren Plateaus in Variational Quantum Algorithms
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Quantum optimization using variational algorithms on near-term quantum devices
• Training variational quantum algorithms is NP-hard
• QAOA for Max-Cut requires hundreds of qubits for quantum speed-up
• Obstacles to State Preparation and Variational Optimization from Symmetry Protection
• Warm-starting quantum optimization
• Finding Exponential Product Formulas of Higher Orders
• $XY$-mixers: analytical and numerical results for QAOA
• Quantum Annealing for Constrained Optimization
• Applying the Quantum Approximate Optimization Algorithm to the Tail Assignment Problem
• Minimizing State Preparations in Variational Quantum Eigensolver by Partitioning into Commuting Families
• Driver Hamiltonians for constrained optimization in quantum annealing
• Efficient encoding of the weighted MAX k-CUT on a quantum computer using QAOA
• The Quantum Alternating Operator Ansatz on Maximum k-Vertex Cover
• An adaptive quantum approximate optimization algorithm for solving combinatorial problems on a quantum computer
• Term Grouping and Travelling Salesperson for Digital Quantum Simulation
• 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