Pith. sign in

REVIEW 2 major objections 5 minor 65 references

A problem-aware greedy SWAP strategy on 2D grids roughly halves QAOA circuit depth for sparse graphs, raising hardware approximation ratios by several percent up to 80 qubits.

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

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

T0 review · grok-4.5

2026-07-14 12:59 UTC pith:B72LWQEB

load-bearing objection Solid systems paper: greedy problem-aware SWAP-layer search on grids cuts sparse QAOA cost-layer depth/CZ count ~2x vs line routing, with matching hardware AR gains up to 80 qubits. the 2 major comments →

arxiv 2607.10274 v1 pith:B72LWQEB submitted 2026-07-11 quant-ph

Efficient Circuit Transpilation of Commuting Gates on 2D Grids

Sabina Dr\u{a}goi , Daniel J. Egger This is my paper
classification quant-ph
keywords QAOAcircuit transpilationSWAP strategies2D grid connectivityMaxCutMaximum Independent Setcommuting gatessparse graphs
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

QAOA cost layers are blocks of commuting two-qubit gates whose interaction graph often does not match a device's limited connectivity, so compilers must insert many SWAP gates. On rectangular grids the usual fixed line-based SWAP network is wasteful when the problem graph is sparse. This paper shows that alternating a greedy search over a small basis of hardware-native SWAP layers with SAT-based remapping of the qubit layout produces substantially shorter routing sequences for those sparse instances. The resulting circuits need about half as many SWAP layers, half the two-qubit depth, and half the CZ gates of the standard line strategy. That reduction is large enough to run QAOA for MaxCut on 3-regular graphs and Max Independent Set on low-density Erdős–Rényi graphs up to 80 qubits on present hardware, lifting measured mean approximation ratios by as much as 6.6 % and 9.3 %, respectively. The same asymptotic scaling argument implies that further hardware improvements will widen the size window in which the grid-aware method remains advantageous.

Core claim

For sparse commuting two-qubit blocks on rectangular 2-D grids, a greedy construction of problem-dependent SWAP-layer sequences drawn from a fixed hardware-native basis, interleaved with SAT remapping of the initial layout, reduces the number of SWAP layers, the two-qubit depth, and the CZ count by roughly a factor of two relative to the standard line SWAP strategy, enabling practical QAOA experiments up to 80 qubits and improving mean approximation ratios by up to 6.6 % (MaxCut) and 9.3 % (MIS).

What carries the argument

The greedy problem-dependent transpilation loop: depth-limited exhaustive search over sequences drawn from a small basis of grid-native SWAP layers (B_grid or its eight-layer extension), followed by outer-loop SAT remapping of the qubit layout, which together produce a shorter routing path that realises exactly the required interactions.

Load-bearing premise

That a small fixed set of hardware-native SWAP layers plus a shallow greedy lookahead is already enough to find near-optimal routing for the sparse graphs under study; if better non-layer or adaptive bases exist, the claimed factor-of-two gain over standard methods shrinks.

What would settle it

Transpile the same family of 3-regular MaxCut and q=0.08 Erdős–Rényi MIS instances with an unrestricted or larger-basis router and check whether the resulting SWAP-layer counts, depths and CZ counts fall well below the greedy figures reported in the paper; if they do, the factor-of-two advantage disappears.

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

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 5 minor

Summary. The manuscript develops a problem-dependent transpilation method for blocks of commuting two-qubit gates (primarily QAOA cost layers) on rectangular 2D grid coupling maps. It introduces a hybrid line-on-grid baseline and a greedy search that builds SWAP-layer sequences from a fixed hardware-native basis (B_grid or its extension) while iteratively refining the initial mapping via SAT. For sparse instances—MaxCut on 3-regular graphs and MIS on Erdős–Rényi graphs with q≈0.08—the method reduces SWAP-layer count, two-qubit depth and CZ count by roughly a factor of two relative to the standard line SWAP strategy, yields an asymptotic O(√n) improvement consistent with routing-diameter arguments, and produces measurable gains in mean approximation ratio (up to 6.62 % for MC and 9.32 % for MIS) on ibm_miami hardware for circuits up to 80 qubits.

