An Exclusive-Sum-of-Products Pipeline for QAOA
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909760201162752 |
|---|---|
| author | Brunet, Matthew Shah, Shilpi Atallah, Mostafa Wilkie, Anthony Herrman, Rebekah |
| author_facet | Brunet, Matthew Shah, Shilpi Atallah, Mostafa Wilkie, Anthony Herrman, Rebekah |
| contents | The quantum approximate optimization algorithm is commonly used to solve combinatorial optimization problems. While unconstrained problems map naturally into the algorithm, incorporating constraints typically requires penalizing constraint violations in the objective function. In this work, we propose an alternative approach that encodes constraints as Boolean expressions in exclusive-sum-of-products (ESOP) form before penalization. We test this method on the maximum independent set problem using graphs with 3 to 20 vertices and find that ESOP constraint formulations achieve higher approximation ratios than standard constraint penalization methods, with percent increases of up to 30.3%. Furthermore, ESOP constraint formulations result in higher approximation ratios than standard QAOA penalization approaches after one layer of the algorithm on approximately 64% of the tested graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_21686 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | An Exclusive-Sum-of-Products Pipeline for QAOA Brunet, Matthew Shah, Shilpi Atallah, Mostafa Wilkie, Anthony Herrman, Rebekah Quantum Physics The quantum approximate optimization algorithm is commonly used to solve combinatorial optimization problems. While unconstrained problems map naturally into the algorithm, incorporating constraints typically requires penalizing constraint violations in the objective function. In this work, we propose an alternative approach that encodes constraints as Boolean expressions in exclusive-sum-of-products (ESOP) form before penalization. We test this method on the maximum independent set problem using graphs with 3 to 20 vertices and find that ESOP constraint formulations achieve higher approximation ratios than standard constraint penalization methods, with percent increases of up to 30.3%. Furthermore, ESOP constraint formulations result in higher approximation ratios than standard QAOA penalization approaches after one layer of the algorithm on approximately 64% of the tested graphs. |
| title | An Exclusive-Sum-of-Products Pipeline for QAOA |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2508.21686 |