Adaptive Qubit Freezing Enables Robust Graph Partitioning for Divide-and-Conquer QAOA

arXiv:2607.08138 · quant-ph · Submitted 2026-07-09 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Quantum Radio. Generated commentary on the latest quantum physics and condensed matter papers.

Kai: We're looking at the paper: "Adaptive Qubit Freezing Enables Robust Graph Partitioning for Divide-and-Conquer QAOA".

Mira: Here's the gist of the paper. Divide-and-conquer variants of the Quantum Approximate Optimization Algorithm (QAOA) provide a promising route for executing combinatorial optimization problems beyond the qubit capacity of near-term quantum devices Frozen Large Graph Partitioning (FrozenLGP), an adaptive decomposition framework that transforms partitionability from an assumption into an enforceable property.

Kai: The Problem and the Proposed Solution Existing divide-and-conquer approaches fail on dense or highly-connected graphs where small vertex separators do not exist, necessitating the introduction of FrozenLGP, which identifies obstructing vertices through a minimum-vertex-cut computation based on max-flow and classically freezes their spin assignments.

Mira: This framework makes partitionability a property the pipeline can enforce rather than an assumption it must inherit.

Kai: When standard partitioning fails, FrozenLGP identifies the minimum set of obstructing vertices through a minimum-vertex-cut computation based on max-flow and classically freezes their spin assignments.

Title and authors: Mira: The paper's title, "Adaptive Qubit Freezing Enables Robust Graph Partitioning for Divide-and-Conquer QAOA," really tells you the central mechanism they are introducing here, which is this adaptive freezing technique for partitioning problems.

Kai: And looking at the authors—Sokea Sang, Leanghok Hour, Dongmin Kim, and Youngsun Han from Pukyong National University—it shows a strong focus on applying these quantum algorithms to real hardware constraints.

Lev: From my side, the implication is that this isn't just a theoretical exercise; it’s about making sure the algorithm actually runs without crashing when you move from sparse graphs to much denser ones that are common in real-world optimization tasks.

Mira: It’s about robustness because standard methods just fail on dense graphs where those small vertex separators don't exist, and FrozenLGP makes partitionability a property the pipeline can enforce instead of an assumption.

Kai: So, what does this mean for us right now? It suggests that we can actually use QAOA for these larger problems that we thought were simply out of reach due to qubit capacity >

Lev: It means we have a new way to manage the overhead, and they show that this method achieves one hundred percent decomposition coverage across graph sizes up to ten thousand vertices in different topology families, which is much better than the standard divide-and-conquer baseline at only four point six percent on high-connectivity instances.

Mira: It’s a significant jump in performance metrics because it proves this framework works where the simpler approaches simply don't.

The paper's summary: Kai: So, to summarize the paper's main contribution, FrozenLGP is an adaptive decomposition framework that handles dense or highly connected graphs by identifying obstructing vertices using a minimum vertex cut computation based on max flow.

Mira: And when they find those nodes, they classically freeze their spin assignments, which simplifies the interaction terms into linear bias terms for the neighboring active qubits. This preserves the energetic contributions of those interactions rigorously >

Lev: From an error correction standpoint, that folding of interactions is key because it means we aren't just throwing away information; we’re modifying it into a manageable classical field that affects the quantum part in a controlled way.

Kai: The paper details a three-phase pipeline: standard LGP first, then adaptive qubit freezing if necessary, and finally connectivity-preserving partitioning if Phase two doesn't succeed >

Mira: If phase one finds a valid bipartition, they just return it immediately with no extra overhead, which is good because it keeps the system efficient when things are simple.

Lev: The real cost comes when phase two activates, where they compute the minimum vertex cut F using max flow and only freeze those nodes if the size of that cut is less than or equal to mmax >

Kai: If that budget isn't met, then control passes to phase three, which unconditionally produces two roughly equal subgraphs by splitting the sorted vertex list at its midpoint >

Mira: The key result they highlight is that this entire process achieves exact solution quality preservation on instances already solvable by conventional divide-and-conquer QAOA while extending applicability to previously unsupported graphs >

The paper's improvements: Lev: One major improvement is the topological robustness; they show that FrozenLGP achieves one hundred percent decomposition coverage across graph sizes up to ten thousand vertices and multiple topology families, which beats the standard divide-and-conquer baseline at only four point six percent on high-connectivity instances >

Kai: And they define a sharp threshold for performance, which is related to the topological budget Bf equals kappa minus k minus one >

Mira: The paper also shows that this freeze budget Bf equals kappa minus k minus one is both necessary and sufficient for achieving the best coverage, meaning over-provisioning your budget doesn't actually give you any better quality or coverage on these instances >

Lev: It’s also a major win for circuit fidelity because by stripping out edges incident on frozen vertices, FrozenLGP reduces the number of required two-qubit entangling gates >

Kai: And they provide some very concrete numbers on the quantum resource footprint; at most k equals six qubits, twenty-two plus or minus eight C X gates and a depth around twenty-seven for every n >