Significance. If the reported factor-of-two resource reductions and the associated hardware approximation-ratio gains hold under broader scrutiny, the work supplies a practical, immediately usable compilation improvement for sparse QAOA and related Ising-model circuits on emerging grid-connected superconducting devices. The asymptotic analysis in Appendix C, the multi-baseline numerical comparisons (line, hybrid, fixed grid, SABRE), and the unmitigated hardware runs with fixed or carefully transferred angles constitute reproducible evidence that problem-aware routing can extend the feasible size of noisy QAOA experiments. The explicit disclosure of the restricted SWAP-layer basis and the tunable classical pre-processing cost (k_max, I) further strengthens the contribution by making the trade-offs transparent.

major comments (2)
  1. Sec. III.B and App. A fix k_max=5 and I=5 for all main-text benchmarks. While the hyper-parameter sweep in Fig. A1 shows that these values are reasonable, the absolute optimality claim relative to “standard methods” would be more robust if the authors quantified, for at least one representative n=80 instance, how much further the SWAP-layer count can be reduced by larger k_max or by an unrestricted (non-layer) router. Without that, the factor-of-two advantage is well-supported against the chosen baselines but remains an upper bound on the residual gap to a fully adaptive router.
  2. App. E derives the ~3600-CZ “feasibility” threshold from optimistic error rates (p_CZ~10^{-3}) that are lower than the median of ibm_miami. Fig. 5 then uses this threshold to delineate the region “enabled” by the greedy method. Because the hardware results themselves (Fig. 7) already demonstrate successful execution of circuits well above that optimistic budget, the threshold is not load-bearing for the experimental claims; however, the language in Sec. IVA that equates the threshold with practical reachability should be softened or recalibrated to the actual device error rates used in Sec. IVB.
minor comments (5)
  1. Fig. 4 caption states that Line (SABRE) results are omitted from panels (b) and (e) because they fall outside the plotted range; a brief numerical range in the caption or a log-scale inset would help the reader gauge the magnitude of the SABRE depth penalty.
  2. Eq. (5) uses a logical disjunction of permuted coupling maps; a short clarifying sentence that the resulting matrix is then interpreted as an adjacency matrix for the implementable edges would remove any ambiguity about the Boolean-to-graph conversion.
  3. In Sec. IIA the MIS penalty is fixed at M=2 with a brief justification; a one-sentence reference to the known closed-form threshold for independence constraints would make the choice fully self-contained.
  4. Appendix G describes the angle-transfer procedure for MIS; the explicit formula for λ (Eq. G.2) is useful, but the main text could note that the same transfer is used for all p=2 MIS hardware runs so that readers do not have to hunt for it.
  5. Typographical consistency: “Erdős–Rényi” appears both with and without the diacritic in figure labels; standardise throughout.

Circularity Check

0 steps flagged

Empirical methods paper with no load-bearing circularity; self-citations supply reusable tools (grid SWAP basis, SAT mapping) while factor-of-two reductions and hardware AR gains are measured against independent baselines.

full rationale

The paper proposes a greedy search over a fixed basis of hardware-native SWAP layers (B_grid / B_extended_grid) interleaved with SAT remapping of the initial layout. All central claims (O(√n) scaling for sparse graphs, ~2 imes reduction in SWAP layers / depth / CZ count versus line and fixed-grid strategies, and the resulting hardware approximation-ratio gains of up to 6.6 % / 9.3 %) are obtained by direct numerical and experimental measurement on RR and ER instances (Secs. IV A–B, Figs. 4–7, Apps. C–H). Self-citations to Weidenfeller et al. (2022) and Matsuo et al. (2023) merely furnish the reference S_grid sequence and the SAT-mapping subroutine used as components or baselines; the measured improvements do not reduce to those citations by construction. No parameter is fitted to data and then re-labeled a prediction, no uniqueness theorem is imported to forbid alternatives, and no known empirical pattern is renamed. The restricted search depth (k_max = 5) and basis size are disclosed limitations on absolute optimality, not circularities. Hence the derivation chain is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

5 free parameters · 6 axioms · 2 invented entities

