Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2511.00582

Towards Quantum Algorithms for the Optimization of Spanning Trees: The Power Distribution Grids Use Case

Carsten Hartmann, Nil Rodellas-Gràcia, Christian Wallisch, Thiemo Pesch, Frank K. Wilhelm, Dirk Witthaut, Tobias Stollenwerk, Andrea Benigni

Published Nov 1, 2025• 0 citations
arXivHTMLPDF

Abstract

Optimizing the topology of networks is an important challenge across engineering disciplines. In energy systems, network reconfiguration can substantially reduce losses and costs and thus support the energy transition. Unfortunately, many related optimization problems are NP hard, restricting practical applications. In this article, we address the problem of minimizing losses in radial networks, a problem that routinely arises in distribution grid operation. We show that even the computation of approximate solutions is computationally hard and propose quantum optimization as a promising alternative. We derive two quantum algorithmic primitives based on the Quantum Alternating Operator Ansatz (QAOA) that differ in the sampling of network topologies: a tailored sampling of radial topologies and simple sampling with penalty terms to suppress non-radial topologies. We show how to apply these algorithmic primitives to distribution grid reconfiguration and quantify the necessary quantum resources.

DOI
10.48550/arxiv.2511.00582

Related papers

Quantum Combinatorial Optimization Algorithms for Network Reconfiguration: QRAO vs. QAOA

Anh Phuong Ngo, Hieu Trung Nguyen

This paper reviews a hybrid quantum-classical distributed algorithm for NP-hard combinatorial optimization problems, which is embedded in IBM Qiskit's Alternating Direction Method of Multipliers (ADMM) optimizer. We demonstrate a proof of concept for solving Mixed-Integer Convex Programs (MICP) in power system applications using a use case on power distribution network reconfiguration in IBM quantum computers. Using the Qiskit ADMM optimizer, the MICP is decomposed into two subproblems: a quadratic unconstrained binary optimization (QUBO) solved by quantum algorithms and a convex one solved by classical solvers. Our essential contribution is integrating the Quantum Random Access Optimization (QRAO) into the quantum-classical distributed framework and the existing Quantum Approximate Optimization Algorithm (QAOA) implemented in the Qiskit ADMM Optimizer. QRAO utilizes Quantum Random Access Codes (QRACs) to minimize qubit requirements and utilizes quantum state rounding for solution extraction. We examine the impact of noise on solutions derived from QRAO and compare them with results from QAOA using a use case on network reconfiguration in response to faults in the power distribution system.

North American Power Symposium (NAPS)•Oct 13, 2024•6 citations

Quantum Resource Estimation for Minimising Energy Grid Losses

Camille de Valk, Milou van Nederveen, Koen Reerink +1 more

Distribution network reconfiguration (DNR) can minimise power losses by identifying the optimal topology of the electricity grid. Determining the minimum loss configuration is NP-hard, and classical optimisation methods struggle to scale to real-world distribution grids. This paper explores the use of gate-based quantum computing to solve DNR for power loss reduction. We formulate DNR as a higher-order unconstrained binary optimisation (HUBO) problem, avoiding the need for auxiliary variables, thereby reducing the required number of qubits. This is applied to a real medium voltage (MV) network operated by Alliander, a Dutch distribution system operator (DSO). For each biconnected component in the network graph, we construct the corresponding HUBO, derive the cost and mixer operators, and determine the number of required logical qubits and rotation gates. These are then mapped to physical qubits and execution time estimates using quantum resource estimation (QRE). The results suggest that the quantum resource requirements depend not only on component size but also on structural characteristics such as connectivity and cyclicity. Overall, the novelty of this work lies in directly framing the optimisation problem as a HUBO, applying it to real-world MV networks, and performing a QRE to assess future feasibility.

quant-pharXiv:2605.03467•IET conference proceedings.•May 6, 2026•0 citations

Exploring Network-Related Optimization Problems Using Quantum Heuristics