Mira: The paper also shows that FrozenLGP is noise flat under NISQ noise models, with approximation ratio shifts of less than zero point zero zero five across three different noise conditions >

Lev: That's telling because it confirms that the gap in coverage you see, which is twenty four instances in the benchmark, actually comes from the partitioning step itself rather than circuit noise >

Conclusion: Kai: So, to wrap up on this paper, FrozenLGP establishes itself as a topology-robust front end for distributed QAOA on near-term quantum hardware by making partitionability an enforceable property rather than just an assumption >

Mira: It confirms that the freeze budget Bf equals kappa minus k minus one is both necessary and sufficient for coverage, and it shows that this approach is more efficient than generic circuit-cutting frameworks when you need to make many cuts on dense graphs >

Lev: From my view, the overhead of the quantum sub-circuit is at most two m max, which is a modest constant that only pays off when phase one fails, and their analysis shows it's exponentially smaller than something like CutQC for any non trivial k >

Kai: And overall, this paper gives us a solid path forward for running divide-and-conquer QAOA on hardware by handling the dense graphs we currently can't manage >

Mira: It’s an important piece of work because it shows how to adapt the algorithm to real hardware limitations without sacrificing solution quality on hard instances >

Lev: We saw that FrozenLGP achieves a significant reduction in two-qubit entangling gates compared to a monolithic circuit and incurs correspondingly lower gate and decoherence error >

Sokea Sang, Leanghok Hour, Dongmin Kim, Youngsun Han

Department of AI Convergence, Pukyong National University

quant-ph

Submitted: 2026-07-09

Updated: 2026-11-09

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 92/100

The gist: Divide-and-conquer variants of the Quantum Approximate Optimization Algorithm (QAOA) provide a promising route for executing combinatorial optimization problems beyond the qubit capacity of near-term…

Key concepts

FrozenLGP
An adaptive framework that transforms partitionability into a property. It uses max-flow to find obstructing vertices in dense graphs and classically freezes their spin assignments. This ensures the pipeline can enforce a valid split even when standard methods fail.
Qubit Freezing
A hybrid optimization technique that fixes the states of highly connected 'hotspot' nodes by simplifying their interaction terms into linear bias terms. This is done because fixing these nodes strips away deep entangling sequences, improving circuit fidelity on noisy quantum hardware.
Minimum Vertex Cut
A graph-theoretic computation performed using max-flow to find the smallest set of vertices whose removal disconnects the graph. FrozenLGP uses this computation to identify the minimum set of obstructing vertices that must be frozen to allow a successful partition.
Freeze Budget (Bf)
The critical threshold, calculated as $\kappa - (k - 1)$, which determines when FrozenLGP is sufficient for decomposition. If the number of obstructing vertices is within this budget, freezing occurs; otherwise, the pipeline proceeds to a simpler split.

Terminology

Summary

Divide-and-conquer variants of the Quantum Approximate Optimization Algorithm (QAOA) provide a promising route for executing combinatorial optimization problems beyond the qubit capacity of near-term quantum devices Frozen Large Graph Partitioning (FrozenLGP), an adaptive decomposition framework that transforms partitionability from an assumption into an enforceable property. p. 0

Where the paper says it

IOP Publishing Journal vv (yyyy) aaaaaa Author et al Journal Name PAPER Crossmark RECEIVED dd Month yyyy REVISED dd Month yyyy Adaptive Qubit Freezing Enables Robust Graph Partitioning for Divide-and-Conquer QAOA Sokea Sang1 , Leanghok Hour1 , Dongmin Kim1 and Youngsun Han1,∗ 1Department of AI Convergence, Pukyong National University, Busan 48513, Republic of Korea E-mail: youngsun@pknu. kr Keywords: Quantum Approximate Optimization Algorithm (QAOA), Divide-and-Conquer Quantum Computing, Graph Partitioning, Qubit Freezing, MaxCut, NISQ Computing Abstract Divide-and-conquer variants of the Quantum Approximate Optimization Algorithm (QAOA) provide a promising route for executing combinatorial optimization problems beyond the qubit capacity of near-term quantum devices.

The Problem and the Proposed Solution

Existing divide-and-conquer approaches fail on dense or highly-connected graphs where small vertex separators do not exist, necessitating the introduction of FrozenLGP, which identifies obstructing vertices through a minimum-vertex-cut computation based on max-flow and classically freezes their spin assignments. This framework makes partitionability a property the pipeline can enforce rather than an assumption it must inherit. p. 1

Where the paper says it

FrozenLGP therefore targets the regime where separator structure is almost present and a few frozen vertices restore it at negligible overhead. Our answer is the Frozen Large Graph Partition (FrozenLGP) algorithm, an adaptive decomposition framework that makes partitionability a property the pipeline can enforce rather than an assumption it must inherit.

When standard partitioning fails, FrozenLGP identifies the minimum set of obstructing vertices through a minimum-vertex-cut computation based on max-flow and classically freezes their spin assignments. p. 0
Where the paper says it

