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

• URL: http://arxiv.org/abs/2511.00582v1
• Date: Sat, 01 Nov 2025 15:12:00 GMT
• Title: Towards Quantum Algorithms for the Optimization of Spanning Trees: The Power Distribution Grids Use Case
• Authors: Carsten Hartmann, Nil Rodellas-Gràcia, Christian Wallisch, Thiemo Pesch, Frank K. Wilhelm, Dirk Witthaut, Tobias Stollenwerk, Andrea Benigni,
• Abstract summary: In energy systems, network reconfiguration can substantially reduce losses and costs.<n>Many related optimization problems are NP hard, restricting practical applications.<n>We show how to apply these algorithmic primitives to distribution grid reconfiguration and quantify the necessary quantum resources.
• Score: 1.6943815984028532
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Tensor Network Formulation of Dequantized Algorithms for Ground State Energy Estimation [2.9436347471485558]
  Dequantization algorithms play a central role in providing a clear theoretical framework to separate complexity of quantum and classical algorithms.<n>Existing dequantized algorithms typically rely on sampling procedures, leading to prohibitively large computational overheads.<n>We propose a tensor network-based dequantization framework for GSEE that eliminates the sampling process while preserving the complexity of prior dequantized algorithms.
  arXiv  Detail & Related papers  (2025-12-15T17:07:04Z)
• Quantum remeshing and efficient encoding for fracture mechanics [0.5541644538483946]
  We present a variational quantum algorithm for structural mechanical problems, specifically addressing crack opening simulations.<n>Our approach provides an alternative solution for a relevant 2D case by implementing a parametrized quantum circuit.<n>Our method has been experimentally validated on Quandela's photonic quantum processor Ascella.
  arXiv  Detail & Related papers  (2025-10-16T14:50:59Z)
• Challenges in Applying Variational Quantum Algorithms to Dynamic Satellite Network Routing [0.0]
  We evaluate two quantum algorithms for dynamic satellite network routing.<n>We find that these algorithms face significant challenges.<n>Negative findings highlight key obstacles that must be addressed before quantum algorithms can offer real advantages.
  arXiv  Detail & Related papers  (2025-08-06T10:25:39Z)
• Knapsack and Shortest Path Problems Generalizations From A Quantum-Inspired Tensor Network Perspective [40.5694560588179]
  We present two quantum-inspired algorithms to solve the knapsack and the shortest path problems.<n>The methods provide an exact equation which returns the optimal solution of the problems.
  arXiv  Detail & Related papers  (2025-06-13T12:27:34Z)
• Resource-Efficient Compilation of Distributed Quantum Circuits for Solving Large-Scale Wireless Communication Network Problems [10.434368470402935]
  optimizing routing in Wireless Sensor Networks (WSNs) is pivotal for minimizing energy consumption and extending network lifetime.<n>This paper introduces a resourceefficient compilation method for distributed quantum circuits tailored to address large-scale WSN routing problems.
  arXiv  Detail & Related papers  (2025-01-17T15:10:22Z)
• Bayesian Parameterized Quantum Circuit Optimization (BPQCO): A task and hardware-dependent approach [49.89480853499917]
  Variational quantum algorithms (VQA) have emerged as a promising quantum alternative for solving optimization and machine learning problems. In this paper, we experimentally demonstrate the influence of the circuit design on the performance obtained for two classification problems. We also study the degradation of the obtained circuits in the presence of noise when simulating real quantum computers.
  arXiv  Detail & Related papers  (2024-04-17T11:00:12Z)
• Evaluating the Practicality of Quantum Optimization Algorithms for Prototypical Industrial Applications [44.88678858860675]
  We investigate the application of the quantum approximate optimization algorithm (QAOA) and the quantum adiabatic algorithm (QAA) to the solution of a prototypical model in this field. We compare the performance of these two algorithms in terms of solution quality, using selected evaluation metrics.
  arXiv  Detail & Related papers  (2023-11-20T09:09:55Z)
• Optimizing Tensor Network Contraction Using Reinforcement Learning [86.05566365115729]
  We propose a Reinforcement Learning (RL) approach combined with Graph Neural Networks (GNN) to address the contraction ordering problem. The problem is extremely challenging due to the huge search space, the heavy-tailed reward distribution, and the challenging credit assignment. We show how a carefully implemented RL-agent that uses a GNN as the basic policy construct can address these challenges.
  arXiv  Detail & Related papers  (2022-04-18T21:45:13Z)
• DESTRESS: Computation-Optimal and Communication-Efficient Decentralized Nonconvex Finite-Sum Optimization [43.31016937305845]
  Internet-of-things, networked sensing, autonomous systems and federated learning call for decentralized algorithms for finite-sum optimizations. We develop DEcentralized STochastic REcurSive methodDESTRESS for non finite-sum optimization. Detailed theoretical and numerical comparisons show that DESTRESS improves upon prior decentralized algorithms.
  arXiv  Detail & Related papers  (2021-10-04T03:17:41Z)
• Entanglement Rate Optimization in Heterogeneous Quantum Communication Networks [79.8886946157912]
  Quantum communication networks are emerging as a promising technology that could constitute a key building block in future communication networks in the 6G era and beyond. Recent advances led to the deployment of small- and large-scale quantum communication networks with real quantum hardware. In quantum networks, entanglement is a key resource that allows for data transmission between different nodes.
  arXiv  Detail & Related papers  (2021-05-30T11:34:23Z)
• Purification and Entanglement Routing on Quantum Networks [55.41644538483948]
  A quantum network equipped with imperfect channel fidelities and limited memory storage time can distribute entanglement between users. We introduce effectives enabling fast path-finding algorithms for maximizing entanglement shared between two nodes on a quantum network.
  arXiv  Detail & Related papers  (2020-11-23T19:00:01Z)
• Adaptive pruning-based optimization of parameterized quantum circuits [62.997667081978825]
  Variisy hybrid quantum-classical algorithms are powerful tools to maximize the use of Noisy Intermediate Scale Quantum devices. We propose a strategy for such ansatze used in variational quantum algorithms, which we call "Efficient Circuit Training" (PECT) Instead of optimizing all of the ansatz parameters at once, PECT launches a sequence of variational algorithms.
  arXiv  Detail & Related papers  (2020-10-01T18:14:11Z)
• TIGER: Topology-aware Assignment using Ising machines Application to Classical Algorithm Tasks and Quantum Circuit Gates [2.4047296366832307]
  A mapping problem exists in gate-based quantum computing where the objective is to map tasks to gates in a topology fashion. Existing task approaches are either or based on physical optimization algorithms, providing different speed and solution quality trade-offs. We propose an algorithm that allows solving the topology-aware assignment problem using Ising machines.
  arXiv  Detail & Related papers  (2020-09-21T19:46:59Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem. We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
  arXiv  Detail & Related papers  (2020-09-15T18:17:27Z)

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.