Zhihui Wang, Eleanor Gilbert Rieffel, Mustafa Adnane +4 more

Network-related connectivity optimization problems are underlying a wide range of applications and are also of high computational complexity. We consider studying network optimization problems using two types of quantum heuristics.One is quantum annealing, and the other Quantum Alternating Operator Ansatz, an extension of the Quantum Approximate Optimization Algorithms for gate-model quantum computation, in which a cost-function based unitary and a non-commuting mixing unitary are applied alternately. We present problem mappings for problems of finding the spanning-tree or spanning-graph of a graph that optimizes certain costs, and a variant that further requires the spanning-tree be degree-bounded. With quantum annealing, all constraints are cast into penalty terms in the cost Hamiltonian, and the solution is encoded as the ground state of the Hamiltonian. We provide three mappings to the quadratic unconstrained binary optimization (QUBO) form, compare the resource requirements, and analyze the tradeoffs. For QAOA, we give special focus on the design of mixers based on the constraints presented in the problem, such that the system evolution remains in a subspace of the full Hilbert space where all constraints are satisfied. In the spanning-tree problem, one such hard constraint is that a mixer applied to a spanning-tree needs also be a spanning tree. This involves checking the connectivity of a subgraph, which is a global condition common for most network-related problems. We show how this feature can be efficiently represented in the mixer in a quantum coherent way, based on manipulation of a descendant-matrix and an adjacent matrix. We further develop a mixer for the spanning-graphs based on the spanning-tree mixer.

•Jan 14, 2019•0 citations

Evaluate Quantum Combinatorial Optimization for Distribution Network Reconfiguration

Ngo, Phuong, Thomas, Christan, Hieu Pham Trung Nguyen +2 more

This paper aims to implement and evaluate the performance of quantum computing on solving combinatorial optimization problems arising from the operations of the power grid. To this end, we construct a novel mixed integer conic programming formulation for the reconfiguration of radial distribution network in response to faults in distribution lines. Comparing to existing bus injection model in the literature, our formulation based the branch flows model is theoretically equivalent without needing non-explainable variables, thus being more numerically stable. The network reconfiguration model is then used as a benchmark to evaluate the performance of quantum computing algorithms in real quantum computers. It shows that while current quantum computing algorithms with fast execution time in quantum computers can be a promising solution candidate, its heuristic nature stem from its theoretical foundation should be considered carefully when applying into power grid optimization problems.

arXiv:2208.07513•Aug 16, 2022•0 citations

Evaluate Quantum Combinatorial Optimization for Distribution Network Reconfiguration

Anh Phuong Ngo, Christan Thomas, Hieu Trung Nguyen +2 more

This paper aims to implement and evaluate the performance of quantum computing on solving combinatorial optimization problems arising from the operations of the power grid. To this end, we construct a novel mixed integer conic programming formulation for the reconfiguration of radial distribution network in response to faults in distribution lines. Comparing to existing bus injection model in the literature, our formulation based the branch flows model is theoretically equivalent without needing non-explainable variables, thus being more numerically stable. The network reconfiguration model is then used as a benchmark to evaluate the performance of quantum computing algorithms in real quantum computers. It shows that while current quantum computing algorithms with fast execution time in quantum computers can be a promising solution candidate, its heuristic nature stem from its theoretical foundation should be considered carefully when applying into power grid optimization problems.

North American Power Symposium (NAPS)•Oct 9, 2022•2 citations

Two-Stage Quantum-Classical Distribution Network Reconfiguration via Cycle-Edge Encoding

Nowar Alashkar, Cade Kennedy, Phillip C. Lotshaw +6 more