We introduce Frozen Large Graph Partitioning (FrozenLGP), an adaptive decomposition framework that transforms partitionability from an assumption into an enforceable property. When standard partitioning fails, FrozenLGP identifies the minimum set of obstructing vertices through a minimum-vertex-cut computation based on max-flow and classically freezes their spin assignments.

The energetic contributions of the removed interactions are rigorously preserved by folding them into linear bias terms in the Ising Hamiltonian of neighboring active qubits. p. 0
Where the paper says it

When standard partitioning fails, FrozenLGP identifies the minimum set of obstructing vertices through a minimum-vertex-cut computation based on max-flow and classically freezes their spin assignments. The energetic contributions of the removed interactions are rigorously preserved by folding them into linear bias terms in the Ising Hamiltonian of neighboring active qubits.

The Mechanism of Qubit Freezing

Qubit freezing is a hybrid optimization technique originally developed to boost circuit fidelity by classically fixing the states of hotspot (high-degree) nodes, thereby stripping away the deep entangling sequences associated with them. Mathematically, freezing relies on the linearity of the Ising Hamiltonian, where if node u is frozen, its interaction term simplifies into a single-body linear term Jv,usvZuZv (2). p. 4

Where the paper says it

Consequently, the quantum operator Zu collapses into the scalar su. The two-body interaction term simplifies into a single-body linear term: Ju,vZuZv freeze u −−−−−→ (Ju,vsu)Zv (2) This classical value is then folded into the existing linear bias (Ising field) of the neighboring 5

This classical value is then folded into the existing linear bias (Ising field) of the neighboring quantum node v, resulting in an updated effective bias h′v = hv + Ju,vsu (3). p. 4
Where the paper says it

Consequently, the quantum operator Zu collapses into the scalar su. The two-body interaction term simplifies into a single-body linear term: Ju,vZuZv freeze u −−−−−→ (Ju,vsu)Zv (2) This classical value is then folded into the existing linear bias (Ising field) of the neighboring 5

The Three-Phase Pipeline

The FrozenLGP pipeline executes three partition phases in strict priority order: Phase 1 (Standard LGP), Phase 2 (Adaptive Qubit Freezing), and Phase 3 (Connectivity-Preserving Partitioning). If a valid bipartition is identified in Phase 1, FrozenLGP returns that partition unchanged with no additional overhead. p. 6

Where the paper says it

If a valid bipartition is identified, FrozenLGP returns that partition unchanged and the pipeline reduces exactly to standard DC-QAOA with no additional overhead. Phase 2 (Adaptive Qubit Freezing).

Phase 2 activates when every candidate separator of size at most k − 1 leaves G S in a single connected component, computing the minimum vertex cut F via max-flow and freezing it if F ≤ mmax. p. 6
Where the paper says it

Phase 2 (Adaptive Qubit Freezing). Phase 2, our principal innovation, activates only when every candidate separator of size at most k − 1 leaves G \ S in a single connected component.

If no valid partition is obtained within this budget, control passes to Phase 3, which unconditionally produces two roughly equal subgraphs by splitting the sorted vertex list at its midpoint. p. 6
Where the paper says it

3) that unconditionally produces two roughly equal subgraphs by splitting the sorted vertex list at its midpoint and tracking the discarded cross-partition edges for classical post-hoc rescoring. CPP guarantees a valid pair of sub-circuits for any graph with n ≥ 4 and therefore provides a hard 100% coverage floor at the cost of foregoing intra-quantum entanglement on a controlled fraction of edges.

Performance and Robustness Metrics

FrozenLGP achieves 100% decomposition coverage across graph sizes up to 10,000 vertices and multiple topology families, compared with only 4.6% for the standard divide-and-conquer baseline on high-connectivity instances. p. 0

Where the paper says it

Across graph sizes up to 10,000 vertices and multiple topology families, FrozenLGP achieves 100% decomposition coverage, compared with 4. 6% for the standard divide-and-conquer baseline on high-connectivity instances.

The algorithm's performance is characterized by a sharp threshold at the topologically expected budget Bf = κ − (k − 1). End-to-end, validity recovery proved free in solution quality, with approximation ratios statistically indistinguishable from DC-QAOA where both run. p. 0
Where the paper says it

6% for the standard divide-and-conquer baseline on high-connectivity instances. End-to-end MaxCut experiments demonstrate that FrozenLGP preserves approximation quality on instances already solvable by conventional divide-and-conquer QAOA while extending applicability to previously unsupported graphs, and outperforming alternative full-coverage decomposition strategies.

Furthermore, FrozenLGP reduces the number of required two-qubit entangling gates by stripping out edges incident on frozen vertices. p. 2
Where the paper says it

CPP is graceful degradation by design, invoked solely when a quantum-exact decomposition is not possible. NISQ robustness: By reducing the size of graph and removing interactions associated with frozen vertices, FrozenLGP reduces the number of required two-qubit entangling gates, leading to lower exposure to gate and decoherence errors.

Conclusion and Future Directions

