Pith. sign in

REVIEW 4 major objections 6 minor 1 cited by

Landscape-Similarity-Guided Optimization in Divide-and-Conquer QAOA

T0 review · 4 major / 6 minor · reviewed 2026-08-02 · deepseek-v4-flash

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

Pith's one-line read Freezing qubits in a QAOA problem produces exponentially many reduced instances, but their energy landscapes are near-identical; one optimized parameter set can serve them all.

desk verdict A plausible method-level win for divide-and-conquer QAOA, but the paper's central claim—that one representative parameter set suffices for all frozen subproblems—is asserted rather than directly measured. read the letter →

arxiv 2602.21689 v2 pith:PTWMX2BM submitted 2026-02-25 quant-ph

Sokea Sang , Leanghok Hour , Sanghyeon Lee , Aniket Patra , Hee Chul Park , Moon Jip Park , Youngsun Han This is my paper · ORCID
classification quant-ph
keywords QAOAdivide-and-conquerparametertransferenergylandscapesimilarityoverlaporderqubitfreezingNISQIsingmodel
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper tries to establish a universality principle for the Quantum Approximate Optimization Algorithm: when a QAOA problem is split by freezing a few high-degree qubits, the exponentially many reduced subproblems (up to 2^m, one per frozen configuration) have variational energy landscapes that are near-copies of one another. If that holds, a single representative subproblem can be fully optimized and its parameters reused for all the others, converting the training cost of divide-and-conquer QAOA from exponential in m to constant. The paper measures landscape similarity with a spin-glass-style overlap order parameter, finds a sharp similarity transition as graph connectivity is tuned, and still observes aligned basin centers on both sides. On the strength of that, DO-QAOA is shown to cut total quantum shots by 280x to 385x and wall-clock time by 10x to 15x on more than 6,000 circuits while matching or improving the approximation ratio gap of independent retraining. The reason to care: it removes the main classical bottleneck that made divide-and-conquer QAOA impractical on near-term hardware.

What carries the argument

The load-bearing structure is the decomposition of a frozen QAOA instance into an invariant quadratic part (edges inside the active subgraph) and a configuration-dependent linear part (induced local fields from frozen neighbors). The similarity measure is the landscape-overlap order parameter q(s), the mean pairwise cosine similarity of standardized energy surfaces over a (gamma,beta) grid, adapted from replica-overlap ideas in spin-glass physics; it detects the sharp transition between fragmented and self-averaging regimes as the connectivity decay exponent s is tuned. Theorem 1 (Landscape Stability) supplies the theoretical bound: the L-infinity pointwise distance between any two subproble

What would settle it

For a fixed graph in the self-averaging regime, compute the exact optimal parameters (gamma*, beta*) for all 2^m frozen subproblems and measure the spread of these optima and the energy lost by using a single representative's parameters on each subproblem. If that energy gap grows with m or with system size L, or if the optimal parameter spread does not shrink as connectivity increases, the claimed collapse to K=1 is falsified.

Watch

Extended reading notes

Core claim

The paper's central claim is that the QAOA variational landscape of a decimated Ising problem is governed by the quadratic interaction backbone that is invariant across frozen configurations, so the configuration-dependent linear biases act only as bounded perturbations. Concretely, freezing m qubits produces a Hamiltonian split into an invariant quadratic part and a configuration-dependent linear part; Theorem 1 bounds the pointwise difference between any two subproblem energy surfaces by the sum of induced-field differences, independent of circuit depth. Empirically the full-landscape correlation between subproblems stays above 0.999 for m=1 and near 0.8 for m=2,3, while the isolated quadr

Load-bearing premise

The entire speedup rests on the assumption that two energy surfaces that look similar also have their best parameter settings in nearly the same place; the paper shows the surfaces are close pointwise, but it does not directly measure how far their optima shift.

Editorial extensions

If this is right

  • Divide-and-conquer QAOA training cost drops from O(2^m x N_shots x N_iter) to O(K x N_shots x N_iter); on every benchmark the measured K is 1, so the exponential overhead disappears entirely.
  • On more than 6,000 noisy circuits, transferred parameters match or beat independent full optimization in approximation ratio gap, cutting total quantum shots by 280x to 385x and wall-clock time by 10x to 15x relative to the standard divide-and-conquer baseline.
  • The method is most effective on sparse, locally connected graphs (power-law, 3-regular, and structured real-world networks) where the graph diameter exceeds the QAOA light cone; dense globally connected problems still benefit at finite sizes but show smaller gains.
  • The empirical operating rule m less than or equal to 3 gives the best trade-off; freezing additional high-degree nodes beyond three yields diminishing returns and mostly adds bookkeeping overhead.
  • Because the circuit structure is identical to standard freezing, all gains come from removing redundant optimization loops, so DO-QAOA is compatible with existing noise-mitigation and circuit-lowering techniques.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The K=1 collapse is an empirical observation, not a derived theorem: Theorem 1 bounds pointwise surface separation but not the displacement of the optima. A direct measurement of the per-subproblem energy gap of transferred parameters would test whether K=1 persists as m and L grow, or whether K>1 clustering eventually becomes necessary.
  • The sharp transition in q(s) suggests a practical diagnostic: a graph's effective connectivity could be estimated before deciding whether direct transfer is safe, potentially replacing the hand-set bias threshold (0.3) with a physics-derived criterion.
  • The same 'invariant quadratic backbone plus local linear perturbations' argument is not specific to QAOA; any variational ansatz whose cost is dominated by a fixed quadratic term and whose light cone limits perturbation spread could inherit the same transferability, which the paper gestures at but does not demonstrate.
  • For dense graphs in the fragmented phase, the paper's own phase diagram predicts that subproblems will eventually fracture into a small number of distinct landscape families rather than one; the natural extension is to cluster the 2^m instances into K groups and train one representative per cluster, exactly the route the paper outlines for future work.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