Distribution network reconfiguration (DNR) is a combinatorial optimization problem that seeks a low-loss network topology subject to topological and electrical operating constraints. In this work, we propose a two-stage quantum-classical method for DNR. First, an iterative linear-ramp Quantum Alternating Operator Ansatz (LR-QAOA) searches topologically feasible subspaces constructed using a novel cycle-edge encoding. The encoding guarantees that every represented configuration is a spanning tree while allowing the size and coverage of each subspace to be adjusted to the available qubit budget. Second, the resulting sample distribution is used to guide a mixed-integer second-order-cone programming (MISOCP) solver. The method is evaluated on six distribution networks ranging from 33 to 417 buses through ideal simulation and execution on trapped-ion quantum hardware. For the 417-bus network, quantum hardware sampling identifies a configuration within approximately $1.4\%$ of the literature reference loss. Across all six test systems, the MISOCP solver guided by hardware-derived distributions reaches an incumbent within $1\%$ of the target with a lower median solver time than the corresponding unguided solver. These findings establish a concrete framework for applying current quantum hardware to DNR, with the potential to become increasingly competitive as hardware improves.

quant-pharXiv:2609.40264•Oct 1, 2026•0 citations
Optimizing the topology of networks is an important challenge across engineering disciplines. In energy systems, network reconfiguration can substantially reduce losses and costs and thus support the energy transition. Unfortunately, many related optimization problems are NP hard, restricting practical applications. In this article, we address the problem of minimizing losses in radial networks, a problem that routinely arises in distribution grid operation. We show that even the computation of approximate solutions is computationally hard and propose quantum optimization as a promising alternative. We derive two quantum algorithmic primitives based on the Quantum Alternating Operator Ansatz (QAOA) that differ in the sampling of network topologies: a tailored sampling of radial topologies and simple sampling with penalty terms to suppress non-radial topologies. We show how to apply these algorithmic primitives to distribution grid reconfiguration and quantify the necessary quantum resources.
This paper reviews a hybrid quantum-classical distributed algorithm for NP-hard combinatorial optimization problems, which is embedded in IBM Qiskit's Alternating Direction Method of Multipliers (ADMM) optimizer. We demonstrate a proof of concept for solving Mixed-Integer Convex Programs (MICP) in power system applications using a use case on power distribution network reconfiguration in IBM quantum computers. Using the Qiskit ADMM optimizer, the MICP is decomposed into two subproblems: a quadratic unconstrained binary optimization (QUBO) solved by quantum algorithms and a convex one solved by classical solvers. Our essential contribution is integrating the Quantum Random Access Optimization (QRAO) into the quantum-classical distributed framework and the existing Quantum Approximate Optimization Algorithm (QAOA) implemented in the Qiskit ADMM Optimizer. QRAO utilizes Quantum Random Access Codes (QRACs) to minimize qubit requirements and utilizes quantum state rounding for solution extraction. We examine the impact of noise on solutions derived from QRAO and compare them with results from QAOA using a use case on network reconfiguration in response to faults in the power distribution system.
Distribution network reconfiguration (DNR) can minimise power losses by identifying the optimal topology of the electricity grid. Determining the minimum loss configuration is NP-hard, and classical optimisation methods struggle to scale to real-world distribution grids. This paper explores the use of gate-based quantum computing to solve DNR for power loss reduction. We formulate DNR as a higher-order unconstrained binary optimisation (HUBO) problem, avoiding the need for auxiliary variables, thereby reducing the required number of qubits. This is applied to a real medium voltage (MV) network operated by Alliander, a Dutch distribution system operator (DSO). For each biconnected component in the network graph, we construct the corresponding HUBO, derive the cost and mixer operators, and determine the number of required logical qubits and rotation gates. These are then mapped to physical qubits and execution time estimates using quantum resource estimation (QRE). The results suggest that the quantum resource requirements depend not only on component size but also on structural characteristics such as connectivity and cyclicity. Overall, the novelty of this work lies in directly framing the optimisation problem as a HUBO, applying it to real-world MV networks, and performing a QRE to assess future feasibility.
Network-related connectivity optimization problems are underlying a wide range of applications and are also of high computational complexity. We consider studying network optimization problems using two types of quantum heuristics.One is quantum annealing, and the other Quantum Alternating Operator Ansatz, an extension of the Quantum Approximate Optimization Algorithms for gate-model quantum computation, in which a cost-function based unitary and a non-commuting mixing unitary are applied alternately. We present problem mappings for problems of finding the spanning-tree or spanning-graph of a graph that optimizes certain costs, and a variant that further requires the spanning-tree be degree-bounded. With quantum annealing, all constraints are cast into penalty terms in the cost Hamiltonian, and the solution is encoded as the ground state of the Hamiltonian. We provide three mappings to the quadratic unconstrained binary optimization (QUBO) form, compare the resource requirements, and analyze the tradeoffs. For QAOA, we give special focus on the design of mixers based on the constraints presented in the problem, such that the system evolution remains in a subspace of the full Hilbert space where all constraints are satisfied. In the spanning-tree problem, one such hard constraint is that a mixer applied to a spanning-tree needs also be a spanning tree. This involves checking the connectivity of a subgraph, which is a global condition common for most network-related problems. We show how this feature can be efficiently represented in the mixer in a quantum coherent way, based on manipulation of a descendant-matrix and an adjacent matrix. We further develop a mixer for the spanning-graphs based on the spanning-tree mixer.
This paper aims to implement and evaluate the performance of quantum computing on solving combinatorial optimization problems arising from the operations of the power grid. To this end, we construct a novel mixed integer conic programming formulation for the reconfiguration of radial distribution network in response to faults in distribution lines. Comparing to existing bus injection model in the literature, our formulation based the branch flows model is theoretically equivalent without needing non-explainable variables, thus being more numerically stable. The network reconfiguration model is then used as a benchmark to evaluate the performance of quantum computing algorithms in real quantum computers. It shows that while current quantum computing algorithms with fast execution time in quantum computers can be a promising solution candidate, its heuristic nature stem from its theoretical foundation should be considered carefully when applying into power grid optimization problems.
This paper aims to implement and evaluate the performance of quantum computing on solving combinatorial optimization problems arising from the operations of the power grid. To this end, we construct a novel mixed integer conic programming formulation for the reconfiguration of radial distribution network in response to faults in distribution lines. Comparing to existing bus injection model in the literature, our formulation based the branch flows model is theoretically equivalent without needing non-explainable variables, thus being more numerically stable. The network reconfiguration model is then used as a benchmark to evaluate the performance of quantum computing algorithms in real quantum computers. It shows that while current quantum computing algorithms with fast execution time in quantum computers can be a promising solution candidate, its heuristic nature stem from its theoretical foundation should be considered carefully when applying into power grid optimization problems.
Distribution network reconfiguration (DNR) is a combinatorial optimization problem that seeks a low-loss network topology subject to topological and electrical operating constraints. In this work, we propose a two-stage quantum-classical method for DNR. First, an iterative linear-ramp Quantum Alternating Operator Ansatz (LR-QAOA) searches topologically feasible subspaces constructed using a novel cycle-edge encoding. The encoding guarantees that every represented configuration is a spanning tree while allowing the size and coverage of each subspace to be adjusted to the available qubit budget. Second, the resulting sample distribution is used to guide a mixed-integer second-order-cone programming (MISOCP) solver. The method is evaluated on six distribution networks ranging from 33 to 417 buses through ideal simulation and execution on trapped-ion quantum hardware. For the 417-bus network, quantum hardware sampling identifies a configuration within approximately 1.4%1.4\%1.4% of the literature reference loss. Across all six test systems, the MISOCP solver guided by hardware-derived distributions reaches an incumbent within 1%1\%1% of the target with a lower median solver time than the corresponding unguided solver. These findings establish a concrete framework for applying current quantum hardware to DNR, with the potential to become increasingly competitive as hardware improves.