Pith. sign in

REVIEW 4 major objections 5 minor 22 references

Realistic grid topology forces power-flow matrices to be ill-conditioned, ruling out end-to-end quantum advantage.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-01 12:55 UTC pith:JO6TF7TZ

load-bearing objection The separator lower bounds are real and the corridor argument is nice, but the 'no advantage at every readout level' conclusion only holds for constant-separator families; the planar case leaves scalar readout open, and the grid-topology premise is asserted, not demonstrated. the 4 major comments →

arxiv 2607.19263 v1 pith:JO6TF7TZ submitted 2026-07-21 quant-ph cs.SYeess.SY

The Limits of Quantum Computers for Power Flow

Cameron Khanpour , Samuel Talkington This is my paper
classification quant-ph cs.SYeess.SY MSC 05C5065F3568Q1281P68
keywords quantum power flowDC power flowcondition numbergraph Laplaciangraph separatorstreewidthquantum linear system algorithmslower bounds
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Quantum linear-system solvers have been proposed as exponential accelerators for DC power flow, but their costs depend on the condition number of the susceptance matrix. This paper proves that realistic transmission-grid topology forces that condition number to grow with network size: any grid split into two large regions joined by few buses has condition number at least linear in the network size, and long inter-area corridors force quadratic growth. These are structural lower bounds, not empirical fits, and they hold with overwhelming probability even when line susceptances are random bounded variables. Combined with quantum query and tomography lower bounds, they rule out end-to-end quantum advantage for DC power flow at every readout level, including reading a single scalar, and the obstruction extends to AC power flow, optimal power flow, and unit commitment. The result matters because it makes the ill-conditioning obstacle provable and redirects the search for speedups toward classical nearly-linear Laplacian solvers.

Core claim

Ill-conditioning of the DC power-flow matrix is structural, not a benchmark artifact. For the susceptance Laplacian B, the key identity is κ+(B) ≥ [2γ(1−γ)/b(∂S)] max{b(E), n max b_e}: any balanced cut with small interface stiffness forces a large pseudo condition number. Bounded-treewidth or planar graphs supply such cuts, giving κ+(B)=Ω(n/(Δτ)) or Ω(√n/Δ); long inter-area corridors supply the sharper Ω(n²). Because quantum linear-system solvers need Ω(κ) queries and classical output costs a tomography factor, no QLS-based algorithm can beat classical eO(m log(1/ε)) Laplacian solvers on these grids — even reading one scalar is not cheaper. The obstruction persists through AC power flow, DC-

What carries the argument

The load-bearing object is the pseudo condition number κ+(B)=λmax(B)/λ2(B) of the weighted graph Laplacian B=Aᵀ diag(b_e) A — the matrix inverted in DC power flow. The mechanism is a weighted-cut identity: for any balanced cut S, if the interface stiffness b(∂S) is small compared with total stiffness b(E), then κ+(B) is forced large. Separator theorems (bounded treewidth, planarity) and corridor constructions provide such cuts — the former with separators of size √n or τ, the latter with a smallest nonzero eigenvalue of order 1/(nℓ²) — converting topology directly into the Ω(κ) query bottleneck that quantum linear-system solvers cannot avoid.

Load-bearing premise

The load-bearing premise is that real transmission grids belong to the defined grid family — bounded degree, bounded treewidth/separator size, and average line susceptance a constant fraction of the maximum — a premise the paper asserts on structural grounds but does not establish from grid measurements; if a real grid lacked such a balanced cut, the polynomial condition-number floor would not apply.

What would settle it