Central claims rest on standard QAOA/Ising encodings, published SWAP-strategy and SAT-mapping machinery, a fixed discrete basis of parallel SWAP layers, and a handful of search hyperparameters. No new physical entities are postulated; the “greedy strategy” is an algorithmic construction, not an invented ontological object. Free parameters are the search controls and the optimistic noise budget used only for feasibility shading, not for the hardware AR numbers.

free parameters (5)
  • k_max (greedy lookahead depth) = 5
    Fixed to 5 for all main benchmarks; controls tree size and solution quality (App. A).
  • I (outer-loop SAT remapping iterations) = 5
    Fixed to 5; each iteration may improve initial mapping via stochastic SAT.
  • k_append (partial-commit depth variant) = k_max (default)
    Optional ≤ k_max; default equals k_max in main experiments; trades rigidity vs. runtime.
  • CZ feasibility budget (~3600 gates) = ~3600 CZ
    Derived from optimistic p_CZ~1e-3, p_meas~1e-2, p_succ,min=1e-2 (App. E); used only to shade “feasible” regions in Fig. 5, not for hardware AR claims.
  • MIS penalty M = 2
    Fixed to 2 by closed-form independence argument (Sec. II.A); standard but still a modeling choice.
axioms (6)
  • domain assumption QAOA cost layers are blocks of mutually commuting two-qubit RZZ (or equivalent) gates whose interaction graph is the problem graph.
    Stated in Sec. I–II; enables reordering and SWAP-strategy compilation.
  • domain assumption Hardware connectivity is a rectangular 2D grid (or a longest line embedded in it) with native parallel SWAP layers drawn from a small basis B.
    Sec. III and Fig. 1; all strategies are defined relative to this coupling map.
  • domain assumption A sequence of layers from B can realize any pairwise interaction (basis-set completeness).
    Definition of basis set in Sec. II.B; required for termination of the greedy search.
  • domain assumption SAT solvers can find feasible initial mappings for a fixed SWAP sequence when one exists (approximate classical solvers).
    Sec. II.B citing Matsuo et al.; used in outer loop of Alg. 1.
  • ad hoc to paper For sparse graphs (|E|=Θ(n) or qn small), circuit depth is dominated by routing diameter rather than interaction packing.
    App. B–C; underpins the claimed O(√n) advantage of grid over line.
  • standard math Standard combinatorial encodings of MaxCut and MIS as Ising/QUBO Hamiltonians (Lucas 2014).
    Sec. II.A.
invented entities (2)
  • Greedy problem-dependent SWAP strategy (S_greedy on B_grid / B_extended_grid) no independent evidence
    purpose: Construct shorter problem-specific SWAP-layer sequences than fixed S_grid or S_line for sparse interaction graphs.
    Algorithmic construction (Alg. 1–2), not a physical entity; independent_evidence false because quality is only demonstrated inside this paper’s benchmarks.
  • Hybrid (S_line, C_grid) strategy no independent evidence
    purpose: Intermediate baseline that keeps line SWAPs but fires RZZ on unused grid edges.
    Simple extension of prior line strategy; again a method, not an ontological postulate.

pith-pipeline@v1.1.0-grok45 · 32803 in / 3604 out tokens · 37058 ms · 2026-07-14T12:59:05.646853+00:00 · methodology

0 comments
read the original abstract

Combinatorial optimization problems are central to many applications but can be challenging to solve. Quantum approaches such as the Quantum Approximate Optimization Algorithm (QAOA) offer new tools with which to tackle such problems. However, QAOA circuits inherit the interaction structure of the target Hamiltonian, often resulting in deep circuits when compiled onto hardware with limited connectivity. Efficient transpilation is therefore critical to their practical performance. In this work, we propose a transpilation scheme for circuits consisting of blocks of commuting two-qubit gates on two-dimensional lattices. Unlike standard approaches based on random initial mappings and fixed routing, our method alternates between constructing problem-dependent SWAP-layer sequences and updating the qubit layout. By adapting the routing to the required interactions, this yields significantly shorter circuits for graphs with few edges. We benchmark our approach on QAOA instances for Maximum Cut (MC) on Random Regular graphs and Maximum Independent Set (MIS) on Erd\H{o}s-R\'enyi graphs. Compared to standard methods, we reduce circuit depth and gate count by about a factor of two, enabling experiments with up to $80$ qubits and improving approximation ratios by up to $6.6\%$ for MC and $9.3\%$ for MIS.