FrozenLGP establishes itself as a topology-robust front end for distributed QAOA on near-term quantum hardware. The work suggests that the freeze budget Bf ≈ κ − (k − 1) is both necessary and sufficient, and over-provisioning brings no further coverage. p. 7

Where the paper says it

Second, Phase 2 is strictly subordinate to Phase 1: it is invoked only after every separator of size at most k − 1 has failed standard partitioning, so FrozenLGP never incurs freeze overhead on graphs where the unmodified LGP would have succeeded. Third, the freeze budget mmax caps both the worst-case classical search and the quantum overhead (see Appendix C); we use mmax ∈ {2, 3} (default 3) throughout this paper, which is sufficient to recover the vast majority of dense graph instances in our benchmark.

Future work may exploit landscape similarity across subproblems to reduce the overhead of the frozen-spin assignments. p. 0
Where the paper says it

We introduce Frozen Large Graph Partitioning (FrozenLGP), an adaptive decomposition framework that transforms partitionability from an assumption into an enforceable property. When standard partitioning fails, FrozenLGP identifies the minimum set of obstructing vertices through a minimum-vertex-cut computation based on max-flow and classically freezes their spin assignments.

Appendix A Divide-and-Conquer QAOA and the Large Graph Partitioner

The LGP policy is responsible for splitting any graph that exceeds the qubit budget into two sub-graphs that each fit. A critical implicit assumption of Eq. p. 0

Where the paper says it

However, existing approaches rely on the existence of small vertex separators and fail entirely on dense or highly connected graphs where such decompositions do not exist. We introduce Frozen Large Graph Partitioning (FrozenLGP), an adaptive decomposition framework that transforms partitionability from an assumption into an enforceable property.

(A.1) is that some separator S of size at most k − 1 actually exists. p. 1
Where the paper says it

The mechanism is qubit freezing, applied where it has not been applied before: at the partitioning layer. When no valid node separator exists, FrozenLGP identifies the exactly minimal set of obstructing vertices, computed as a minimum vertex cut via max-flow [17, 18], and classically fixes their states to spins of +1 and −1 so that the residual active 2

When no valid separator can be identified, LGP terminates with a GraphPartitionError and the entire DC-QAOA pipeline aborts without returning any candidate bitstring. p. 1
Where the paper says it

The prerequisite breaks down precisely where problems get hard: on dense or highly connected networks such as dense Erdős–Rényi (ER) graphs [15], Barabási–Albert (BA), and complete graphs (Kn), graphs with high preferential attachment [16], removing a small set of shared nodes rarely severs the graph. When LGP fails, the entire pipeline aborts and returns nothing, not even a suboptimal solution.

Appendix B Graph-Theoretic Foundations of Adaptive Qubit Freezing

The node-split max-flow computation returns a provably minimum vertex cut, not merely a small one. The decision rule is then a single comparison against the freeze budget. p. 8

Where the paper says it

2 candidates tie on cut count, and amplifies candidates that combine strong quantum support with many recovered cut edges without introducing a tunable weight that would otherwise require per-instance calibration between a probability and an integer cut count. An ablation against additive and weighted-normalised combinations ( Appendix I) shows that the final quality is statistically insensitive to this choice on the instances where CPP fires, so the parameter-free multiplicative rule is retained.

Appendix F Analyze Graph Partition Scalability

The decomposition trees produced by FrozenLGP and the baseline are identical instance-by-instance on the easy families, an at-scale empirical confirmation of the strict phase-priority guarantee that FrozenLGP never incurs freezing overhead where standard LGP suffices. The reduction ratio is budget-independent and grows with the connectivity surplus d − (k − 1), from ≈2% at d=7 to ≈9% at d=8, ≈17% at d=9, and ≈25% at d=10. p. 9

Where the paper says it

CoverageF counts instances decomposed by freezing alone (no CPP); FrozenLGP coverage including CPP is 100% throughout. ρ is the graph reduction ratio |Ftotal|/n averaged over successful runs.

Appendix J Quantum Resource Footprint

FrozenLGP’s executed sub-circuits are size-invariant: at most k=6 qubits, 22 ± 8 CX gates and depth ∼27 at every n, a 30× qubit, 83× two-qubit-gate, and 9× depth reduction at n = 180. The price is classical-quantum breadth instead of quantum depth. p. 3

Where the paper says it

This closed hybrid quantum-classical loop continues until the parameters converge, ideally driving the circuit to output a distribution tightly clustered around the optimal MaxCut bitstring. 2 provides a concrete visual representation of this hybrid quantum-classical execution loop for a 3-qubit subgraph at a circuit depth of p = 1.

Appendix H End-to-End Effect of the Freeze Budget

The partition-level analysis identified Bf ≈ κ − (k − 1) as the coverage knee, and larger budgets buy no additional quality and only inflate the quantum workload. The budget also has a pronounced runtime effect below the threshold. p. 9

Where the paper says it

82 as the freeze budget grows and removes vertices from the quantum workload. Method Bf CoverageF Runtime [s] ρ [%] NRL DC-QAOA (Phase 1) — 4.

Appendix I CPP rescoring-rule ablation

