Evaluating Quantum Optimization for Dynamic Self-Reliant Community Detection
- URL: http://arxiv.org/abs/2407.06773v2
- Date: Wed, 16 Oct 2024 15:24:37 GMT
- Title: Evaluating Quantum Optimization for Dynamic Self-Reliant Community Detection
- Authors: David Bucher, Daniel Porawski, Benedikt Wimmer, Jonas Nüßlein, Corey O'Meara, Naeimeh Mohseni, Giorgio Cortiana, Claudia Linnhoff-Popien,
- Abstract summary: We formulate a Quadratic Unconstrained Binary Optimization (QUBO) problem suitable for solving using quantum computationcolorblue.
The formulation aims to find communities with maximal self-sufficiency and minimal power flowing between them.
We benchmark the solution quality for multiple approaches: D-Wave's hybrid quantum-classical solvers, classicals, and a branch-and-bound solver.
- Score: 3.6021182997326022
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: 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.
Related papers
- A hybrid Quantum-Classical Algorithm for Mixed-Integer Optimization in Power Systems [0.0]
We present a framework for solving power system optimization problems with a Quantum Computer (QC)
Our guiding applications are the optimal transmission switching and the verification of neural networks trained to solve a DC Optimal Power Flow.
arXiv Detail & Related papers (2024-04-16T16:11:56Z) - Hierarchical Multigrid Ansatz for Variational Quantum Algorithms [1.5448433683670526]
Quantum computing promises to enhance supercomputing using fundamental physics.
In the near term, the best candidate algorithms for achieving this advantage are variational quantum algorithms (VQAs)
We design and numerically evaluate a novel ansatz for VQAs, focusing in particular on the variational quantum eigensolver (VQE)
We show through numerical simulation that the multigrid ansatz outperforms the standard hardware-efficient ansatz in terms of solution quality for the Laplacian eigensolver.
arXiv Detail & Related papers (2023-12-22T20:22:43Z) - A Hybrid Quantum-Classical Approach to the Electric Mobility Problem [0.8796261172196743]
We suggest a hybrid quantum-classical routine for the NP-hard Electric Vehicle Fleet Charging and Allocation Problem.
We benchmark the performance of the decomposition technique with classical and quantum-inspired metaheuristics.
The major advantage of the proposed approach is that it enables quantum-based methods for this realistic problem with many inequality constraints.
arXiv Detail & Related papers (2023-10-04T12:14:56Z) - An Optimization-based Deep Equilibrium Model for Hyperspectral Image
Deconvolution with Convergence Guarantees [71.57324258813675]
We propose a novel methodology for addressing the hyperspectral image deconvolution problem.
A new optimization problem is formulated, leveraging a learnable regularizer in the form of a neural network.
The derived iterative solver is then expressed as a fixed-point calculation problem within the Deep Equilibrium framework.
arXiv Detail & Related papers (2023-06-10T08:25:16Z) - Quantum-inspired optimization for wavelength assignment [51.55491037321065]
We propose and develop a quantum-inspired algorithm for solving the wavelength assignment problem.
Our results pave the way to the use of quantum-inspired algorithms for practical problems in telecommunications.
arXiv Detail & Related papers (2022-11-01T07:52:47Z) - Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
Multi-Object Tracking (MOT) is most often approached in the tracking-by-detection paradigm, where object detections are associated through time.
As these optimization problems are often NP-hard, they can only be solved exactly for small instances on current hardware.
We show that our approach is competitive compared with state-of-the-art optimization-based approaches, even when using of-the-shelf integer programming solvers.
arXiv Detail & Related papers (2022-02-17T18:59:20Z) - Testing a QUBO Formulation of Core-periphery Partitioning on a Quantum
Annealer [3.093890460224435]
We present a new kernel that quantifies success for the task of computing a core-periphery partition for an undirected network.
Finding the associated optimal partitioning may be expressed in the form of a quadratic unconstrained binary optimization problem.
We compare this approach with existing core-periphery partitioning methods.
arXiv Detail & Related papers (2022-01-05T11:08:09Z) - Hybrid Quantum-Classical Multi-cut Benders Approach with a Power System
Application [0.0]
A quantum-classical (HQC) solution to the Unit Commitment (UC) problem is presented.
The validity and computational viability of the proposed approach are demonstrated using the D-Wave Advantage 4.1 quantum annealer.
arXiv Detail & Related papers (2021-12-10T16:16:09Z) - Quadratic Unconstrained Binary Optimisation via Quantum-Inspired
Annealing [58.720142291102135]
We present a classical algorithm to find approximate solutions to instances of quadratic unconstrained binary optimisation.
We benchmark our approach for large scale problem instances with tuneable hardness and planted solutions.
arXiv Detail & Related papers (2021-08-18T09:26:17Z) - Accelerating variational quantum algorithms with multiple quantum
processors [78.36566711543476]
Variational quantum algorithms (VQAs) have the potential of utilizing near-term quantum machines to gain certain computational advantages.
Modern VQAs suffer from cumbersome computational overhead, hampered by the tradition of employing a solitary quantum processor to handle large data.
Here we devise an efficient distributed optimization scheme, called QUDIO, to address this issue.
arXiv Detail & Related papers (2021-06-24T08:18:42Z) - Cross Entropy Hyperparameter Optimization for Constrained Problem
Hamiltonians Applied to QAOA [68.11912614360878]
Hybrid quantum-classical algorithms such as Quantum Approximate Optimization Algorithm (QAOA) are considered as one of the most encouraging approaches for taking advantage of near-term quantum computers in practical applications.
Such algorithms are usually implemented in a variational form, combining a classical optimization method with a quantum machine to find good solutions to an optimization problem.
In this study we apply a Cross-Entropy method to shape this landscape, which allows the classical parameter to find better parameters more easily and hence results in an improved performance.
arXiv Detail & Related papers (2020-03-11T13:52:41Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.