Find a real or synthetic graph with a small balanced separator and b̄/b_max=Ω(1) whose DC susceptance Laplacian has pseudo condition number growing sublinearly with n; that would contradict Lemma 1/Theorem 1. Alternatively, construct an expander-like family with no small separator/corridor and show κ+(B)=O(1): this would show topology alone does not force ill-conditioning outside realistic grid families, delimiting the paper's claim.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • On any grid family satisfying the structural definitions, producing a classical DCPF solution costs eΩ(n²/ε) quantum queries versus eO(n log(1/ε)) classically; with corridors the gap widens to eΩ(n³/ε).
  • The quadratic conditioning lower bound matches the empirical κ∼N² observations and upgrades that fit to a theorem about transfer corridors.
  • No readout level passes the advantage criterion: substituting the provable κ=Ω(N) into Dκ^{3/2} ≪ N/d forces D≪N^{−1/2}, so even a single scalar observable is out of reach.
  • Because the weighted Laplacian reappears in the flat-start AC Jacobian and in every DC-OPF interior-point Newton system, the no-advantage result propagates to AC power flow, security-constrained OPF, and unit commitment.
  • The same separator/weak-cut structure that makes quantum solvers slow is what classical Laplacian solvers exploit, so the paper's baseline standard is nearly-linear classical time with logarithmic conditioning dependence.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Editorial inference: Because the bound is topological and survives random susceptances, the only topology left open for QLS-style speedups is an expander-like graph with no balanced separator or corridor; a concrete next test is measuring κ(B) on such synthetic grids.
  • Editorial inference: The weighted-cut lemma is generic for graph Laplacians, so analogous topology-forces-conditioning arguments may hold in other QLS application domains built on structured graphs, such as resistor-network simulation, Markov-chain mixing, or finite-element systems.
  • Editorial inference: The machine-verified proof enables a practical certificate pipeline: for any benchmark grid, one can certify a lower bound on κ by finding a balanced cut with small b(∂S)/b(E), giving a cheap classical warning that no QLS-based quantum algorithm can win on that instance.
  • Editorial inference: The conclusion is conditional on the grid-family definition; if real transmission data show sublinear separator growth or extreme susceptance heterogeneity, the Ω(n) floor would need revisiting. The natural empirical check is to compute separator sizes and κ on large operational grids.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

4 major / 5 minor

Summary. The paper proves lower bounds on the pseudo condition number of the DC susceptance Laplacian for graphs with small balanced separators (Theorem 1), longer transfer corridors (Proposition 1), and for random susceptances (Proposition 2). It combines these with existing query and tomography lower bounds to argue that no end-to-end quantum advantage exists for DC power flow on 'grid families' defined by constant separator size, treewidth, and bounded susceptance ratio. The paper also claims these obstructions extend to AC power flow, OPF, and unit commitment. All numbered results in Sections II–III are claimed to be formally verified in Lean 4.

Significance. If the topological assumptions it codifies are met, the paper provides a rigorous, parameter-free explanation of the empirical κ~N² behavior and a clear query-complexity obstruction to QLS-based quantum power flow. The formal verification and explicit use of the [5] advantage criterion are genuine strengths. However, the central 'every readout level' claim is only proved for constant-size separators, not for planar/near-planar grids, and the empirical premise that real grids satisfy that condition is not demonstrated.