Figures

Figures reproduced from arXiv: 2607.10274 by Daniel J. Egger, Sabina Dr\u{a}goi.

Figure 1
Figure 1. Figure 1: Example of two basis sets of SWAP layers for [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Linear and hybrid strategy on a 4 × 4 rectan￾gular grid coupling map. Both strategies route along the longest line of qubits (red), but the hybrid strategy can additionally apply interactions on the remaining edges of the coupling map (light blue). We now consider the two-dimensional rectangular grid transpilation strategy (Sgrid, Cgrid) of Ref. [23], where the rectangular grid Cgrid is defined by [Cgrid](… view at source ↗
Figure 3
Figure 3. Figure 3: Greedy searches a tree of SWAP layer se￾quences. The edges correspond to SWAP layers and are colored according to the basis Bgrid shown in [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Circuit complexity versus graph size of e −iγHC transpiled to a rectangular grid with different strategies. The linear strategy is the current state-of-the-art and is based on (Sline, Cline grid); the hybrid one is our first contribution and is based on (Sline, Cgrid); the grid strategy uses (Sgrid, Cgrid) [23]; the greedy strategy is our main contribution and uses (S greedy grid , Cgrid); the Line (SABRE)… view at source ↗
Figure 5
Figure 5. Figure 5: Entangling gates scaling of e −iγHC transpiled ton a grid with the linear (a) and greedy (b) SWAP strategies versus the graph size and edge density of the underlying Erdős–Rényi graphs. Each data point is the average of ten instances. The colors and numbers show the number of CZ gates. White and black dashed lines indicate the estimated ∼ 3,600 CZ gates feasibility thresholds for linear and greedy strategi… view at source ↗
Figure 6
Figure 6. Figure 6: Truncation quality, measured by the fraction of [PITH_FULL_IMAGE:figures/full_fig_p006_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Hardware performance analysis of QAOA circuits with [PITH_FULL_IMAGE:figures/full_fig_p007_7.png] view at source ↗

discussion (0)

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

Reference graph

Works this paper leans on

65 extracted references · 8 linked inside Pith

  1. [1]

    required by the linear method, see Fig. 7(g). At this size, we measured an average independent set of sizec linear ≈16. The improvement in the size of the independent set is∆c=δ¯r·c linear ≈1.5nodes. Not- ably, this corresponds to the largest MIS circuit tested, measured by gate-count, and thus the largest absolute gate reduction, see Fig. 7(h). The incre...

  2. [2]

    1, finds the initial mapping for a given SWAP strategySj

    Algorithms The outer loop, Alg. 1, finds the initial mapping for a given SWAP strategySj. For the initial mappingπj−1 0 at iterationj, the inner loop, Alg. 2, constructs the SWAP strategyS j by exploring the tree of reachable qubit con- figurations. Inthestandardgreedymethod, thefullselectedpathis committed before the search resumes from its endpoint, i.e...

  3. [3]

    Computational cost and hyperparameter tuning We now investigate the trade-off between performance and computational cost of thegreedymethod. When kappend =k max, it explores a number of paths in the tree that scales as Tstandard ∼I·N subtrees · |B| ·(|B| −1) k−1.(A.1) Here,Iis the number of outer-loop iterations and Nsubtrees is the number of subtrees exp...

  4. [4]

    General Set-Up For a given placement of decision variables to qubits, called aqubit permutation, only a subset of the target RZZ gates can be executed without SWAPs in what we call aninteraction block. Since a qubit cannot simultan- eously participate in multiple gates, the two-qubit gate depth of such a blockDint is upper bounded by the max- imum degree ...

  5. [5]

    We consider a rectangular coupling map withnr rows andn c =⌈n/n r⌉ ≥n r columns, leaving only a few unused qubits

    Aspect-ratio impact We study the aspect-ratio dependence of a circuit’s depth and gate-count for sparse graphs with|E|= Θ(n) edges. We consider a rectangular coupling map withnr rows andn c =⌈n/n r⌉ ≥n r columns, leaving only a few unused qubits. The average node degree of the rectangu- lar lattice with nodesVand connection edgesE, ¯d= 2|E| |V| = 2 nr(nc ...

  6. [6]

    (B.1) dominates the circuit depth

    Sparse regime We call the target graph sparse when the routing con- tribution in Eq. (B.1) dominates the circuit depth. This occurs when the number of required qubit permutations, Nperm, remains small compared with the routing depth which depends onD(C), see Fig. C1(a).d-regular graphs Gwithd≪D(C)satisfyN perm ≪D(C). Indeed, RZZ gates can be applied in pa...

  7. [7]

    (B.1) dominates the circuit depth

    Dense regime We call the target graph dense when the number of qubit permutationsN perm in Eq. (B.1) dominates the circuit depth. This happens when the2|E|/(n ¯d)lower bound toNperm of Sec. B2 scales asO(n)and is no longer small compared to the couplong map diameterD(C), see Fig. C1. Ref. [23] lower-bounds the two-qubit gate depth of the line-based and gr...

  8. [8]

    Bridging the two regimes The sparse and dense regimes correspond to different circuit complexity scalings resulting from different dom- inant contributions, see Fig. C1. In the sparse regime, Nperm is small and the routing distanceD(C)dominates the circuit depth. In the dense regime,Nperm scales as O(n). The crossover between these limits occurs once the ...

    2000

  9. [9]

    P.TothandD.Vigo,Vehicle routing: Problems, methods, and applications(SIAM, 2014)

    2014

  10. [10]

    Pinedo,Scheduling: Theory, algorithms, and systems (Springer, 2016)

    M. Pinedo,Scheduling: Theory, algorithms, and systems (Springer, 2016)

    2016

  11. [11]

    Katoh and T

    N. Katoh and T. Ibaraki, Resource allocation problems, inHandbook of combinatorial optimization, edited by D.- Z. Du and P. M. Pardalos (Springer, Boston, MA, 1998) pp. 905–1006

    1998

  12. [12]

    M. R. Garey and D. S. Johnson,Computers and intract- ability: A guide to the theory of NP–completeness(W. H. Freeman, 1979)

    1979

  13. [13]

    C. H. Papadimitriou and K. Steiglitz,Combinatorial op- timization: Algorithms and complexity(Dover, 1998)

    1998

  14. [14]

    G. L. Nemhauser and L. A. Wolsey,Integer and combin- atorial optimization(Wiley, 1988)

    1988

  15. [15]

    D. P. Williamson and D. B. Shmoys,The design of approximation algorithms(Cambridge University Press, 2011)

    2011

  16. [16]

    V. V. Vazirani,Approximation algorithms, Vol. 1 (Springer, 2001)

    2001

  17. [17]

    Feige, A threshold of ln n for approximating set cover, Journal of the ACM45, 634 (1998)

    U. Feige, A threshold of ln n for approximating set cover, Journal of the ACM45, 634 (1998)

    1998

  18. [18]

    Montanaro, Quantum algorithms: an overview, npj Quantum Information2, 1 (2016)

    A. Montanaro, Quantum algorithms: an overview, npj Quantum Information2, 1 (2016)

    2016

  19. [19]

    Bharti, A

    K. Bharti, A. Cervera-Lierta, T. H. Kyaw, T. Haug, S. Alperin-Lea, A. Anand, M. Degroote, H. Heimonen, J. S. Kottmann, T. Menke,et al., Noisy intermediate- scale quantum algorithms, Reviews of Modern Physics 94, 015004 (2022)

    2022

  20. [20]

    H. Zhao, A. Zlokapa, H. Neven, R. Babbush, J. Preskill, J. R. McClean, and H.-Y. Huang, Exponential quantum advantage in processing massive classical data (2026) arXiv:2604.07639

    Pith/arXiv arXiv 2026

  21. [21]

    Hangleiter, Has quantum advantage been achieved? (2026) arXiv:2603.09901

    D. Hangleiter, Has quantum advantage been achieved? (2026) arXiv:2603.09901

    arXiv 2026

  22. [22]

    Lucas, Ising formulations of many NP problems, Fron- tiers in Physics2, 5 (2014)

    A. Lucas, Ising formulations of many NP problems, Fron- tiers in Physics2, 5 (2014)

    2014

  23. [23]

    Farhi, J

    E. Farhi, J. Goldstone, and S. Gutmann, A quantum approximate optimization algorithm (2014) arXiv:1411.4028

    Pith/arXiv arXiv 2014

  24. [24]

    Rajak, S

    A. Rajak, S. Suzuki, A. Dutta, and B. K. Chakrabarti, Quantum annealing: an overview, Philosophical Trans- actions of the Royal Society A: Mathematical, Physical and Engineering Sciences381, 20210417 (2023)

    2023

  25. [25]

    A. B. Finnila, M. A. Gomez, C. Sebenik, C. Stenson, and J. D. Doll, Quantum annealing: A new method for minimizing multidimensional functions, Chemical Phys- ics Letters219, 343–348 (1994)

    1994

  26. [26]

    Drăgoi, A

    S. Drăgoi, A. Baiardi, and D. J. Egger, Approximate quadratization of high-order Hamiltonians for combin- atorial quantum optimization, Physical Review Research 8, 023159 (2026)

    2026

  27. [27]

    Z. Wang, J. Mandell, Y. Xu, and J. Shi, A depth– independent linear chain ansatz for large–scale quantum approximate optimization (2025) arXiv:2509.17296

    arXiv 2025

  28. [28]

    H. Zou, M. Treinish, K. Hartman, A. Ivrii, and J. Lish- 19 man, LightSABRE: A lightweight and enhanced SABRE algorithm (2024) arXiv:2409.08368

    Pith/arXiv arXiv 2024

  29. [29]

    G. Li, Y. Ding, and Y. Xie, Tackling the qubit mapping problemforNISQ–eraquantumdevices,inProceedings of the Twenty-Fourth International Conference on Architec- tural Support for Programming Languages and Operating Systems, ASPLOS ’19 (Association for Computing Ma- chinery, New York, NY, USA, 2019) p. 1001–1014

    2019

  30. [30]

    Maslov, S

    D. Maslov, S. M. Falconer, and M. Mosca, Quantum cir- cuit placement, IEEE Transactions on Computer-Aided DesignofIntegratedCircuitsandSystems27,752(2008)

    2008

  31. [31]

    Weidenfeller, L

    J. Weidenfeller, L. C. Valor, J. Gacon, C. Tornow, L. Bello, S. Woerner, and D. J. Egger, Scaling of the quantum approximate optimization algorithm on su- perconducting qubit based hardware, Quantum6, 870 (2022)

    2022

  32. [32]

    Matsuo, S

    A. Matsuo, S. Yamashita, and D. J. Egger, A SAT ap- proach to the initial mapping problem in SWAP gate insertion for commuting gates, IEICE Transactions on Fundamentals of Electronics, Communications and Com- puter Sciences106, 1424 (2023)

    2023

  33. [33]

    Rigetti and M

    C. Rigetti and M. Devoret, Fully microwave-tunable uni- versal gates in superconducting qubits with linear coup- lings and fixed transition frequencies, Physical Review B 81, 134507 (2010)

    2010

  34. [34]

    Chamberland, G

    C. Chamberland, G. Zhu, T. J. Yoder, J. B. Hertzberg, and A. W. Cross, Topological and subsystem codes on low-degree graphs with flag qubits, Physical Review X 10, 011022 (2020)

    2020

  35. [35]

    Bravyi, A

    S. Bravyi, A. W. Cross, J. M. Gambetta, D. Maslov, P. Rall, and T. J. Yoder, High–threshold and low– overhead fault–tolerant quantum memory, Nature627, 778 (2024)

    2024

  36. [36]

    T. Koch, D. E. Bernal Neira, Y. Chen, G. Cortiana, D. J. Egger, R. Heese, N. N. Hegade, A. G. Cada- vid, R. Huang, T. Itoko,et al., Quantum optimization benchmarking library – The intractable decathlon (2025) arXiv:2504.03832

    Pith/arXiv arXiv 2025

  37. [37]

    Zhou, S.-T

    L. Zhou, S.-T. Wang, S. Choi, H. Pichler, and M. D. Lukin, Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near- term devices, Physical Review X10, 021067 (2020)

    2020

  38. [38]

    Brandhofer, D

    S. Brandhofer, D. Braun, V. Dehn, G. Hellstern, M. Hüls, Y. Ji, I. Polian, A. S. Bhatia, and T. Wellens, Bench- marking the performance of portfolio optimization with QAOA, Quantum Information Processing22, 25 (2022)

    2022

  39. [39]

    Willsch, D

    M. Willsch, D. Willsch, F. Jin, H. De Raedt, and K. Michielsen, Benchmarking the quantum approxim- ate optimization algorithm, Quantum Information Pro- cessing19, 1–24 (2020)

    2020

  40. [40]

    Alessandroni, S

    E. Alessandroni, S. Ramos-Calderer, I. Roth, E. Traversi, and L. Aolita, Alleviating the quantum big-M problem, npj Quantum Information11, 125 (2025)

    2025

  41. [41]

    Ebadi, A

    S. Ebadi, A. Keesling, M. Cain, T. T. Wang, H. Lev- ine, D. Bluvstein, G. Semeghini, A. Omran, J.-G. Liu, R. Samajdar,et al., Quantum optimization of maximum independent set using Rydberg atom arrays, Science376, 1209 (2022)

    2022

  42. [42]

    Cococcioni and L

    M. Cococcioni and L. Fiaschi, The big-M method with the numerical infinite M, Optimization Letters15, 2455 (2021)

    2021

  43. [43]

    F. G. Fuchs, K. O. Lye, H. M. Nilsen, A. J. Stasik, and G. Sartor, Constraint preserving mixers for the quantum approximate optimization algorithm, Algorithms15, 202 (2022)

    2022

  44. [44]

    Z. He, R. Shaydulin, S. Chakrabarti, D. Herman, C. Li, Y. Sun, and M. Pistoia, Alignment between initial state and mixer improves QAOA performance for constrained optimization, npj Quantum Information9, 121 (2023)

    2023

  45. [45]

    html, accessed: 2026-03-10

    PySAT developers, SAT solvers’ API (pysat.solvers), https://pysathq.github.io/docs/html/api/solvers. html, accessed: 2026-03-10

    2026

  46. [46]

    Javadi-Abhari, M

    A. Javadi-Abhari, M. Treinish, K. Krsulich, C. J. Wood, J. Lishman, J. Gacon, S. Martiel, P. D. Nation, L. S. Bishop, A. W. Cross,et al., Quantum computing with Qiskit (2024) arXiv:2405.08810

    Pith/arXiv arXiv 2024

  47. [47]

    Wurtz and D

    J. Wurtz and D. Lykov, Fixed–angle conjectures for the quantum approximate optimization algorithm on regular MaxCut graphs, Physical Review A104, 052419 (2021)

    2021

  48. [48]

    M. X. Goemans and D. P. Williamson, Improved approx- imation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM42, 1115–1145 (1995)

    1995

  49. [49]

    Basso, E

    J. Basso, E. Farhi, K. Marwaha, B. Villalonga, and L. Zhou, The quantum approximate optimization al- gorithm at high depth for MaxCut on large-girth regular graphs and the Sherrington–Kirkpatrick model, in17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022), Leibniz International Proceedings in Informatics (LIPIc...

    Pith/arXiv arXiv 2022

  50. [50]

    Here, large girth refers to graphs whose shortest cycles are long, implyingthatlocalneighborhoodsuptoafixedradiusare cycle-free

    Lower bounds for the performance of QAOA on regular graphs with degreedhold for large-girth graphs only, which is a reasonable assumption for smalldvalues. Here, large girth refers to graphs whose shortest cycles are long, implyingthatlocalneighborhoodsuptoafixedradiusare cycle-free. In the infinite-size limit, such graphs become locally tree-like, meanin...

  51. [51]

    Viola, E

    L. Viola, E. Knill, and S. Lloyd, Dynamical decoupling of open quantum systems, Physical Review Letters82, 2417 (1999)

    1999

  52. [52]

    M. J. Biercuk, H. Uys, A. P. VanDevender, N. Shiga, W. M. Itano, and J. J. Bollinger, Optimized dynamical decoupling in a model quantum memory, Nature458, 996 (2009)

    2009

  53. [53]

    Niu and A

    S. Niu and A. Todri-Sanial, Effects of dynamical decoup- ling and pulse-level optimizations on ibm quantum com- puters, IEEE Transactions on Quantum Engineering3, 1 (2022)

    2022

  54. [54]

    Pokharel, N

    B. Pokharel, N. Anand, B. Fortman, and D. A. Lidar, Demonstration of fidelity improvement using dynamical decoupling with superconducting qubits, Physical Re- view Letters121, 220502 (2018)

    2018

  55. [55]

    In particular, when two adja- centverticesarebothselected, oneofthemisremovedac- cording to a fixed ordering of the vertices, ensuring a de- terministic and reproducible outcome

    Typical MIS bitstring reconstruction methods resolve conflicts by iteratively removing vertices involved in vi- olating edges until independence is restored, yielding a computationally efficient, though not necessarily op- timal, approximate value. In particular, when two adja- centverticesarebothselected, oneofthemisremovedac- cording to a fixed ordering...

  56. [56]

    [28]) for which Gurobi 11.0.0 did not prove optimality within the7200s time limit

    Maximum Independent Set instances from the QOBLIB benchmark (Table 7 of Ref. [28]) for which Gurobi 11.0.0 did not prove optimality within the7200s time limit. graph_filename number_nodes edge_density brock400-1400 0.2516 R_500_005_1500 0.0501 C500-9500 0.0995 R_1000_005_11000 0.0494 hamming10-41024 0.1711 frb53-24-11272 0.1166 p_hat1500-31500 0.2464 frb5...

  57. [57]

    T. J. Yoder, E. Schoute, P. Rall, E. Pritchett, J. M. Gam- betta, A. W. Cross, M. Carroll, and M. E. Beverland, Tour de gross: A modular quantum computer based on bivariate bicycle codes (2025) arXiv:2506.03094

    Pith/arXiv arXiv 2025

  58. [58]

    J. N. Eberhardt and V. Steffan, Logical operators and fold-transversal gates of bivariate bicycle codes, IEEE Transactions on Information Theory71, 1140 (2024)

    2024

  59. [59]

    J.N.Eberhardt, F.R.F.Pereira,andV.Steffan,Pruning qLDPC codes: Towards bivariate bicycle codes with open boundary conditions (2024) arXiv:2412.04181

    Pith/arXiv arXiv 2024

  60. [60]

    Dembo, A

    A. Dembo, A. Montanari, and S. Sen, Extremal cuts of sparse random graphs, Annals of Probability45, 1190 (2017)

    2017

  61. [61]

    Montanari, Optimization of the Sherrington– KirkpatrickHamiltonian,SIAMJournalonOptimization 26, 1088 (2016)

    A. Montanari, Optimization of the Sherrington– KirkpatrickHamiltonian,SIAMJournalonOptimization 26, 1088 (2016)

    2016

  62. [62]

    S. H. Sureshbabu, D. Herman, R. Shaydulin, J. Basso, S. Chakrabarti, Y. Sun, and M. Pistoia, Parameter set- ting in quantum approximate optimization of weighted problems, Quantum8, 1231 (2024)

    2024

  63. [63]

    D. J. Egger, J. Mareček, and S. Woerner, Warm-starting quantum optimization, Quantum5, 479 (2021)

    2021

  64. [64]

    Qiskit Community, QAOA training pipeline, https://github.com/qiskit-community/qaoa_ training_pipeline(2025), GitHub repository

    2025

  65. [65]

    Rossmannek, J

    M. Rossmannek, J. R. Garrison, and C. Johnson, Qiskit addon utils (2024)

    2024