Papers With

← All papers
First page of The Limits of Quantum Computers for Power Flow

The Limits of Quantum Computers for Power Flow

Cameron Khanpour, Samuel Talkington

quant-ph Jul 21, 2026 · v1 eess.SY
formalization verification quantum
Read PDF arXiv abstract Code
TL;DR
All numbered theorems and lemmas bounding the pseudo condition number of DC power flow matrices are formally verified in Lean 4.
Abstract
This letter proves realistic grid properties limit the applicability of quantum computers for power flow. Grids that split into two large regions meeting at only a few buses, common in transmission networks, force the pseudo condition number of the DC susceptance matrix to grow polynomially in the network size, and long chains of lines bridging such regions force quadratic growth, making recent empirical observations rigorous. The bounds also hold with overwhelming probability for arbitrary bounded random line susceptances. Combined with query and tomography lower bounds, this precludes end-to-end quantum advantage for DC power flow at every readout level, and these obstructions persist through AC power flow, optimal power flow, and unit commitment. All proofs are formally verified with accompanying Lean 4 source code.
Problem

Quantum linear system solvers are claimed to give exponential speedups for power flow, but the ill-conditioning of grid matrices may negate any quantum advantage. The question is whether this ill-conditioning is an inherent consequence of transmission network topology.

Approach

The work proves that small balanced separators (bounded treewidth or planarity, typical of transmission grids) force the pseudo condition number of the DC susceptance Laplacian to grow polynomially in network size, and transfer corridors force quadratic growth. Combined with query and tomography lower bounds, these results rule out end-to-end quantum advantage at every readout level. The obstructions are extended through AC power flow, DC-OPF, and NP-hard layers. All numbered results are machine-checked in Lean 4.

Results

Grid families force condition number Omega(n), or Omega(n^2) with macroscopic corridors, making classical Laplacian solvers fast but quantum solvers slow. No readout level passes the quantum advantage criterion, and the obstructions persist through AC power flow, optimal power flow, and unit commitment.