The choice of rescoring rule affects only re-ranking, not coverage. The multiplicative default is retained on grounds of parsimony, it is parameter-free, scale-invariant, and introduces no mixing weight λ that would require calibrating a probability against an integer cut count. p. 8

Where the paper says it

2 candidates tie on cut count, and amplifies candidates that combine strong quantum support with many recovered cut edges without introducing a tunable weight that would otherwise require per-instance calibration between a probability and an integer cut count. An ablation against additive and weighted-normalised combinations ( Appendix I) shows that the final quality is statistically insensitive to this choice on the instances where CPP fires, so the parameter-free multiplicative rule is retained.

Appendix G Noise robustness under NISQ noise models

FrozenLGP (Bf=3) is noise-flat: AR shifts are ∆AR ≤ 0.005 across the three noise conditions, confirming that the 24-instance coverage gap originates in the partitioning step rather than in circuit noise. p. 8

Where the paper says it

This subsection studies the four heterogeneous families, chosen to span the connectivity regimes that determine partitioning difficulty relative to the separator budget k − 1 = 5: Barabási–Albert graphs [16] with attachment degree d = 3 (vertex connectivity κ≈3 ≤ k − 1), BA graphs with d = 7 (κ≈7 > k − 1, freezing required), dense Erdős–Rényi graphs [15] with mean degree ⟨d⟩ = 12 (mixed regime), and a two-cluster BA topology joined by two bridge edges (κ = 2, an easy control); the random d-regular family [33] is analysed separately in Sec. Instance sizes cover four scale categories, small (n = 10–100, five seeds), medium (n = 150–500, three seeds), large (n = 600–1000, three seeds), and extreme (n = 2000–10,000, two seeds) for a total of 256 instances and 2,616 full decompositions (every (instance, method) pair across the budget sweep below, including the DC-QAOA baseline).

The freeze-reduced ansatz executes far fewer two-qubit entangling gates than a monolithic circuit and incurs correspondingly lower gate and decoherence error. p. 2
Where the paper says it

CPP is graceful degradation by design, invoked solely when a quantum-exact decomposition is not possible. NISQ robustness: By reducing the size of graph and removing interactions associated with frozen vertices, FrozenLGP reduces the number of required two-qubit entangling gates, leading to lower exposure to gate and decoherence errors.

Appendix F. p. 1

Where the paper says it

4: FrozenLGP recovers the boundary on which DC-QAOA aborts while preserving a higher approximation ratio at every size, the gap widening with n, because separator preservation avoids the cut-edge loss that QAOA2 ’s arbitrary partition incurs at every merge. Second, generic circuit-cutting frameworks such as CutQC [8] also achieve full coverage but incur a classical reconstruction cost of O(4K) in the number of cut K; because dense graphs force K = Θ(n) cuts to reach a k-qubit fragment, this cost is astronomical (Appendix C), whereas FrozenLGP’s overhead is a constant 2 m ≤2 Bf (m is the number of frozen qubits and Bf is the freeze budget that caps the overhead) per partition.

5 Exact and polynomial-time partitioners

The upper-bound driver returns the exact threshold on these instances, and the coverage-versus-budget curves coincided exactly (Table 5). The driver then preserves the same coverage profile out to n = 160. p. 0

Where the paper says it

6% for the standard divide-and-conquer baseline on high-connectivity instances. End-to-end MaxCut experiments demonstrate that FrozenLGP preserves approximation quality on instances already solvable by conventional divide-and-conquer QAOA while extending applicability to previously unsupported graphs, and outperforming alternative full-coverage decomposition strategies.

Appendix D Augmented Sub-Circuit Hamiltonian and Bit-Flip Symmetry

The augmented cost Hamiltonian for the sub-circuit becomes H aug S(sF) = X(u,v)∈ES Ju,vZuZv + X(u∈VS hu(sF)Zu (D.2). This formulation is implemented by constructing an augmented Sparse Pauli Operator containing both the ZuZv and Zu generators, so that the QAOA ansatz H aug S,reps = p) is expressed natively at the circuit level via the Rz(γlhu) rotations on each qubit. p. 3

Where the paper says it

At the circuit level, this is implemented natively using rotation gates. The linear bias terms hi are realized via local Pauli-Z rotations, denoted as Rz(γ1hi).

Appendix E Measurement Distribution Reconstruction of FrozenLGP

FrozenLGP must additionally handle the bits associated with the frozen set F, which are classical constants rather than quantum measurement outcomes. The parent bitstring is assembled in a stable left-to-right node order O = VG1, VG2∖VG1, F, so that frozen bits always occupy the final F positions of the reconstructed string. p. 6

Where the paper says it