major comments (4)
  1. [Section III, Prop. 3 and Corollary 1(ii)] The no-advantage claim at every readout level rests on κ=Ω(n), obtained from the grid-family assumption s=O(1). For planar graphs, Corollary 1(ii) yields only κ=Ω(√n/Δ). Since Section II explicitly treats near-planarity as a realistic grid model, Proposition 3 does not apply. Under the [5] criterion D κ^{3/2} ≪ n/d, a planar family with κ~√n satisfies the criterion for scalar readout D=1 when n is large (n^{3/4} ≪ n/d for constant d). Thus the paper does not preclude scalar-readout quantum advantage for planar/near-planar grids; it only precludes it for bounded-treewidth/constant-separator families.
  2. [Section II, 'Transmission networks supply such cuts...'] The phrase 'small balanced separators (equivalently bounded treewidth or planarity)' is mathematically incorrect: planar graphs have separators of size O(√n), not O(1), and bounded treewidth is strictly stronger. This conflation drives the definition of 'grid family' in Section III, where s=O(1) is assumed. The authors should correct the equivalence and separate the two regimes: bounded treewidth gives κ=Ω(n), planarity gives κ=Ω(√n).
  3. [Section III, grid family definition] The paper asserts that transmission networks supply such cuts on combinatorial and electromechanical grounds, but no data or references are provided demonstrating that real grids have balanced separators of constant size (or treewidth O(1)) and b̄/bmax=Ω(1). The slow-coherency argument supports existence of weak cuts, not necessarily with s=O(1) and β bounded away from 0. The grid-family definition in Section III assumes a key empirical premise; the main theorem is conditional. This is load-bearing for the abstract's claim that grids 'that split into two large regions meeting at only a few buses, common in transmission networks' preclude advantage.
  4. [Section IV] The abstract claims the obstructions 'persist through AC power flow, optimal power flow, and unit commitment.' Section IV is heuristic: it invokes spectral similarity of the flat-start Jacobian, states that IPM Newton systems are weighted Laplacians, and appeals to NP-hardness, but it does not provide formal statements or proofs at the same level as Sections II–III. If these are intended as rigorous results, the proofs are missing; otherwise the abstract overstates the scope.
minor comments (5)
  1. [Abstract] Typo: 'thisprecludes' should be 'this precludes'.
  2. [Section III] Typo: 'thatdotame' should be 'that tame'.
  3. [Section III] The sentence 'At the separator floor κ=Θ(n) ... HHL pays eΩ(n κ²/ε²)=eΩ(n³/ε²)' uses a specific HHL complexity model that is not defined; please clarify the query-count convention.
  4. [Section II, Proposition 1] The remark 'Letting ℓ=2 recovers the tie line case of Theorem 1' is not immediately obvious; a one-line verification would help.
  5. [General] The statement 'All proofs are formally verified' should specify which results (Theorem 1, Corollary 1, Propositions 1–3) are covered by the Lean 4 source; the GitHub link alone is insufficient in a letter.

Circularity Check

0 steps flagged

No significant circularity: the main lower bounds are derived from graph topology and external query/tomography results; the grid-family assumption is conditional, not circular.

full rationale

The derivation chain is self-contained. Lemma 1 is a Rayleigh–Ritz bound; Theorem 1, Corollary 1, Proposition 1, and Proposition 2 are proved directly from graph-theoretic definitions and Hoeffding's inequality. Proposition 3 combines the resulting κ lower bounds with external black-box query/tomography lower bounds ([1], [9]) and classical solver baselines ([10], [11]). The only internal input is the conditional definition of a 'grid family' (Δ, τ, s = O(1) and b̄/bmax = Ω(1)); the no-advantage conclusion is conditional on that class. Whether real grids satisfy these assumptions is an empirical claim asserted in Section II but not demonstrated from grid data—this is a correctness/empirical-support gap, not circularity. The self-citation [8] supplies the random-susceptance model and an AC Jacobian structural claim, but Proposition 2 reproves the random bound with Hoeffding, and the DC no-advantage result does not depend on [8]. No fitted parameter is renamed as a prediction; the PGLib κ∼N^2 fit from [5] is used only as motivation, not as an input. Therefore no circular step is present.

Axiom & Free-Parameter Ledger

0 free parameters · 11 axioms · 0 invented entities

The central claim rests on standard graph theory and quantum complexity results, plus domain assumptions about grid topology. There are no fitted parameters.

