Papers With

← All papers
First page of Proving the Limits of Quantum Power Flow

Proving the Limits of Quantum Power Flow

Cameron Khanpour, Samuel Talkington

quant-ph Jul 21, 2026 · v2 eess.SY
formalization quantum
Read PDF arXiv abstract Code
TL;DR
All numbered results (spectral bounds on susceptance Laplacian conditioning and quantum lower-bound consequences) are machine-checked in Lean 4, with a public repository.
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. This rigorously verifies the empirical results of recent work. We also show that the theory holds without model information with high probability for independent 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 in Lean 4.
Problem

Quantum linear system solvers are promoted as giving exponential speedups for power flow, but prior evidence that grid matrices are ill-conditioned rested on empirical fits to test systems. Such fits cannot rule out well-conditioned grids, which leaves open whether quantum advantage for DC power flow is possible.

Approach

The authors prove that small balanced separators and long transfer corridors in transmission network topology force the pseudo condition number of the DC susceptance Laplacian to grow as Omega(n) and Omega(n^2). The bounds rest on weighted cut arguments for eigenvalue estimates and are extended to random bounded susceptances with high probability. They combine these bounds with known QLS query lower bounds and tomography lower bounds, and carry the consequences through AC power flow, OPF, and unit commitment. Every numbered result is formally verified in Lean 4.

Results

The bounds rule out end-to-end quantum advantage for DC power flow at every readout level, including single-observable estimation, on separator-structured grid families. The obstructions persist through AC power flow, DC-OPF interior point methods, and the NP-hard layers. Nearly-linear classical Laplacian solvers are identified as the right baseline.