5(c)), and selects the assignment whose reconstructed distribution attains the highest classically evaluated cut value before returning the top-t parent bitstrings via the extended MDR step in Appendix E (Fig. Because Phases 1–3 are tried in strict priority order, FrozenLGP incurs no additional cost on instances that standard LGP already solves and only enters the freezing or CPP regimes when validity recovery is strictly required.

This process ensures that frozen vertices are absent from both sub-graphs by construction. p. 7
Where the paper says it

Fourth, the algorithm is recursion-ready: the returned sub-graphs G1 and G2 may themselves exceed the qubit budget, in which case FrozenLGP is invoked recursively with bias contributions propagated through the augmented Hamiltonian introduced in Appendix D. 3 Connectivity-Preserving Partitioning Fallback For graphs in which no separator of size ≤ k − 1 disconnects G even after freezing mmax vertices, both Phase 1 and Phase 2 fail by construction.

Appendix C Computational Overhead and Complexity

FrozenLGP introduces three sources of overhead beyond standard DC-QAOA, all of which are tightly bounded by the freeze budget mmax. The quantum sub-circuit overhead is at most 2 mmax = 8 assignments, a modest constant that is paid only when Phase 1 fails. p. 7

Where the paper says it

Second, Phase 2 is strictly subordinate to Phase 1: it is invoked only after every separator of size at most k − 1 has failed standard partitioning, so FrozenLGP never incurs freeze overhead on graphs where the unmodified LGP would have succeeded. Third, the freeze budget mmax caps both the worst-case classical search and the quantum overhead (see Appendix C); we use mmax ∈ {2, 3} (default 3) throughout this paper, which is sufficient to recover the vast majority of dense graph instances in our benchmark.

FrozenLGP’s overhead is exponentially smaller than CutQC for any non-trivial K, and infinitely more efficient than the DC-QAOA failure mode in terms of solution coverage. p. 1
Where the paper says it

4: FrozenLGP recovers the boundary on which DC-QAOA aborts while preserving a higher approximation ratio at every size, the gap widening with n, because separator preservation avoids the cut-edge loss that QAOA2 ’s arbitrary partition incurs at every merge. Second, generic circuit-cutting frameworks such as CutQC [8] also achieve full coverage but incur a classical reconstruction cost of O(4K) in the number of cut K; because dense graphs force K = Θ(n) cuts to reach a k-qubit fragment, this cost is astronomical (Appendix C), whereas FrozenLGP’s overhead is a constant 2 m ≤2 Bf (m is the number of frozen qubits and Bf is the freeze budget that caps the overhead) per partition.

References

[1] Preskill J 2018 Quantum Computing in the NISQ era and beyond Quantum 2 79 ISSN 2521-327X URL https://doi.org/10.22331/q-2018-08-06-79

[4] Wurtz J and Lykov D 2021 Fixed-angle conjectures for the quantum approximate optimization algorithm on regular maxcut graphs Phys. Rev. A 104(5) 052419 URL https://link. p. 8

Where the paper says it

The first is universality: FrozenLGP should decompose every instance, including the dense families on which the standard LGP fails, at preprocessing cost negligible against the quantum stage it enables. 2 test this claim at partition level, up to n = 104 .

aps.org/doi/10.1103/PhysRevA.104.052419

[8] Cutqc: using small quantum computers for large quantum circuit evaluations Proceedings of the 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems ASPLOS ’21 (New York, NY, USA: Association for Computing Machinery) p 473–486 ISBN 9781450383172 URL https://doi.org/10.1145/3445814.3446758

[2] Farhi E, Goldstone J and Gutmann S 2014 A quantum approximate optimization algorithm arXiv preprint arXiv:1411.4028

[3] Lotshaw P C, Humble T S, Herrman R, Ostrowski J and Siopsis G 2021 Empirical performance bounds for quantum approximate optimization Quantum Information Processing 20 403

[5] Galda A, Liu X, Lykov D, Alexeev Y and Safro I 2021 Transferability of optimal qaoa parameters between random graphs 2021 IEEE International Conference on Quantum Computing and Engineering (QCE) pp 171–180

[6] Wang Z, Hadfield S, Jiang Z and Rieffel E G 2018 Quantum approximate optimization algorithm for maxcut: A fermionic view Phys. Rev. A 97(2) 022304 URL https://link.aps.org/doi/10.1103/PhysRevA.97.022304

[7] Cuomo D, Caleffi M and Cacciapuoti A S 2020 Towards a distributed quantum computing ecosystem IET Quantum Communication 1 3–8

[11] Li J, Alam M and Ghosh S 2023 Large-scale quantum approximate optimization via divide-and-conquer IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 42 1852–1860

[14] Huang P H, Li X R, Chuang C, Tu C H and Hung S H 2026 Paraqaoa: Efficient parallel divide-and-conquer qaoa for large-scale max-cut problems beyond 10,000 vertices arXiv preprint arXiv:2603.26232

[15] Gilbert E N 1959 Random graphs The Annals of Mathematical Statistics 30 1141–1144

[18] Dantzig G and Fulkerson D R 2003 On the max flow min cut theorem of networks Linear inequalities and related systems 38 225–231

[20] Bondy J A, Murty U S R et al 1976 Graph theory with applications vol 290 (Macmillan London)

[19] Dittmann C 2017 Menger’s theorem Archive of Formal Proofs

[32] West D B et al 2001 Introduction to graph theory vol 2 (Prentice hall Upper Saddle River)

[34] Goemans M X and Williamson D P 1995 Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming J. ACM 42 1115–1145

[30] Ayanzadeh R, Alavisamani N, Das P and Qureshi M 2023 Frozenqubits: Boosting fidelity of qaoa by skipping hotspot nodes Proceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 2 ASPLOS 2023 (New York, NY, USA: Association for Computing Machinery) p 311–324 ISBN 9781450399166 URL https://doi.org/10.1145/3575693.3575741

[22] Hadfield S, Wang Z, O’Gorman B, Rieffel E G, Venturelli D and Biswas R 2019 From the quantum approximate optimization algorithm to a quantum alternating operator ansatz Algorithms 12 ISSN 1999-4893 URL https://www.mdpi.com/1999-4893/12/2/34

[23] Nielsen M A and Chuang I L 2010 Quantum computation and quantum information (Cambridge university press)

[24] Peruzzo A, McClean J, Shadbolt P, Yung M H, Zhou X Q, Love P J, Aspuru-Guzik A and O’brien J L 2014 A variational eigenvalue solver on a photonic quantum processor Nature communications 5 4213

[25] Kandala A, Mezzacapo A, Temme K, Takita M, Brink M, Chow J M and Gambetta J M and Gambetta J M 2017 Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets nature 549 242–246

[38] Wille R, Van Meter R and Naveh Y 2019 Ibm’s qiskit tool chain: Working with and developing for real quantum computers 2019 Design, Automation, Test in Europe Conference and Exhibition (DATE) pp 1234–1240

[37] Powell M J 1994 A direct search optimization method that models the objective and constraint functions by linear interpolation Advances in optimization and numerical analysis (Springer) pp 51–67

Table 1 Graph families used in the partition-level scalability evaluation.

Graph family Vertex connectivity κ Expected regime Study page

|:--- |:--- |:--- |:---: |

BA d = 3 Barabási–Albert, m=3 heavy-tailed, δ=3 ≈3 Phase 1 Sec. 4.1 Study page 4. p. 8

Where the paper says it

Sizes per scale category: small n = 10–100 (5 seeds), medium n = 150–500 (3 seeds), large n = 600– 1000 (3 seeds), extreme n= 2000–10,000 (2 seeds). Family Generator Degree structure κ Expected regime Study BA d=3 Barabási–Albert, m=3 heavy-tailed, δ=3 ≈3 Phase 1 Sec.

p. 8
Where the paper says it

Sizes per scale category: small n = 10–100 (5 seeds), medium n = 150–500 (3 seeds), large n = 600– 1000 (3 seeds), extreme n= 2000–10,000 (2 seeds). Family Generator Degree structure κ Expected regime Study BA d=3 Barabási–Albert, m=3 heavy-tailed, δ=3 ≈3 Phase 1 Sec.

p. 8
Where the paper says it

Sizes per scale category: small n = 10–100 (5 seeds), medium n = 150–500 (3 seeds), large n = 600– 1000 (3 seeds), extreme n= 2000–10,000 (2 seeds). Family Generator Degree structure κ Expected regime Study BA d=3 Barabási–Albert, m=3 heavy-tailed, δ=3 ≈3 Phase 1 Sec.

p. 8
Where the paper says it

Sizes per scale category: small n = 10–100 (5 seeds), medium n = 150–500 (3 seeds), large n = 600– 1000 (3 seeds), extreme n= 2000–10,000 (2 seeds). Family Generator Degree structure κ Expected regime Study BA d=3 Barabási–Albert, m=3 heavy-tailed, δ=3 ≈3 Phase 1 Sec.

p. 8
Where the paper says it

Sizes per scale category: small n = 10–100 (5 seeds), medium n = 150–500 (3 seeds), large n = 600– 1000 (3 seeds), extreme n= 2000–10,000 (2 seeds). Family Generator Degree structure κ Expected regime Study BA d=3 Barabási–Albert, m=3 heavy-tailed, δ=3 ≈3 Phase 1 Sec.

1 κ≈3 ≤ k − 1; Phase 1 suffices when κ ≤ k − 1

BA d = 7 Barabási–Albert, m=7 heavy-tailed, δ=7 ≈7 Phase 2 (Bf≥2) Sec. 4.1 Study page 4.1 κ≈7 > k − 1; freezing required

Dense ER G(n, p), p=12/(n−1), connected Poisson, ⟨d⟩=12 varies mixed (Phases 1–3) Sec. 4.1 Study page 4.1 Mixed regime

Two-cluster BA 2×BA(n/2, 2) + 2 bridges heavy-tailed, bridged 2 Phase 1 (control) Sec. 4.1 Study page 4.1 κ = 2; an easy control

Random d-regular pairing model, d ∈ [3,..., 10] uniform, δ=d d (w. p. 8

Where the paper says it

1 Random d-regular pairing model, d ∈ {3, . , 10} uniform, δ=d d (w.

h.p.) Phase 1 iff d≤5; else Phase 2 Sec. p. 8
Where the paper says it

, 10} uniform, δ=d d (w. ) Phase 1 iff d≤5; else Phase 2 Sec.

4.2 Study page 4. p. 8
Where the paper says it

Sizes per scale category: small n = 10–100 (5 seeds), medium n = 150–500 (3 seeds), large n = 600– 1000 (3 seeds), extreme n= 2000–10,000 (2 seeds). Family Generator Degree structure κ Expected regime Study BA d=3 Barabási–Albert, m=3 heavy-tailed, δ=3 ≈3 Phase 1 Sec.

2 Phase 1 iff d≤5; else Phase 2 Sec. p. 8
Where the paper says it

, 10} uniform, δ=d d (w. ) Phase 1 iff d≤5; else Phase 2 Sec.