axioms (11)
  • standard math Lipton-Tarjan planar separator theorem
    Used in Corollary 1(ii) to obtain a separator of size O(√n).
  • standard math Treewidth separator lemma (a bag of size ≤ τ+1 leaves components of size ≤ n/2)
    Used in Corollary 1(i) to obtain a balanced separator from bounded treewidth.
  • standard math Hoeffding's inequality for bounded independent random variables
    Used in Proposition 2 to bound the probability that total susceptance is small.
  • domain assumption Quantum query lower bound Ω(κ) for linear system solvers (fact F1)
    Facts from [1] and [2] used in Proposition 3; not proved in this paper.
  • domain assumption Pure-state tomography lower bound Θ(n/ε) state preparations (fact F2)
    From [9]; used to convert QLS to classical output.
  • domain assumption Classical Laplacian solver runtime Õ(m log(1/ε)) (fact F3)
    From [10],[11]; baseline for classical comparison.
  • domain assumption End-to-end advantage criterion D κ^{3/2} ≪ N/d from [5]
    Used in Section III to conclude no readout level D passes.
  • domain assumption Transmission grids have small separators / bounded treewidth / near-planarity
    The key empirical premise for applying the lower bounds to real grids; asserted in Section II.
  • domain assumption Average-to-max susceptance ratio Ω(1) for real grids
    Needed to translate b(E)/b_max into Ω(n); assumed in grid family definition.
  • domain assumption AC Jacobian flat-start spectral structure governed by Laplacian blocks
    Used for the heuristic AC extension in Section IV.
  • standard math Strong NP-hardness of AC-OPF and unit commitment
    Used for the NP⊆BQP argument in Section IV.

pith-pipeline@v1.3.0-alltime-deepseek · 6424 in / 19559 out tokens · 159137 ms · 2026-08-01T12:55:09.986227+00:00 · methodology

0 comments
read the original 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.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

