Towards Less Greedy Quantum Coalition Structure Generation in Induced Subgraph Games
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908450104016896 |
|---|---|
| author | Nüßlein, Jonas Schuman, Daniëlle Bucher, David Mohseni, Naeimeh Ghosh, Kumar O'Meara, Corey Cortiana, Giorgio Linnhoff-Popien, Claudia |
| author_facet | Nüßlein, Jonas Schuman, Daniëlle Bucher, David Mohseni, Naeimeh Ghosh, Kumar O'Meara, Corey Cortiana, Giorgio Linnhoff-Popien, Claudia |
| contents | The transition to 100% renewable energy requires new techniques for managing energy networks, such as dividing them into sensible subsets of prosumers called micro-grids. Doing so in an optimal manner is a difficult optimization problem, as it can be abstracted to the Coalition Structure Generation problem in Induced Subgraph Games, a NP-complete problem which requires dividing an undirected, complete, weighted graph into subgraphs in a way that maximizes the sum of their internal weights. Recently, Venkatesh et al. (arXiv:2212.11372) published a Quantum Annealing (QA)-based iterative algorithm called GCS-Q, which they claim to be the best currently existing solver for the problem in terms of runtime complexity. As this algorithm makes the application of QA to the problem seem promising, but is a greedy one, this work proposes several less greedy QA-based approaches and investigates whether any of them can outperform GCS-Q in terms of solution quality. While we find that this is not the case yet on D-Wave hardware, most of them do when using the classical QBSolv software as a solver. Especially an algorithm we call 4-split iterative R-QUBO shows potential here, finding all optima in our dataset while scaling favorably with the problem size in terms of runtime. Thus, it appears to be interesting for future research on quantum approaches to the problem, assuming QA hardware will become more noise-resilient over time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_04366 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Towards Less Greedy Quantum Coalition Structure Generation in Induced Subgraph Games Nüßlein, Jonas Schuman, Daniëlle Bucher, David Mohseni, Naeimeh Ghosh, Kumar O'Meara, Corey Cortiana, Giorgio Linnhoff-Popien, Claudia Quantum Physics Emerging Technologies The transition to 100% renewable energy requires new techniques for managing energy networks, such as dividing them into sensible subsets of prosumers called micro-grids. Doing so in an optimal manner is a difficult optimization problem, as it can be abstracted to the Coalition Structure Generation problem in Induced Subgraph Games, a NP-complete problem which requires dividing an undirected, complete, weighted graph into subgraphs in a way that maximizes the sum of their internal weights. Recently, Venkatesh et al. (arXiv:2212.11372) published a Quantum Annealing (QA)-based iterative algorithm called GCS-Q, which they claim to be the best currently existing solver for the problem in terms of runtime complexity. As this algorithm makes the application of QA to the problem seem promising, but is a greedy one, this work proposes several less greedy QA-based approaches and investigates whether any of them can outperform GCS-Q in terms of solution quality. While we find that this is not the case yet on D-Wave hardware, most of them do when using the classical QBSolv software as a solver. Especially an algorithm we call 4-split iterative R-QUBO shows potential here, finding all optima in our dataset while scaling favorably with the problem size in terms of runtime. Thus, it appears to be interesting for future research on quantum approaches to the problem, assuming QA hardware will become more noise-resilient over time. |
| title | Towards Less Greedy Quantum Coalition Structure Generation in Induced Subgraph Games |
| topic | Quantum Physics Emerging Technologies |
| url | https://arxiv.org/abs/2408.04366 |