4.1 Study page 4.1

Table 6 Normalised expectation value EVS =⟨C⟩/Copt of the reconstructed distribution on the 100-instance benchmark (n ∈ ≤20), under each noise condition.

| Method | noiseless | depolarizing | strong thermal |

|:--- |:---: |:---: |:---: |

| Monolithic QAOA 0.797 0.788 0.710

DC-QAOA (solved set) 0.939 0.932 0.890

FrozenLGP (Bf=2) 0.925 0.923 0.881

FrozenLGP (Bf=3) 0.937 0.922 0.885

Figure 16 End-to-end budget sweep on the high-connectivity families (n ≤1000 pooled).

(a) Graph reduction ratio ρ and (b) total frozen nodes saturate at the topology-determined level once Bf ≥ κ − (k − 1). p. 9

Where the paper says it

3 scoped accordingly. We record five groups of preprocessing metrics per run: coverage (fraction of instances successfully decomposed), runtime, the node redundancy level NRL = P i |Vi |/n), and graph reduction (total frozen nodes and the reduction ratio ρ = |Ftotal|/n), and the number of CPP invocations.

**Table 5 Coverage (% of instances decomposed within the freeze budget for exact MVC. p. 9

Where the paper says it

Table 2: Freeze-budget sweep on the high-connectivity families (BA d=7 and dense ER pooled, n ≤ 1000). CoverageF counts instances decomposed by freezing alone (no CPP); FrozenLGP coverage including CPP is 100% throughout.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Adaptive decomposition framework for divide-and-conquer QAOA: FrozenLGP transforms partitionability from an assumption into an enforceable property by identifying obstructing vertices via a minimum vertex cut computed through max-flow and classically freezing their spin assignments.

  2. Topology-robust front end for distributed QAOA: The system can handle dense or highly connected graphs where standard divide-and-conquer approaches fail by absorbing obstructing vertices as bounded linear bias distortion, ensuring FrozenLGP achieves 100% decomposition coverage compared to only 4.6% for the standard baseline on high-connectivity instances.

  3. Enhanced circuit fidelity in NISQ devices: By freezing specific edges out of existence, the system reduces the number of required two-qubit entangling gates, leading to lower exposure to gate and decoherence errors and demonstrating improved robustness arising from reduced entangling-gate requirements.

  4. Exact solution quality preservation: FrozenLGP preserves approximation quality on instances already solvable by conventional divide-and-conquer QAOA while extending applicability to previously unsupported graphs, showing that FrozenLGP recovers the boundary on which DC-QAOA aborts while preserving a higher approximation ratio at every size.

  5. Efficient classical reconstruction overhead: The system incurs a constant overhead of "a constant 2 m <= 2 Bf per partition for freezing, which is more efficient than generic circuit-cutting frameworks that incur an astronomical" classical reconstruction cost when forced to use many cuts on dense graphs.

Abstract

Divide-and-conquer variants of the Quantum Approximate Optimization Algorithm (QAOA) provide a promising route for executing combinatorial optimization problems beyond the qubit capacity of near-term quantum devices. However, existing approaches rely on the existence of small vertex separators and fail entirely on dense or highly connected graphs where such decompositions do not exist. We introduce Frozen Large Graph Partitioning (FrozenLGP), an adaptive decomposition framework that transforms partitionability from an assumption into an enforceable property. When standard partitioning fails, FrozenLGP identifies the minimum set of obstructing vertices through a minimum-vertex-cut computation based on max-flow and classically freezes their spin assignments. The energetic contributions of the removed interactions are rigorously preserved by folding them into linear bias terms in the Ising Hamiltonian of neighboring active qubits. Across graph sizes up to 10,000 vertices and multiple topology families, FrozenLGP achieves 100% decomposition coverage, compared with 4.6% for the standard divide-and-conquer baseline on high-connectivity instances. End-to-end MaxCut experiments demonstrate that FrozenLGP preserves approximation quality on instances already solvable by conventional divide-and-conquer QAOA while extending applicability to previously unsupported graphs, and outperforming alternative full-coverage decomposition strategies. Noise simulations further show improved robustness arising from reduced entangling-gate requirements. These results establish FrozenLGP as a topology-robust front end for distributed QAOA on near-term quantum hardware.

Sources

Related papers