4 major / 6 minor

Summary. The paper proposes DO-QAOA, a divide-and-conquer strategy for QAOA in which a subset of high-degree qubits is frozen, generating 2^m reduced subproblems. The authors argue that the variational energy landscapes of these subproblems are highly similar—quantified by a replica-overlap order parameter and by pairwise correlations—so that a single representative subproblem can be optimized and its parameters transferred to all others. This collapses the exponential training cost to O(K), typically K=1. The method includes a bias-aware transfer rule with optional fine-tuning, and is benchmarked on synthetic and real-world graphs under a realistic noise model, reporting large reductions in quantum shot count and runtime while maintaining or improving approximation ratio gap versus the FrozenQubits baseline.

Significance. If the central claim were established, the paper would offer a practically important result: replacing the exponential training overhead of divide-and-conquer QAOA with a constant cost while preserving approximation quality. The authors provide a simple, correct pointwise landscape-stability bound (Appendix B) and a broad benchmark suite of over 6,000 noisy circuits, which is a strength. However, the key inference—that landscape similarity implies near-optimal parameter transfer—is not directly measured. The reported correlations are modest (r≈0.8 for m=2,3 in the meaningful 'With Coeffs' rows), the 'No Coeffs' rows are tautological, and no per-target transfer gap is reported. The paper is therefore best viewed as an interesting empirical proposal whose main efficiency claim is not yet supported by the evidence presented.

