Efficient QAOA Architecture for Solving Multi-Constrained Optimization Problems

Abstract

This paper proposes a novel combination of constraint encoding methods for the Quantum Approximate Optimization Ansatz (QAOA). Real-world optimization problems typically consist of multiple types of constraints. To solve these optimization problems with quantum methods, normally, all constraints are added as quadratic penalty terms to the objective, which expands the search space and increases problem complexity. This work proposes a general workflow that extracts and encodes specific constraints directly into the circuit of QAOA: One-hot constraints are enforced through $XY$-mixers that restrict the search space to the feasible sub-space naturally. Inequality constraints are implemented through oracle-based Indicator Functions (IF). This paper focuses on the numerical benchmarks of the combined approach for solving the Multi-Knapsack (MKS) and the Prosumer Problem (PP), a modification of the MKS in the domain of electricity optimization. To this end, we introduce computational techniques that efficiently simulate the two presented constraint architectures. Since $XY$-mixers restrict the search space, specific state vector entries are always zero and can be omitted from the simulation, saving valuable memory and computing resources. We benchmark the combined method against the established QUBO formulation, yielding a better solution quality and probability of sampling the optimal solution. Despite more complex circuits, the time-to-solution is more than an order of magnitude faster compared to the baseline methods and exhibits more favorable scaling properties.

References in corpus (26)

• SciPy 1.0--Fundamental Algorithms for Scientific Computing in Python
• Ising formulations of many NP problems
• Adiabatic Quantum Computing
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• $XY$-mixers: analytical and numerical results for QAOA
• Challenges and Opportunities in Quantum Optimization
• Quantum annealing initialization of the quantum approximate optimization algorithm
• Efficient quantum algorithms for $GHZ$ and $W$ states, and implementation on the IBM quantum computer
• Grover Mixers for QAOA: Shifting Complexity from Mixer Design to State Preparation
• Hybrid quantum-classical algorithms for approximate graph coloring
• On the representation of Boolean and real functions as Hamiltonians for quantum computing
• The Quantum Alternating Operator Ansatz on Maximum k-Vertex Cover
• Constrained mixers for the quantum approximate optimization algorithm
• Unbalanced penalization: A new approach to encode inequality constraints of combinatorial problems for quantum optimization algorithms
• Constrained Optimization via Quantum Zeno Dynamics
• Assessing Quantum Computing Performance for Energy Optimization in a Prosumer Community
• Quantum approximate optimization algorithm for qudit systems
• Towards a Linear-Ramp QAOA protocol: Evidence of a scaling advantage in solving some combinatorial optimization problems
• rustworkx: A High-Performance Graph Library for Python
• Quantum Computing Techniques for Multi-Knapsack Problems
• Fast Simulation of High-Depth QAOA Circuits
• JuliQAOA: Fast, Flexible QAOA Simulation
• A quantum algorithm for solving 0-1 Knapsack problems
• Quantum optimization with linear Ising penalty functions for customer data science
• Quantum Relaxation for Solving Multiple Knapsack Problems