Evaluating Quantum Optimization for Dynamic Self-Reliant Community Detection
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_ | 1866913549724418048 |
|---|---|
| author | Bucher, David Porawski, Daniel Wimmer, Benedikt Nüßlein, Jonas O'Meara, Corey Mohseni, Naeimeh Cortiana, Giorgio Linnhoff-Popien, Claudia |
| author_facet | Bucher, David Porawski, Daniel Wimmer, Benedikt Nüßlein, Jonas O'Meara, Corey Mohseni, Naeimeh Cortiana, Giorgio Linnhoff-Popien, Claudia |
| contents | Power grid partitioning is an important requirement for resilient distribution grids. Since electricity production is progressively shifted to the distribution side, dynamic identification of self-reliant grid subsets becomes crucial for operation. This problem can be represented as a modification to the well-known NP-hard Community Detection (CD) problem. We formulate it as a Quadratic Unconstrained Binary Optimization (QUBO) problem suitable for solving using quantum computation{\color{blue}, which is expected to find better-quality partitions faster. The formulation aims to find communities with maximal self-sufficiency and minimal power flowing between them}. To assess quantum optimization for sizeable problems, we apply a hierarchical divisive method that solves sub-problem QUBOs to perform grid bisections. Furthermore, we propose a customization of the Louvain heuristic that includes self-reliance. In the evaluation, we first demonstrate that this problem examines exponential runtime scaling classically. Then, using different IEEE power system test cases, we benchmark the solution quality for multiple approaches: D-Wave's hybrid quantum-classical solvers, classical heuristics, and a branch-and-bound solver. As a result, we observe that the hybrid solvers provide very promising results, both with and without the divisive algorithm, regarding solution quality achieved within a given time frame. Directly utilizing D-Wave's Quantum Annealing (QA) hardware shows inferior partitioning. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_06773 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Evaluating Quantum Optimization for Dynamic Self-Reliant Community Detection Bucher, David Porawski, Daniel Wimmer, Benedikt Nüßlein, Jonas O'Meara, Corey Mohseni, Naeimeh Cortiana, Giorgio Linnhoff-Popien, Claudia Quantum Physics Power grid partitioning is an important requirement for resilient distribution grids. Since electricity production is progressively shifted to the distribution side, dynamic identification of self-reliant grid subsets becomes crucial for operation. This problem can be represented as a modification to the well-known NP-hard Community Detection (CD) problem. We formulate it as a Quadratic Unconstrained Binary Optimization (QUBO) problem suitable for solving using quantum computation{\color{blue}, which is expected to find better-quality partitions faster. The formulation aims to find communities with maximal self-sufficiency and minimal power flowing between them}. To assess quantum optimization for sizeable problems, we apply a hierarchical divisive method that solves sub-problem QUBOs to perform grid bisections. Furthermore, we propose a customization of the Louvain heuristic that includes self-reliance. In the evaluation, we first demonstrate that this problem examines exponential runtime scaling classically. Then, using different IEEE power system test cases, we benchmark the solution quality for multiple approaches: D-Wave's hybrid quantum-classical solvers, classical heuristics, and a branch-and-bound solver. As a result, we observe that the hybrid solvers provide very promising results, both with and without the divisive algorithm, regarding solution quality achieved within a given time frame. Directly utilizing D-Wave's Quantum Annealing (QA) hardware shows inferior partitioning. |
| title | Evaluating Quantum Optimization for Dynamic Self-Reliant Community Detection |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2407.06773 |