major comments (4)
  1. [§II.C, Appendix B, Table II] The load-bearing claim is that one representative parameter set is near-optimal for all subproblems. Theorem 1 (Eq. B2) bounds only the pointwise L∞ distance between energy surfaces |E^{(z')}(θ) - E^{(z)}(θ)|; it does not bound the distance between their optima or the transfer gap E^{(z')}(θ*_rep) - min_θ E^{(z')}(θ). The measured correlations in Table II (With Coeffs) are r≈0.80 for m=2,3 with L∞≈1.04 and 0.77, which do not imply close optima or near-optimal transfer. The paper never reports the per-subproblem ARG or energy of transferred parameters versus fully optimized parameters. This is a required measurement; without it, the K=1 collapse remains an empirical assertion.
  2. [Table II, §IV.A] The 'No Coeffs' rows are tautological: setting the induced linear fields to zero makes every subproblem Hamiltonian exactly equal to H_quad, so the subproblems are identical as operators and r≈1 by construction. These rows cannot serve as empirical support for landscape similarity. The caption's claim that 'even with induced linear coefficients the correlation remains near 1.0' is contradicted by the table's own 'With Coeffs' rows for m=2 and m=3 (r=0.796 and r=0.802). Either the table, the caption, or the verification protocol should be corrected, and the empirical claim should rest on the With Coeffs numbers only.
  3. [§III.B, Appendix D] The Bias-Aware Transfer Rule uses a threshold ΔB=0.3, a 10-epoch fine-tune, and the Shortcut initialization angles (γ≈−π/6, β≈−π/8). These appear to be fitted on the same benchmark set. Since the reported ARG improvements over FrozenQubits could plausibly arise from the Shortcut initialization rather than from landscape-aware transfer, the paper should provide a sensitivity analysis and/or a train/test split, and should specify the initialization used for the FrozenQubits baseline. Without this, the comparison in Table IV is not clean.
  4. [§IV.C, Table IV] The efficiency claims compare DO-QAOA's total shots to FrozenQubits' 2^m independent optimizations. This comparison is valid only if the transferred parameters actually achieve comparable per-subproblem solution quality. Since the paper does not report the distribution of per-subproblem ARGs for transferred parameters, the reader cannot tell whether the method is 'collapsing the landscape classes' or simply ignoring poorly solved subproblems. Please report, for each target subproblem, the ARG obtained with θ*_rep and, if available, the ARG after full target-specific optimization, across all instances.
minor comments (6)
  1. [Abstract] The notation '2 m' and '2 m distinct reduced problems' should be typeset as 2^m throughout.
  2. [Table II caption] The caption is confusing: 'MSE denotes the mean squared error in evaluating the Correlation' is unclear. It should say MSE of the raw energy surfaces and define it explicitly.
  3. [Fig. 2 caption] The sentence 'the landscape is defined over the single-component parameter space (γ1, β1)' is contradictory; the landscape is two-dimensional in (γ,β) for p=1.
  4. [Appendix D] The Shortcut initialization angles are stated without derivation or reference. If they are empirically chosen, say so and provide the evidence for the cluster location.
  5. [Appendix E1] The noise model is described only as 'derived from FakeBrisbane' and compiled with 'a popular quantum software stack'; specify the simulator backend, noise-model version, and compilation settings so the results can be reproduced.
  6. [Section V] The sentence 'In the rare cases where its framework naturally extends to the fragmented phase (s < sc)' is grammatically incomplete; it appears to mean that the framework can be extended to the fragmented phase, but the current wording obscures the intended meaning.

Circularity Check

1 steps flagged · score 4.0 of 10

No-Coefficients 'verification' is definitional; actual With-Coeffs correlations are r≈0.8, so the K=1 collapse is asserted rather than derived.

  1. self definitional [Section IV A, Fig. 5 caption; see also Section II C, Table II (No Coeffs rows) and Eq. (2.3)]
    "Panel (a–c) displays the “Ideal” landscape of the reference sub-problem (where induced fields are artificially removed), representing the renormalization fixed point."

    In the No-Coefficients condition, Eq. (2.3) H^(z) = H_quad^(R) + H_lin^(R,z) is truncated to H_quad^(R) by artificially removing induced fields, so all 2^m subproblem Hamiltonians are identical. Hence r>0.999 for 'No Coeffs' in Table II is true by construction and cannot test whether real linear biases preserve optima. The paper's own 'With Coeffs' rows for m=2,3 show r≈0.796–0.802 with L∞≈0.77–1.04, contradicting the caption's 'correlation remains near 1.0'. Since no per-target transfer gap is reported, the K=1 collapse is an empirical assertion, not a derived consequence; the No-Coeffs evidence for it is circular.

full rationale

The derivation chain contains one genuine construction-level circularity: the 'No Coeffs' rows of Table II and the 'Ideal' panels of Fig. 5 verify landscape similarity after artificially setting the induced linear fields to zero. Under Eq. (2.3), doing so makes every frozen subproblem Hamiltonian equal to the same H_quad^(R), so r≈1 is definitional rather than empirical evidence that real frozen configurations share a landscape. The paper itself reports With-Coeffs correlations of only r≈0.80 for m=2 and m=3, and it never measures the per-target optimization gap E^(z')(θ*_rep) − min_θ E^(z')(θ) for transferred parameters; thus the central K=1 collapse is an unverified empirical assertion. I do not score this higher because the end-to-end ARG and shot-count comparisons against FrozenQubits are independent external benchmarks, Theorem 1 is a self-contained deterministic bound, and there is no load-bearing self-citation chain. Additional risks such as the 0.3 bias threshold and Shortcut initialization being fitted on the same benchmark regime are overfitting concerns, not circularity per se.

Assumptions & free parameters 4 free parameters · 4 assumptions · 2 invented entities

The central claim rests on the fitted transfer threshold, fitted initialization angles, an unscaled phase-transition estimate, and the unproven transferability of pointwise landscape closeness to optimum proximity. The quadratic-backbone dominance is partially supported but is asserted beyond the tested m ≤ 3.

free parameters (4)
  • Bias distortion threshold ΔB = 0.3
    Set experimentally to decide direct transfer vs warm-start; no derivation.
  • Shortcut initialization angles = γ ≈ -π/6, β ≈ -π/8
    Chosen from empirical observation of the optimal parameter cluster for the Ising formulation; tuned to the benchmark class.
  • Fine-tuning epochs = 10
    Arbitrary constant for warm-start fine-tuning in distorted cases.
  • Critical connectivity s_c = ≈ 0.6
    Estimated from crossing of q(s) curves for L = 50–400; no rigorous finite-size scaling or error bars.
assumptions (4)
  • domain assumption The long-range percolation model p(r) = 1 − exp(−r^{−s}) captures the connectivity structure relevant to landscape similarity on real graphs.
    Used to generate the phase diagram; assumes power-law distance decay proxies for diverse real-world topologies.
  • ad hoc to paper A small L∞ distance / high correlation between two energy landscapes implies that their optima are close enough for parameter transfer.
    This is the transferability step; not proven by Theorem 1, which bounds pointwise differences only.
  • domain assumption The quadratic backbone H_quad dominates the landscape so that induced linear biases are minor perturbations.
    Central hypothesis; supported partially by r ≈ 0.8 for m = 2, 3, but asserted for m > 3.
  • domain assumption FakeBrisbane noise model faithfully represents NISQ hardware.
    All benchmarks use this simulated backend; real-device behavior may differ.
invented entities (2)
  • Effective landscape classes (K)
    purpose: Conceptual grouping of 2^m sub-problems claimed to be in K = O(1) similarity classes, motivating single-representative training.
    K is never measured or clustered; K = 1 is asserted for all benchmarks, and K > 1 is left to future work.
  • Landscape similarity phase (self-averaging vs fragmented)
    purpose: Phenomenological phase separation in connectivity parameter s used to explain when transfer works.
    The transition is inferred from q(s) curves without a theoretical order-parameter derivation or independent probe.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Landscape-Similarity-Guided Optimization in Divide-and-Conquer QAOA." pith.science (2026). https://pith.science/paper/PTWMX2BM

@misc{pith2026260221689,
  author       = {Pith},
  title        = {Pith review of: Landscape-Similarity-Guided Optimization in Divide-and-Conquer QAOA},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PTWMX2BM}},
  note         = {Machine review of arXiv:2602.21689}
}
abstract

