Partitioned-Constraint QAOA (PC-QAOA): Structural State Preparation and Penalty Enforcement for Quantum Optimization
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_ | 1866916023527014400 |
|---|---|
| author | Wilkie, Anthony DeLise, Alexander Del Real, Andrew Herrman, Rebekah Ostrowski, James |
| author_facet | Wilkie, Anthony DeLise, Alexander Del Real, Andrew Herrman, Rebekah Ostrowski, James |
| contents | Constrained combinatorial optimization remains challenging for quantum algorithms because feasibility must be explicitly enforced, typically through penalty terms or problem-specific mixers. We introduce Partitioned-Constraint QAOA (PC-QAOA), which partitions constraints into those enforced structurally and those enforced energetically. Structural constraints are handled via feasible-state preparation and a Grover mixer that preserves feasibility, while the remaining constraints are enforced through penalties. We show that constraints with disjoint support can be prepared in parallel with little error accumulation. We identify broad classes of constraints (including cardinality, assignment, and flow conservation) that admit efficient structural enforcement, and introduce a variational gadget construction that extends this approach to arbitrary low-support constraints. Across 413 completed instances spanning multiple constraint families, PC-QAOA substantially improves feasibility and solution quality at shallow depth relative to penalty-based QAOA, demonstrating the value of partial structural enforcement. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_02590 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Partitioned-Constraint QAOA (PC-QAOA): Structural State Preparation and Penalty Enforcement for Quantum Optimization Wilkie, Anthony DeLise, Alexander Del Real, Andrew Herrman, Rebekah Ostrowski, James Quantum Physics Constrained combinatorial optimization remains challenging for quantum algorithms because feasibility must be explicitly enforced, typically through penalty terms or problem-specific mixers. We introduce Partitioned-Constraint QAOA (PC-QAOA), which partitions constraints into those enforced structurally and those enforced energetically. Structural constraints are handled via feasible-state preparation and a Grover mixer that preserves feasibility, while the remaining constraints are enforced through penalties. We show that constraints with disjoint support can be prepared in parallel with little error accumulation. We identify broad classes of constraints (including cardinality, assignment, and flow conservation) that admit efficient structural enforcement, and introduce a variational gadget construction that extends this approach to arbitrary low-support constraints. Across 413 completed instances spanning multiple constraint families, PC-QAOA substantially improves feasibility and solution quality at shallow depth relative to penalty-based QAOA, demonstrating the value of partial structural enforcement. |
| title | Partitioned-Constraint QAOA (PC-QAOA): Structural State Preparation and Penalty Enforcement for Quantum Optimization |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2508.02590 |