Efficient QAOA Architecture for Solving Multi-Constrained Optimization Problems
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917132627869696 |
|---|---|
| author | Bucher, David Porawski, Daniel Janetschek, Maximilian Stein, Jonas O'Meara, Corey Cortiana, Giorgio Linnhoff-Popien, Claudia |
| author_facet | Bucher, David Porawski, Daniel Janetschek, Maximilian Stein, Jonas O'Meara, Corey Cortiana, Giorgio Linnhoff-Popien, Claudia |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_03115 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Efficient QAOA Architecture for Solving Multi-Constrained Optimization Problems Bucher, David Porawski, Daniel Janetschek, Maximilian Stein, Jonas O'Meara, Corey Cortiana, Giorgio Linnhoff-Popien, Claudia Quantum Physics 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. |
| title | Efficient QAOA Architecture for Solving Multi-Constrained Optimization Problems |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2506.03115 |