22 extracted references · 1 linked inside Pith

  1. [1]

    Quantum Algorithm for Linear Systems of Equations,

    A. W. Harrow, A. Hassidim, and S. Lloyd, “Quantum Algorithm for Linear Systems of Equations,”Phys. Rev. Lett., vol. 103, no. 15, p. 150502, 2009

    2009

  2. [2]

    Optimal Scaling Quantum Linear-Systems Solver via Discrete Adiabatic Theorem,

    P. C. S. Costaet al., “Optimal Scaling Quantum Linear-Systems Solver via Discrete Adiabatic Theorem,”PRX Quantum, vol. 3, no. 4, p. 040303, 2022

    2022

  3. [3]

    Quantum Power Flow,

    F. Feng, Y. Zhou, and P. Zhang, “Quantum Power Flow,”IEEE Trans. Power Syst., vol. 36, no. 4, pp. 3810–3812, 2021

    2021

  4. [4]

    A. M. Dalzellet al.,Quantum Algorithms: A Survey of Applications and End-to-End Complexities. Cambridge: Cambridge University Press, 2025

    2025

  5. [5]

    Limitations of Fault-Tolerant Quantum Linear System Solvers for Quantum Power Flow,

    P. Pareek, A. Jayakumar, C. Coffrin, and S. Misra, “Limitations of Fault-Tolerant Quantum Linear System Solvers for Quantum Power Flow,”IEEE Trans. Power Syst., vol. 41, no. 2, pp. 811–820, 2026

    2026

  6. [6]

    The Power Grid Library for Bench- marking AC Optimal Power Flow Algorithms

    S. Babaeinejadsarookolaeeet al., “The Power Grid Library for Bench- marking AC Optimal Power Flow Algorithms.” arXiv:1908.02788, 2021

    Pith/arXiv arXiv 1908

  7. [7]

    Exploiting Sparsity in SDP Relaxations of the OPF Problem,

    R. A. Jabr, “Exploiting Sparsity in SDP Relaxations of the OPF Problem,”IEEE Trans. Power Syst., vol. 27, no. 2, pp. 1138–1139, 2012

    2012

  8. [8]

    Admittance Ma- trix Concentration Inequalities for Understanding Uncertain Power Networks

    S. Talkington, C. Khanpour, R. K. Gupta,et al., “Admittance Ma- trix Concentration Inequalities for Understanding Uncertain Power Networks.” arXiv:2510.17798, 2026

    arXiv 2026

  9. [9]

    Quantum Tomography using State-Preparation Unitaries,

    J. van Apeldoorn, A. Cornelissen, A. Gilyén, and G. Nannicini, “Quantum Tomography using State-Preparation Unitaries,” inProc. ACM-SIAM SODA, pp. 1265–1318, 2023

    2023

  10. [10]

    Nearly-Linear Time Algorithms for Graph Partitioning, Graph Sparsification, and Solving Linear Systems,

    D. A. Spielman and S.-H. Teng, “Nearly-Linear Time Algorithms for Graph Partitioning, Graph Sparsification, and Solving Linear Systems,” inProc. ACM STOC, pp. 81–90, 2004

    2004

  11. [11]

    Approximate Gaussian Elimination for Laplacians - Fast, Sparse, and Simple,

    R. Kyng and S. Sachdeva, “Approximate Gaussian Elimination for Laplacians - Fast, Sparse, and Simple,” inProc. IEEE FOCS, pp. 573– 582, 2016

    2016

  12. [12]

    Convex Relaxation for Optimal Power Flow Problem: Mesh Networks,

    R. Madaniet al., “Convex Relaxation for Optimal Power Flow Problem: Mesh Networks,”IEEE Trans. Power Syst., vol. 30, no. 1, pp. 199–211, 2015

    2015

  13. [13]

    J. H. Chow, ed.,Time-Scale Modeling of Dynamic Networks with Applications to Power Systems. Springer, 1982

    1982

  14. [14]

    Cyganet al.,Parameterized Algorithms

    M. Cyganet al.,Parameterized Algorithms. Springer, 2015

    2015

  15. [15]

    A Separator Theorem for Planar Graphs,

    R. J. Lipton and R. E. Tarjan, “A Separator Theorem for Planar Graphs,”SIAM J. Appl. Math., vol. 36, no. 2, pp. 177–189, 1979

    1979

  16. [16]

    Disentangling Hype from Prac- ticality: On Realistically Achieving Quantum Advantage,

    T. Hoefler, T. Häner, and M. Troyer, “Disentangling Hype from Prac- ticality: On Realistically Achieving Quantum Advantage,”Commun. ACM, vol. 66, no. 5, pp. 82–87, 2023

    2023

  17. [17]

    Quantum Interior Point Methods for Semidefinite Optimization,

    B. Augustino, G. Nannicini, T. Terlaky, and L. F. Zuluaga, “Quantum Interior Point Methods for Semidefinite Optimization,”Quantum, vol. 7, p. 1110, 2023

    2023

  18. [18]

    Maximum Flow and Minimum-Cost Flow in Almost- Linear Time,

    L. Chenet al., “Maximum Flow and Minimum-Cost Flow in Almost- Linear Time,” inProc. IEEE FOCS, pp. 612–623, 2022

    2022

  19. [19]

    Strong NP-Hardness of AC Power Flows Feasibility,

    D. Bienstock and A. Verma, “Strong NP-Hardness of AC Power Flows Feasibility,”Oper. Res. Lett., vol. 47, no. 6, pp. 494–501, 2019

    2019

  20. [20]

    On the Complexity of the Unit Commitment Problem,

    P. Bendotti, P. Fouilhoux, and C. Rottner, “On the Complexity of the Unit Commitment Problem,”Ann. Oper. Res., vol. 274, no. 1–2, pp. 119–130, 2019

    2019

  21. [21]

    Strengths and Weaknesses of Quantum Computing,

    C. H. Bennett, E. Bernstein, G. Brassard, and U. Vazirani, “Strengths and Weaknesses of Quantum Computing,”SIAM J. Comput., vol. 26, no. 5, pp. 1510–1523, 1997

    1997

  22. [22]

    Tang,Quantum Machine Learning Without Any Quantum

    E. Tang,Quantum Machine Learning Without Any Quantum. PhD thesis, University of Washington, 2023

    2023