Across diverse synthetic and real-world interaction graphs, the variational landscapes of reduced Quantum Approximate Optimization Algorithm (QAOA) instances obtained via variable freezing exhibit a robust universality. Leveraging this structure, we introduce Doubly Optimized QAOA (DO-QAOA), which lowers runtime and quantum measurement overhead while maintaining a competitive approximation ratio gap (ARG). Adapting the replica-overlap framework of spin-glass physics, we define a landscape-overlap order parameter $q$ to quantify geometric correlations between energy landscapes, revealing a sharp landscape-similarity transition as graph connectivity is tuned. Notwithstanding this transition, the dominant convex features of nearly all conditioned sub-instances remain aligned across both phases. Exploiting this persistence, DO-QAOA collapses the nominal $2^m$ reduced instances generated by freezing $m$ qubits into $K = O(1)$ effective landscape classes, eliminating the exponential proliferation in $m$. By leveraging landscape structure, DO-QAOA provides a scalable route to hybrid quantum-classical optimization under realistic hardware constraints, with potential applicability across variational quantum algorithms.

Figures

Figures reproduced from arXiv: 2602.21689 by the authors.

Figure 1
Figure 1. Landscape similarity phase transition. Order [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. (a) Fragmented Phase (s < sc) vs. (d) Self-Averaging Phase (s > sc). (b–c) Energy Landscape of Fragmented Phase (s < sc): Long-Range Connections Dominate (Minima are instance-dependent). The vertical axis represents the expectation value E(γ, β) of the cost Hamiltonian. Note that for the depth p = 1 ansatz used here, the landscape is defined over the single-component parameter space (γ1, β1). Local perturbations spr… view at source ↗
Figure 3
Figure 3. Divide-and-conquer approach and energy landscapes. The energy landscapes of [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figures from the paper (9 more)
Figure 4
Figure 4. Figure 4: Overview of the DO-QAOA framework. The process begins with partitioning the Input Graph, selecting a [PITH_FULL_IMAGE:figures/full_fig_p006_4.png]
Figure 5
Figure 5. Figure 5: Reference and distorted QAOA energy landscapes with 1-layer. Panels (a–c) show the ideal (reference) [PITH_FULL_IMAGE:figures/full_fig_p008_5.png]
Figure 6
Figure 6. Figure 6: Scaling analysis on Power-Law graphs using [PITH_FULL_IMAGE:figures/full_fig_p008_6.png]
Figure 7
Figure 7. Figure 7: Average end-to-end performance metrics across all benchmarks. (a) Average Number of [PITH_FULL_IMAGE:figures/full_fig_p009_7.png]
Figure 8
Figure 8. Figure 8: Overview of the Variational Quantum Algorithm. (a) The hybrid classical-quantum feedback loop. (b) [PITH_FULL_IMAGE:figures/full_fig_p012_8.png]
Figure 9
Figure 9. Figure 9: Workflow of the divide-and-conquer approach for QAOA optimization. (a) High-degree nodes (hotspots, [PITH_FULL_IMAGE:figures/full_fig_p013_9.png]
Figure 10
Figure 10. Figure 10: Study on QAOA Depth (p). (a) The CNOT count and (b) Circuit depth scales linearly with p, significantly increasing the error rate. (c) The results confirm that for current NISQ devices, lower depth (p = 1) provides a superior trade-off between noise resilience and opt…
Figure 11
Figure 11. Figure 11: Impact of initialization strategies on optimization convergence across varying problem configurations [PITH_FULL_IMAGE:figures/full_fig_p015_11.png]
Figure 12
Figure 12. Figure 12: ARG analysis on Regular (3-regular and SK) and Real-world Graph Datasets (AIDS, Linux, and IMDb). [PITH_FULL_IMAGE:figures/full_fig_p017_12.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

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

    quant-ph 2026-07 conditional novelty 6.0 of 10

    Adaptive min-vertex-cut qubit freezing plus bias folding makes DC-QAOA partition every graph (to n=10k) while matching quality on separable instances and beating QAOA2 at equal coverage.

Reference graph

Works this paper leans on

83 extracted references · 2 canonical work pages · cited by 1 Pith paper

  1. [1]

    The objective is typically encoded in a cost HamiltonianH C, which is diagonal in the computational basis

    Variational Quantum Algorithms and QAOA The Quantum Approximate Optimization Algorithm (QAOA) is designed to find approximate solutions to combinatorial optimization problems defined on a graph G(V, E). The objective is typically encoded in a cost HamiltonianH C, which is diagonal in the computational basis. In its most general form, the problem is repres...

  2. [2]

    As shown in Fig

    Noise and Hardware Efficiency In the NISQ era, the depth of quantum circuits is strictly limited by coherence times and gate error rates. As shown in Fig. 8(c), Hardware Efficient An- sätze (HEA) [1] attempt to mitigate this by utilizing na- tive gate sets and minimizing SWAP operations [18–20]. However, standard QAOA circuits often require exten- sive co...

  3. [3]

    hotspot” nodes with high degree centrality (Fig. 9(a)). By “freezing

    The Divide-and-Conquer Strategy To address both connectivity and depth constraints (See A2), theFrozenQubitsapproach [3] employs a divide-and-conquer strategy based on graph partitioning. LetS⊂Vbe a set ofm“hotspot” nodes with high degree centrality (Fig. 9(a)). By “freezing” these nodes into classical statesz k ∈ {+1,−1}for allk∈S, we re- move them from ...

  4. [4]

    Parisi, Infinite number of order parameters for spin- glasses, Physical Review Letters43, 1754 (1979)

    G. Parisi, Infinite number of order parameters for spin- glasses, Physical Review Letters43, 1754 (1979)

    1979

  5. [5]

    Hamiltonian Decomposition Let the original problem Hamiltonian beH. Freezing a subset of qubitsSinto configurationz∈ {±1}|S| yields a reducedHamiltonianH (z) actingontheremainingqubits R: H (z) =H (R) quad +H (R,z) lin +C (z),(B1) 14 1 2 3 Circuit Layers (p) 20 40 60 80CNOT Count (a) 1 2 3 Circuit Layers (p) 40 60 80Circuit Depth (b) 1 2 3 Circuit Layers ...

  6. [6]

    The Landscape Stability Theorem We define theVariational LandscapeE (z)(γ, β) = ⟨ψ(γ, β)|H(z)|ψ(γ, β)⟩. Theorem 1 (Landscape Stability)For any two sub- problems with frozen configurationszandz ′, the point- wise distance between their shifted energy landscapes is bounded by the coupling strength between the frozen and active partitions: L∞ = E(z′)(γ, β)−E...

  7. [7]

    The bound simplifies to: Deviation≤2 X i∈N(k) |Jki|,(B3) whereN(k)are the neighbors of qubitk

    Implications for Optimization Consider the case where a single “hotspot” qubitkis toggled (zk → −zk). The bound simplifies to: Deviation≤2 X i∈N(k) |Jki|,(B3) whereN(k)are the neighbors of qubitk. This implies:

  8. [8]

    Depth Independence: The bound relies solely on the spectral norm of the Hamiltonian difference, rendering it independent of the QAOA depthp

Show all 83 references
  1. [9]

    This justifies theO(1)transfer of optimal parameters(γ ∗, β∗)

    Topology Dependence: For graphs with weak cou- plings (smallJ) or sparse connectivity (small |N(k)|), the landscapes are effectively parallel sheets. This justifies theO(1)transfer of optimal parameters(γ ∗, β∗). Appendix C: Impact of Circuit Depth in NISQ Regime To empiricall...

  2. [10]

    The experiments were conducted usinganoisemodelderivedfromtheFakeBrisbaneback- end to simulate realistic NISQ conditions [55]

    Experimental Setup We evaluated the performance of the QAOA ansatz on a set of random regular graphs with varying circuit depthsp∈ {1,2,3}. The experiments were conducted usinganoisemodelderivedfromtheFakeBrisbaneback- end to simulate realistic NISQ conditions [55]

  3. [11]

    Existing methods treat these as2m unrelated optimization problems, requiring2 m independent train- ing loops

    1). Existing methods treat these as2m unrelated optimization problems, requiring2 m independent train- ing loops. As depicted in Fig. 9, even a small cut of m= 10results in 1024 separate training sessions, creat- ing the exponential barrier we aim to break. Appendix B: Theoret...

  4. [12]

    Shortcut

    Results and Analysis As illustrated in Figure 10, increasing the number of layerspresults in a linear increase in both CNOT count and total circuit depth. Resource Scaling: Forp= 1, the circuit remains com- pact with manageable two-qubit gate overhead. How- ever, atp= 3, the C...

  5. [13]

    noise floor

    Conclusion on Depth Selection The study confirms that finding the lowest energy state becomes increasingly difficult at greater depths because the “noise floor” rises faster than the theoretical overlap improves. Consequently, our DO-QAOA methodology and the associated theoret...

  6. [14]

    Instead, the increased gate count and circuitdepthintroduceadditionalnoisechannelsthatcan degrade solution quality and hinder convergence

    do not yield significant improvements in the final ARG compared top= 1. Instead, the increased gate count and circuitdepthintroduceadditionalnoisechannelsthatcan degrade solution quality and hinder convergence. Thus, maintaining a shallow depth (p= 1) strikes a critical bal- a...

  7. [15]

    Experimental Setup Benchmarks.We evaluated our method on over 6,000 circuits across a diverse set of graph benchmarks to assess robustness on synthetic and real-world prob- lem instances. Synthetic benchmarks include power- law graphs generated using the Barabási-Albert pref- ...

  8. [16]

    Per-Dataset Benchmark Results a. DO-QAOA on Regular Graphs We study DO-QAOA on 3-regular graphs, and fully connected graphs (or SK model) provide a complemen- tary benchmark characterized by uniform degree distri- butions and reduced structural asymmetry [38–40]. As shown in T...

  9. [17]

    Kandala, A

    A. Kandala, A. Mezzacapo, K. Temme, M. Takita, M. Brink, J. M. Chow, and J. M. Gambetta, Hardware- efficient variational quantum eigensolver for small moleculesandquantummagnets,nature549,242(2017)

    2017

  10. [18]

    M. Wang, B. Fang, A. Li, and P. J. Nair, Red-qaoa: Effi- cient variational optimization through circuit reduction, inProceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 2, ASPLOS ’24 (Association...

    2024

  11. [19]

    Ayanzadeh, N

    R. Ayanzadeh, N. Alavisamani, P. Das, and M. Qureshi, Frozenqubits: Boosting fidelity of qaoa by skipping hotspot nodes, inProceedings of the 28th ACM Interna- tional Conference on Architectural Support for Program- ming Languages and Operating Systems, Volume 2, AS- PLOS 2023...

    2023

  12. [20]

    Kirkpatrick, C

    S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, Optimiza- tion by simulated annealing, Science220, 671 (1983)

    1983

  13. [21]

    P. W. Anderson,Basic notions of condensed matter physics(CRC press, 2018)

    2018

  14. [22]

    Bengio, Identifying and attacking the saddle 20 point problem in high-dimensional non-convex optimiza- tion, Advances in neural information processing systems 27(2014)

    Y.N.Dauphin, R.Pascanu, C.Gulcehre, K.Cho, S.Gan- guli, and Y. Bengio, Identifying and attacking the saddle 20 point problem in high-dimensional non-convex optimiza- tion, Advances in neural information processing systems 27(2014)

    2014

  15. [23]

    J. R. McClean, S. Boixo, V. N. Smelyanskiy, R. Bab- bush, and H. Neven, Barren plateaus in quantum neural network training landscapes, Nature communications9, 4812 (2018)

    2018

  16. [24]

    Larocca, N

    M. Larocca, N. Ju, D. García-Martín, P. J. Coles, and M. Cerezo, Theory of overparametrization in quantum neural networks, Nature Computational Science3, 542 (2023)

    2023

  17. [25]

    P. C. Lotshaw, T. S. Humble, R. Herrman, J. Ostrowski, and G. Siopsis, Empirical performance bounds for quan- tum approximate optimization, Quantum Information Processing20, 403 (2021)

    2021

  18. [26]

    Galda, X

    A. Galda, X. Liu, D. Lykov, Y. Alexeev, and I. Safro, Transferability of optimal qaoa parameters between ran- dom graphs, in2021 IEEE International Conference on Quantum Computing and Engineering (QCE)(2021) pp. 171–180

    2021

  19. [27]

    Shaydulin, P

    R. Shaydulin, P. C. Lotshaw, J. Larson, J. Ostrowski, and T. S. Humble, Parameter transfer for quantum ap- proximateoptimizationofweightedmaxcut,ACMTrans- actions on Quantum Computing4, 10.1145/3584706 (2023)

    2023 doi

  20. [28]

    Wurtz and D

    J. Wurtz and D. Lykov, Fixed-angle conjectures for the quantum approximate optimization algorithm on regular maxcut graphs, Phys. Rev. A104, 052419 (2021)

    2021

  21. [29]

    Farhi, J

    E. Farhi, J. Goldstone, and S. Gutmann, A quan- tum approximate optimization algorithm (2014), arXiv:1411.4028 [quant-ph]

    2014 arXiv

  22. [30]

    Z. Wang, S. Hadfield, Z. Jiang, and E. G. Rieffel, Quan- tum approximate optimization algorithm for maxcut: A fermionic view, Phys. Rev. A97, 022304 (2018)

    2018

  23. [31]

    B. A. Cordier, N. P. D. Sawaya, G. G. Guerreschi, and S. K. McWeeney, Biology and medicine in the landscape of quantum advantages, Journal of The Royal Society Interface19, 20220541 (2022)

    2022

  24. [32]

    Preskill, Quantum Computing in the NISQ era and beyond, Quantum2, 79 (2018)

    J. Preskill, Quantum Computing in the NISQ era and beyond, Quantum2, 79 (2018)

    2018

  25. [33]

    G. Li, Y. Ding, and Y. Xie, Tackling the qubit mapping problem for nisq-era quantum devices, inProceedings of the Twenty-Fourth International Conference on Architec- tural Support for Programming Languages and Operating Systems, ASPLOS ’19 (Association for Computing Ma- chiner...

    2019

  26. [34]

    J. Liu, P. Li, and H. Zhou, Not all swaps have the same cost: A case for optimization-aware qubit rout- ing, in2022 IEEE International Symposium on High- Performance Computer Architecture (HPCA)(2022) pp. 709–725

    2022

  27. [35]

    S. Niu, A. Suau, G. Staffelbach, and A. Todri-Sanial, A hardware-aware heuristic for the qubit mapping problem in the nisq era, IEEE Transactions on Quantum Engi- neering1, 1 (2020)

    2020

  28. [36]

    Mézard, G

    M. Mézard, G. Parisi, and M. A. Virasoro,Spin glass the- ory and beyond: An Introduction to the Replica Method and Its Applications, Vol. 9 (World Scientific Publishing Company, 1987)

    1987

  29. [37]

    Carmona and Y

    P. Carmona and Y. Hu, Universality in sherring- ton–kirkpatrick’s spin glass model, Annales de l’Institut Henri Poincare (B) Probability and Statistics42, 215 (2006)

    2006

  30. [38]

    F. G. Brandao, M. Broughton, E. Farhi, S. Gutmann, and H. Neven, For fixed control parameters the quantum approximate optimization algorithm’s objective function value concentrates for typical instances, arXiv preprint arXiv:1812.04170 (2018)

    2018 arXiv

  31. [39]

    F. A. Venturelli, S. Das, and F. Caruso, Investigating layer-selective transfer learning of quantum approximate optimization algorithm parameters for the max-cut prob- lem, Phys. Rev. A112, 042428 (2025)

    2025

  32. [40]

    Bravyi, M

    S. Bravyi, M. B. Hastings, and F. Verstraete, Lieb- robinson bounds and the generation of correlations and topological quantum order, Phys. Rev. Lett.97, 050401 (2006)

    2006

  33. [41]

    Farhi, D

    E. Farhi, D. Gamarnik, and S. Gutmann, The quan- tum approximate optimization algorithm needs to see the whole graph: A typical case, arXiv preprint arXiv:2004.09002 (2020)

    2004 arXiv

  34. [42]

    E. H. Lieb and D. W. Robinson, The finite group velocity of quantum spin systems, Communications in mathemat- ical physics28, 251 (1972)

    1972

  35. [43]

    D. J. Watts and S. H. Strogatz, Collective dynamics of ‘small-world’networks, nature393, 440 (1998)

    1998

  36. [44]

    M. T. Agler, J. Ruhe, S. Kroll, C. Morhenn, S.-T. Kim, D. Weigel, and E. M. Kemen, Microbial hub taxa link host and abiotic factors to plant microbiome variation, PLoS biology14, e1002352 (2016)

    2016

  37. [45]

    Clauset, E

    A. Clauset, E. Tucker, and M. Sainz, The colorado index of complex networks, Retrieved July20, 22 (2016)

    2016

  38. [46]

    K.-I. Goh, E. Oh, H. Jeong, B. Kahng, and D. Kim, Classification of scale-free networks, Proceedings of the National Academy of Sciences99, 12583 (2002)

    2002

  39. [47]

    House, J

    T. House, J. M. Read, L. Danon, and M. J. Keeling, Testing the hypothesis of preferential attachment in so- cial network formation, EPJ Data Science4, 1 (2015)

    2015

  40. [48]

    Mislove, M

    A. Mislove, M. Marcon, K. P. Gummadi, P. Druschel, and B. Bhattacharjee, Measurement and analysis of on- line social networks, inProceedings of the 7th ACM SIG- COMM Conference on Internet Measurement, IMC ’07 (Association for Computing Machinery, New York, NY, USA, 2007) p. 29–42

    2007

  41. [49]

    Pastor-Satorras, C

    R. Pastor-Satorras, C. Castellano, P. Van Mieghem, and A. Vespignani, Epidemic processes in complex networks, Rev. Mod. Phys.87, 925 (2015)

    2015

  42. [50]

    Meghanathan, Complex network analysis of the con- tiguous united states graph., Comput

    N. Meghanathan, Complex network analysis of the con- tiguous united states graph., Comput. Inf. Sci.10, 54 (2017)

    2017

  43. [51]

    Gamermann, J

    D. Gamermann, J. Triana-Dopico, and R. Jaime, A comprehensive statistical study of metabolic and pro- tein–protein interaction network properties, Physica A: Statistical Mechanics and its Applications534, 122204 (2019)

    2019

  44. [52]

    Barabási and R

    A.-L. Barabási and R. Albert, Emergence of scaling in random networks, science286, 509 (1999)

    1999

  45. [53]

    Basso, E

    J. Basso, E. Farhi, K. Marwaha, B. Villalonga, and L. Zhou, The quantum approximate optimization algo- rithm at high depth for maxcut on large-girth regular graphs and the sherrington-kirkpatrick model (Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022) pp. 7:1–7:21

    2022

  46. [54]

    M. P. Harrigan, K. J. Sung, M. Neeley, K. J. Satzinger, F. Arute, K. Arya, J. Atalaya, J. C. Bardin, R. Barends, S. Boixo,et al., Quantum approximate optimization of non-planar graph problems on a planar superconducting processor, Nature Physics17, 332 (2021)

    2021

  47. [55]

    Sherrington and S

    D. Sherrington and S. Kirkpatrick, Solvable model of a 21 spin-glass, Phys. Rev. Lett.35, 1792 (1975)

    1975

  48. [56]

    Riesen and H

    K. Riesen and H. Bunke, Iam graph database repository for graph based pattern recognition and machine learn- ing, inJoint IAPR international workshops on statisti- cal techniques in pattern recognition (SPR) and struc- tural and syntactic pattern recognition (SSPR)(Springer,

  49. [57]

    X. Wang, X. Ding, A. K. Tung, S. Ying, and H. Jin, An efficient graph indexing method, in2012 IEEE 28th International Conference on Data Engineering(2012)pp. 210–221

    2012

  50. [58]

    Yanardag and S

    P. Yanardag and S. Vishwanathan, Deep graph kernels, inProceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’15 (Association for Computing Machinery, New York, NY, USA, 2015) p. 1365–1374

    2015

  51. [59]

    J. Choi, S. Oh, and J. Kim, Quantum approxi- mation for wireless scheduling, Applied Sciences10, 10.3390/app10207116 (2020)

    2020 doi

  52. [60]

    Dalyac, L

    C. Dalyac, L. Henriet, E. Jeandel, W. Lechner, S. Per- drix, M. Porcheron, and M. Veshchezerova, Qualifying quantum approaches for hard industrial optimization problems. a case study in the field of smart-charging of electric vehicles, EPJ Quantum Technology8, 12 (2021)

    2021

  53. [61]

    Kotil, E

    A. Kotil, E. Pelofske, S. Riedmüller, D. J. Egger, S. Ei- denbenz, T. Koch, and S. Woerner, Quantum approx- imate multi-objective optimization, Nature Computa- tional Science 10.1038/s43588-025-00873-y (2025)

    2025 doi

  54. [62]

    L. S. Schulman, Long range percolation in one dimen- sion, Journal of Physics A: Mathematical and General 16, L639 (1983)

    1983

  55. [63]

    The graph diameter is formally defined as the maximum shortest-path distance (geodesic distance) between any pair of nodes in the network:D L ≡max i,j∈V d(i, j), whered(i, j)denotes the minimum number of edges re- quired to connect nodeito nodej

  56. [64]

    Benjamini and N

    I. Benjamini and N. Berger, The diameter of long-range percolation clusters on finite cycles, Random Structures & Algorithms19, 102 (2001)

    2001

  57. [65]

    Coppersmith, D

    D. Coppersmith, D. Gamarnik, and M. Sviridenko, The diameter of a long-range percolation graph, Random Structures & Algorithms21, 1 (2002)

    2002

  58. [66]

    Erdős, A

    P. Erdős, A. Rényi,et al., On the evolution of random graphs, Publications of the (1960)

    1960

  59. [67]

    M.Alam, A.Ash-Saki,andS.Ghosh,Circuitcompilation methodologies for quantum approximate optimization al- gorithm, in2020 53rd Annual IEEE/ACM International Symposium on Microarchitecture (MICRO)(2020) pp. 215–228

    2020

  60. [68]

    P. Das, S. Tannu, and M. Qureshi, Jigsaw: Boosting fidelity of nisq programs via measurement subsetting, inMICRO-54: 54th Annual IEEE/ACM International Symposium on Microarchitecture, MICRO ’21 (Associ- ation for Computing Machinery, New York, NY, USA,

  61. [69]

    Herrman, P

    R. Herrman, P. C. Lotshaw, J. Ostrowski, T. S. Humble, and G. Siopsis, Multi-angle quantum approximate opti- mization algorithm, Scientific Reports12, 6781 (2022)

    2022

  62. [70]

    cloud.ibm.com/docs/en/api/qiskit-ibm-runtime/ fake-provider, accessed: 2025-12-15

    IBM Quantum, Fake provider,https://quantum. cloud.ibm.com/docs/en/api/qiskit-ibm-runtime/ fake-provider, accessed: 2025-12-15

    2025

  63. [71]

    Wurtz and P

    J. Wurtz and P. J. Love, Counterdiabaticity and the quantum approximate optimization algorithm, Quantum 6, 635 (2022)

    2022

  64. [72]

    Shaydulin, K

    R. Shaydulin, K. Marwaha, J. Wurtz, and P. C. Lotshaw, Qaoakit: A toolkit for reproducible study, application, and verification of the qaoa (2021) arXiv:2110.05555

    2021 arXiv

  65. [73]

    Albert, Scale-free networks in cell biology, Journal of cell science118, 4947 (2005)

    R. Albert, Scale-free networks in cell biology, Journal of cell science118, 4947 (2005)

    2005

  66. [74]

    Barabási, R

    A.-L. Barabási, R. Albert, and H. Jeong, Scale-free char- acteristics of random networks: the topology of the world-wide web, Physica A: statistical mechanics and its applications281, 69 (2000)

    2000

  67. [75]

    C. Gray, L. Mitchell, and M. Roughan, Super-blockers and the effect of network structure on information cas- cades, inCompanion Proceedings of the The Web Confer- ence 2018, WWW ’18 (International World Wide Web Conferences Steering Committee, Republic and Canton of Geneva, CH...

    2018

  68. [76]

    Kim, Y.-M

    S.-S. Kim, Y.-M. Kang, and Y.-K. Kimt, Sparsity-aware reachability computation for massive graphs, in2022 IEEE International Conference on Big Data and Smart Computing (BigComp)(2022) pp. 157–160

    2022

  69. [77]

    Wang, Complex web-api network construction based on barabasi-albert model and popularity-similarity op- timization model, Auckland University of Technology (2019)

    H. Wang, Complex web-api network construction based on barabasi-albert model and popularity-similarity op- timization model, Auckland University of Technology (2019)

    2019

  70. [78]

    V. N. Zadorozhnyi and E. B. Yudin, Structural properties of the scale-free barabasi-albert graph, Automation and Remote Control73, 702 (2012)

    2012

  71. [79]

    Zbinden, A

    S. Zbinden, A. Bärtschi, H. Djidjev, and S. Eiden- benz, Embedding algorithms for quantum annealers with chimera and pegasus connection topologies, inInter- national Conference on High Performance Computing (Springer, 2020) pp. 187–206

    2020

  72. [80]

    M. B. Healy, R. Jokar, S. Thomas, V. R. Pascuzzi, K. Barton, T. A. Alexander, R. Elkabetz, B. C. Dono- van, H. Horii, and M. Hillenbrand, Design and archi- tecture of the ibm quantum engine compiler (2024), arXiv:2408.06469 [quant-ph]

    2024 arXiv

  73. [81]

    D. C. McKay, T. Alexander, L. Bello, M. J. Biercuk, L. Bishop, J. Chen, J. M. Chow, A. D. Córcoles, D. Eg- ger, S. Filipp, J. Gomez, M. Hush, A. Javadi-Abhari, D. Moreda, P. Nation, B. Paulovicks, E. Winston, C. J. Wood, J. Wootton, and J. M. Gambetta, Qiskit backend specifica...

    2018 arXiv

  74. [82]

    Qiskit Compiler, Compilation routines,https: //quantum.cloud.ibm.com/docs/en/api/qiskit/ compiler, accessed: 2025-12-15

    2025

  75. [83]

    Karuppasamy, V

    K. Karuppasamy, V. Puram, S. Johnson, and J. P. Thomas, A comprehensive review of quantum circuit op- timization: Current trends and future directions, Quan- tum Reports7, 10.3390/quantum7010002 (2025)

    2025 doi

Pith tools

Reviewed August 2, 2026 · model on record in the stance chip above.