Quantum tree generator improves QAOA state-of-the-art for the knapsack problem
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866915717480185856 |
|---|---|
| author | Christiansen, Paul Binkowski, Lennart Ramacciotti, Debora Wilkening, Sören |
| author_facet | Christiansen, Paul Binkowski, Lennart Ramacciotti, Debora Wilkening, Sören |
| contents | This paper introduces a novel approach to the Quantum Approximate Optimization Algorithm (QAOA), specifically tailored to the knapsack problem. We combine the recently proposed quantum tree generator as an efficient state preparation circuit for all feasible solutions to the knapsack problem with the framework of Grover-mixer QAOA to form the first representative of Amplitude Amplification-mixer QAOA (AAM-QAOA). On hard benchmark sets with up to 20 knapsack items, we demonstrate our method's improved performance over the current state-of-the-art Copula-QAOA. However, for larger instance sizes, both approaches fail to deliver better outcomes than greedily packing items in descending value-to-weight ratio, at least for the considered circuit depths. For sufficiently high circuit depths, however, we can prove that AAM-QAOA will eventually be able to sample the optimal solution. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_00518 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Quantum tree generator improves QAOA state-of-the-art for the knapsack problem Christiansen, Paul Binkowski, Lennart Ramacciotti, Debora Wilkening, Sören Quantum Physics This paper introduces a novel approach to the Quantum Approximate Optimization Algorithm (QAOA), specifically tailored to the knapsack problem. We combine the recently proposed quantum tree generator as an efficient state preparation circuit for all feasible solutions to the knapsack problem with the framework of Grover-mixer QAOA to form the first representative of Amplitude Amplification-mixer QAOA (AAM-QAOA). On hard benchmark sets with up to 20 knapsack items, we demonstrate our method's improved performance over the current state-of-the-art Copula-QAOA. However, for larger instance sizes, both approaches fail to deliver better outcomes than greedily packing items in descending value-to-weight ratio, at least for the considered circuit depths. For sufficiently high circuit depths, however, we can prove that AAM-QAOA will eventually be able to sample the optimal solution. |
| title | Quantum tree generator improves QAOA state-of-the-art for the knapsack problem |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2411.00518 |