Adaptive Qubit Freezing Enables Robust Graph Partitioning for Divide-and-Conquer QAOA
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 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.Where the paper says it
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 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. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
The Mechanism of Qubit Freezing
Qubit freezing is a hybrid optimization technique originally developed to boost circuit fidelity by classically fixing the states of 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 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
5hotspot
(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. 4Where the paper says it
Where the paper says it
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 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 (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. 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.Where the paper says it
Where the paper says it
Where the paper says it
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 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. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
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 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. 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.Where the paper says it
Where the paper says it
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 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. 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 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.Where the paper says it
Where the paper says it
Where the paper says it
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 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.Where the paper says it
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 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.Where the paper says it
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 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.Where the paper says it
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 82 as the freeze budget grows and removes vertices from the quantum workload. Method Bf CoverageF Runtime [s] ρ [%] NRL
DC-QAOA (Phase 1) — 4.Where the paper says it
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 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.Where the paper says it
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 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). 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.Where the paper says it
Where the paper says it
Appendix F. p. 1 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.Where the paper says it
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 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.Where the paper says it
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 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).Where the paper says it
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 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. 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.Where the paper says it
Where the paper says it
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 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. 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.Where the paper says it
Where the paper says it
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 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
.Where the paper says it
[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 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. 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. 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. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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 1
Random d-regular pairing model, d ∈ {3, . , 10} uniform, δ=d d (w. , 10} uniform, δ=d d (w. ) Phase 1 iff d≤5; else Phase 2 Sec. 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. , 10} uniform, δ=d d (w. ) Phase 1 iff d≤5; else Phase 2 Sec.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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 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.Where the paper says it
**Table 5 Coverage (% of instances decomposed within the freeze budget for exact MVC. p. 9 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.Where the paper says it
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
-
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.
-
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. -
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 demonstratingimproved robustness arising from reduced entangling-gate requirements.
-
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.
-
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
- A Quantum Approximate Optimization Algorithm
- QAOA with fewer qubits: a coupling framework to solve larger-scale Max-Cut problem
- ParaQAOA: Efficient Parallel Divide-and-Conquer QAOA for Large-Scale Max-Cut Problems Beyond 10,000 Vertices
- Landscape-Similarity-Guided Optimization in Divide-and-Conquer QAOA
Related papers
- Fulqrum: a generalized framework for quantum subspace diagonalization
- Flux-Activated Resonant Control of a Bosonic Quantum Memory
- Machine learning the effects of many quantum measurements
- Barriers to dequantization of near-term molecular electronic structure methods
- BRIDGE: Lazy-Move Compilation for Dual-Species Neutral-Atom Quantum Computers
- Non-Hermiticity of an anomalous superradiant phase