The Problem
Power grids require accurate power flow analysis and state estimation to ensure efficient energy distribution and stability. Traditional methods face challenges in solving the high-dimensional, linear equations involved, particularly as grids grow in complexity with the integration of renewable energy sources and dynamic demand patterns. Grid data is stored in large data structures and to optimize data-storage and -processing, these data structures can be ordered in a particular way. Once a good order is found for the data-structure of a particular grid, it can be used for all subsequent calculations over that grid. Finding this order is computationally challenging, and quantum computers may provide a solution for organizations like Alliander that are faced with scaling up their energy grids to meet future demands.
The Solution
n this project we developed a quantum algorithm for matrix reordering, known as qreorder. Finding the optimal matrix order is an NP-hard problem that can be phrased as a combinatorial optimization problem over graphs. This makes the problem suitable to be solved using a quantum annealer, but with an exponential overhead in the number of constraints and the required computational resources to solve it. To reduce the number of constraints for the quantum annealing formulation, we solved the optimization problem using “Benders Cuts”, which iteratively makes the problem formulation more complex until an optimal order is found. At each iteration of the optimization schedule, the quantum annealer is used. The solution is posted on our Quantumapplicationlab Github.
Diagram of the computational workflow for performing power flow analysis. The goal is to solve the equation Ax=b and this process can be optimized by reordering the matrix A, for which we developed a quantum algorithm.
The Benefits
Classical solutions to the problem of finding an optimal matrix order already make use of heuristic computational methods that sacrifice accuracy for speed. The goal in this project was to use quantum heuristics to find (near)optimal solutions, for small real-world energy grids, that could potentially allow for speed-ups with increasing problem sizes while leading to a higher accuracy than classical heuristics. We showed that, using classical pre-processing, we can find optimal orders for grid data of real-world energy grids in Alliander’s management with up to 700 different nodes.
The results of the project were presented at the 11th annual PowerWeb conference at TUDelft in November 2024, where colleagues demonstrated the following poster:
