Pith. sign in

REVIEW 5 major objections 6 minor 1 cited by

Adaptive Graph Shrinking for Quantum Optimization of Constrained Combinatorial Problems

T0 review · 5 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read The paper claims that adaptive graph shrinking, guided by SDP correlations and constraint-aware merge penalties, makes constrained combinatorial optimization tractable for near-term quantum hardware by shrinking the QUBO before the…

desk verdict A sensible QUBO preprocessing heuristic whose headline claims about solution quality and repair complexity overreach its own Appendix B data; worth refereeing with required revisions. read the letter →

arxiv 2506.14250 v1 pith:ZXGQE7C5 submitted 2025-06-17 quant-ph

Monit Sharma , Hoong Chuin Lau This is my paper
classification quant-ph
keywords graphshrinkingQUBOMax-CutSDPrelaxationconstraint-awaremergingVQEQAOAconstrainedcombinatorialoptimization
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

Quantum optimization algorithms such as QAOA and VQE are limited on current hardware by qubit counts, circuit depth, and noise, so constrained combinatorial problems often cannot be encoded directly. This paper proposes a hybrid classical–quantum pipeline that first maps a constrained QUBO (quadratic unconstrained binary optimization) instance into a weighted Max-Cut graph, uses an SDP relaxation to identify strongly correlated variables, and iteratively merges them while penalizing merges that would break feasibility. After a quantum solver runs on the shrunken graph, the solution is lifted back to the original variables and repaired by problem-specific greedy heuristics. The paper reports that on multidimensional knapsack, maximum independent set, and quadratic assignment benchmarks, the pipeline yields feasible solutions, cuts the qubit demand, and achieves better or competitive optimality gaps compared with direct quantum solving on hardware-limited instances.

What carries the argument

The carrying object is the constraint-aware shrinking loop. A QUBO instance is first mapped to a weighted Max-Cut graph, and the Max-Cut SDP relaxation supplies a Gram matrix $X$ whose entries estimate spin correlations between variables. Supernodes (groups of original variables that shrink into one unit) are merged by maximizing the score $S(C_i,C_j)=E_{u\in C_i,v\in C_j}[X_{uv}] - \lambda\,\Pi(C_i,C_j)$, where $\Pi$ penalizes merges that would violate the problem's feasibility constraints, and $\lambda$ balances structural exploration against constraint safety. An adaptive spectral criterion—cumulative retained Laplacian eigenvalue energy above a threshold $\alpha$—sets how far the graph shrinks, and the recorded merge history is replayed in reverse to reconstruct the full solution after the quantum solve.

What would settle it

Take a benchmark instance where constraint-derived and objective-derived edge weights are comparable in magnitude, violating the condition in Eq. 25, and compare the adaptive-shrinking reconstructed objective against the known optimum; if solution quality drops systematically on such instances, the merging signal depends on that dominance condition rather than on generic structure preservation.

Watch

Extended reading notes

Core claim

The central claim is that graph shrinking can serve as a standalone preprocessing step for constrained QUBO problems, not just as a circuit-cutting or decomposition aid. The authors argue that once a QUBO is converted to an equivalent weighted Max-Cut graph, the SDP relaxation's correlation structure encodes feasibility information, especially when constraint-derived edge weights dominate objective-derived edge weights; merging the most correlated supernodes therefore preserves the landscape that matters. Solving the reduced QUBO with VQE, then reconstructing and repairing the solution, produces feasible answers on the tested MDKP, MIS, and QAP instances, including cases where direct quantum solvers fail on qubit or memory limits. The paper presents this as a scalable pathway for near-term quantum algorithms, with the explicit caveat that shrinking is heuristic and carries no optimality guarantee.

Load-bearing premise

The load-bearing premise is that correlations from the relaxed Max-Cut graph, under the paper's condition that constraint-related edges are much heavier than objective edges, identify merges that preserve the original constrained problem's optimum closely enough; the paper does not verify that condition on its benchmarks.

Editorial extensions

If this is right

  • Instances that direct quantum solvers cannot encode because of qubit limits or memory errors can be run after shrinking, since the reduced graph is what gets encoded into the quantum circuit.
  • Embedding constraint awareness into the shrinking and the QUBO formulation improves the quality of VQE solutions relative to the non-constraint-aware version, while lowering the repair effort needed afterward.
  • Adaptive shrinking, using the spectral energy criterion, gives a better quality-versus-size trade-off than fixed reductions to two-thirds or one-half of the original instance.
  • The framework is solver-agnostic: any QUBO-oriented quantum algorithm, such as QAOA, VQE, or QRAO, can be plugged into the reduced-problem stage.

Reading between the lines

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

  • Because the pipeline only needs a QUBO formulation and a constraint-violation oracle, the same shrinking-plus-repair recipe should apply to other constrained combinatorial problems, such as vehicle routing or graph coloring, provided the dominance condition of Eq. 25 is checked on each new family.
  • A direct way to test the paper's explanation is to measure how often the constraint-dominance condition actually holds on the benchmark instances; if shrinking still works when it fails, the repair phase rather than the SDP guidance may be doing the heavy lifting.
  • The spectral stopping rule is heuristic; a sharper version would try to bound the reconstructed objective's error in terms of the discarded Laplacian energy, which would turn the empirical claim into a formal one.
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

5 major / 6 minor

Summary. The paper proposes a hybrid classical–quantum pipeline for constrained combinatorial optimization in which a QUBO instance is mapped to a weighted Max-Cut graph, iteratively reduced by merging variables with strong SDP-derived correlations under a constraint-aware penalty, solved by VQE or CPLEX on the reduced instance, and reconstructed with a greedy repair step. The method is applied to three benchmark families (MDKP, MIS, QAP), with adaptive correlation recalculation and a spectral stopping criterion as secondary contributions. The central empirical claims are that the approach improves feasibility, reduces repair complexity, and enhances quantum solution quality on hardware-limited instances.

Significance. The constraint-aware merging idea is reasonable, and the ablation structure (fixed-ratio versus adaptive shrinking; constraint-aware versus non-constraint-aware QUBO formulations) is a genuine strength. The paper also provides the full shrinking algorithm as pseudocode (Algorithm 1) and per-instance circuit resource counts (Appendix D), which aid reproducibility. On the reported evidence, the constraint-aware variant improves VQE quality on a majority of instances (e.g., MDKP hp1 gap from 15.77% to 5.76%, pet3 from 17.06% to 2.49%; MIS 1tc.64 RSQ from 90% to 95%), and adaptive shrinking beats direct full-QUBO VQE on most MDKP and MIS instances. However, the headline claims exceed the evidence: two MDKP instances contradict the quality-preservation claim, no repair-complexity metric is reported anywhere, the VQE runs are single-shot with no error bars, and the final reduced sizes (37–128 variables) remain far above near-term hardware capacity while all results come from a noiseless simulator. The significance of the contribution as stated is therefore not yet established, although the underlying method is defensible and improvable.

major comments (5)
  1. [VIII.D and Appendix B, Tables I–II] The headline claim that adaptive shrinking 'significantly reduces problem size while preserving solution quality' is not supported for two of the twelve MDKP instances. For hp2, direct VQE on the full 67-variable QUBO reaches a 12.34% gap while VQE on the adaptively shrunk 57-variable instance reaches 16.61%; for pb5 the figures are 4.25% on 116 variables versus 12.53% on 95 variables, and the constraint-aware variant in Table VIII also gives 12.53%. These size reductions (15–18%) are representative of the whole table, so final sizes remain 37–128 variables, which undercuts the 'otherwise intractable instances' and 'hardware-limited' framing. Moreover, Figures 3–5 compare only shrunken-instance solvers; the unshrunk VQE baseline essential to the preservation claim appears only in Appendix B. The preservation claim should be restated per instance or confined to the majority of instances where shrinking helps.
  2. [Abstract and Section VI.A.5] The claims of 'reduces repair complexity' (abstract) and 'improves pre-repair feasibility rates' (Section VI.A.5) are asserted without any supporting measurement. All tables (Tables III–X) report only final feasibility, which is True by construction because the repair step is applied to every solution; no table reports the number of repaired variables, repair iterations, pre-repair violations, or the fraction of runs requiring repair. Either a repair-complexity metric must be reported, or these claims should be removed from the abstract and Section VI.A.5.
  3. [Section VIII and Appendices C–D] The experiments are not reproducible as reported. The penalty factor λ is discussed in the sensitivity analysis (Section VIII.C), but the specific λ, spectral threshold α, recalculation interval r, change-detection threshold δ, correlation threshold τ, and QUBO penalty weights P_j used for the main benchmark runs are never stated. The VQE results are single runs with no seeds, shots, or variance, so small differences such as MDKP pet5 (12.66% non-CA versus 14.11% CA) and QAP scr12 (1.51% versus 4.99%) cannot be distinguished from optimizer noise. The ansatz family, circuit depth schedule, and optimizer used for VQE are not specified in the main text. These omissions should be corrected before the comparative claims can be evaluated.
  4. [Section IV.B, Eq. (25)] The condition min constraint edges |w_ij| >> max objective edges |w_ij| is the stated justification for why SDP-derived correlations encode feasibility structure, but the paper never verifies this condition for the MDKP, MIS, or QAP benchmarks, and it is not obvious that it holds for QAP, where the objective contributes quadratic terms F_ik D_jl that can be comparable in magnitude to the penalized constraint terms. Because the entire merging heuristic rests on this assumption, the paper should either verify the condition numerically for the benchmark instances or present an ablation showing that merge decisions are insensitive to it.
  5. [Section V.B.e] The spectral stopping rule is underspecified. The paper orders eigenvalues as λ_1 ≤ ... ≤ λ_n and defines Energy_k = (Σ_{i≤k} λ_i)/(Σ_i λ_i) over the smallest eigenvalues, while simultaneously referring to the 'top k eigenmodes'; it is unclear whether the retained modes are the lowest- or highest-frequency ones, and the reported final sizes (e.g., 50 of 60 for hp1, 95 of 116 for pb5) are not reconciled with any stated α value. Without the α values used and a clarification of the ordering convention, Contribution 3 cannot be reproduced or checked.
minor comments (6)
  1. [References] References [22] ('A. Author and B. Author') and [24] ('John Smith and Jane Doe') appear to be placeholder citations and should be replaced with real references or removed.
  2. [Appendix C, Table X] Table X omits the constraint-aware row for tai12b, so the QAP comparison between constraint-aware and non-constraint-aware shrinking is incomplete.
  3. [Throughout] Typos include 'perofrmance' in Section VIII.D and 'targetted' in Section I; these should be corrected.
  4. [Section VIII.C] The sensitivity analysis reports that λ ∈ [1.0, 2.0] is robust but does not give the value used for the main experiments; the chosen values for λ and α should be stated alongside the results.
  5. [Section VII.B] Section VII.B mentions QAOA and CVaR-VQE as downstream solvers, but Section VIII reports only 'VQE'; the actual solver and objective function used in the experiments should be specified.
  6. [Section VIII.D] The statement that constraint-aware shrinking improves solution quality 'across all benchmarks' is contradicted by QAP scr12 (1.51% non-CA versus 4.99% CA) and tai12a (9.99% versus 10.27%) and by MDKP pet5 (12.66% versus 14.11%); the wording should be softened to 'on most instances.'

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the SDP-guided shrinking pipeline is a heuristic evaluated against external benchmarks, not a derivation that reduces to its inputs.

full rationale

The derivation chain QUBO to weighted Max-Cut (Barahona reduction, Eqs. 21-24) to SDP correlations (Eqs. 27-30) to correlation- and constraint-aware merging (Eq. 26, Sec. VI.A) to a reduced QUBO solved by VQE/CPLEX and then reconstructed/repaired is a heuristic pipeline, but none of its steps defines the target result in terms of itself or fits a parameter to the reported outcome and then calls it a prediction. The only tunable parameters (lambda in Sec. VI.A and alpha in Sec. V.B.e) are selected by sensitivity analysis on sampled instances and reported as empirical choices; the final quality numbers are measured against known optima from external benchmark libraries, not generated by the tuning procedure. The SDP correlations are computed from the problem's own QUBO and penalty structure, which makes the method self-referential in a weak heuristic sense (the merged graph inherits the original objective), but that is not circular derivation: the reduced problem is not equivalent to the original by construction, and solution quality is evaluated on the original problem after reconstruction. The repair step guarantees feasibility by design, and the absence of a repair-complexity metric and the Appendix B optimality-gap contradictions are evidence/correctness concerns rather than circularity. No load-bearing self-citation exists: methodological attribution is to external works [8,9,10]. Hence no circular step is exhibited.

Assumptions & free parameters 6 free parameters · 5 assumptions · 0 invented entities

The central claim rests on several hand-tuned hyperparameters (lambda, alpha, r, delta, tau, penalty weights) and on unproven domain assumptions about SDP-guided merging and greedy repair. No new physical entities are introduced.

free parameters (6)
  • lambda (merge penalty factor) = 1.0 to 2.0 (selected from {0.0, 0.5, 1.0, 1.5, 2.0, 5.0, 10.0})
    Controls strength of constraint-aware penalty in S(Ci,Cj); tuned by sensitivity analysis in Section VIII.C on random MIS/MDKP instances.
  • alpha (spectral energy retention) = 0.85 to 0.95
    Threshold for choosing target reduced size k via Energy_k >= alpha; stated in Section V.B.e as user-defined and found stable in experiments.
  • r (correlation recalculation interval) = not specified
    Number of merge steps before SDP correlations are recomputed; described in Section V.B.d but no value given.
  • delta (change detection threshold) = not specified
    Threshold for triggering recalculation when |E| changes substantially; Section V.B.d, no value specified.
  • tau (merge correlation threshold) = not specified
    Threshold for accepting a merge in Eq. (26) (if |Cij| >= tau); no value is reported.
  • QUBO penalty weights P_j = P_j = lambda * max_i p_i with lambda in [10,100] (MDKP/QAP); P > 1 (MIS)
    Chosen following Lucas [30] to make violations energetically unfavorable; Section III. These are hand-selected per problem class.
assumptions (5)
  • domain assumption SDP correlations from the QUBO-derived Max-Cut graph, with constraint edge weights dominant (Eq. 25), reflect the feasible structure of the original problem.
    Section IV.B asserts this as the basis for constraint-aware merging; no proof or empirical validation of dominance is given.
  • domain assumption Solving the reduced QUBO and replaying recorded merge steps yields a solution close to the original problem's optimum.
    Algorithm 1 relies on this; no approximation guarantee or error bound is provided.
  • domain assumption Greedy repair heuristics restore feasibility with small objective loss.
    Section VI.B; MDKP repair removes items by efficiency ratio, MIS removes higher-degree vertices, QAP uses Hungarian on a proxy cost matrix; no quality loss bound.
  • domain assumption Spectral energy retention via Laplacian eigenvalues preserves solution-relevant structure.
    Section V.B.e; motivated by spectral clustering literature, not proven for QUBO/Max-Cut solution quality.
  • standard math Barahona reduction maps any QUBO to an equivalent weighted Max-Cut instance.
    Section IV.A, standard result from [10].

how reviews work

0 comments
Cite this review

Pith. "Pith review of Adaptive Graph Shrinking for Quantum Optimization of Constrained Combinatorial Problems." pith.science (2026). https://pith.science/paper/ZXGQE7C5

@misc{pith2026250614250,
  author       = {Pith},
  title        = {Pith review of: Adaptive Graph Shrinking for Quantum Optimization of Constrained Combinatorial Problems},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZXGQE7C5}},
  note         = {Machine review of arXiv:2506.14250}
}
read the original abstract

A range of quantum algorithms, especially those leveraging variational parameterization and circuit-based optimization, are being studied as alternatives for solving classically intractable combinatorial optimization problems (COPs). However, their applicability is limited by hardware constraints, including shallow circuit depth, limited qubit counts, and noise. To mitigate these issues, we propose a hybrid classical--quantum framework based on graph shrinking to reduce the number of variables and constraints in QUBO formulations of COPs, while preserving problem structure. Our approach introduces three key ideas: (i) constraint-aware shrinking that prevents merges that will likely violate problem-specific feasibility constraints, (ii) a verification-and-repair pipeline to correct infeasible solutions post-optimization, and (iii) adaptive strategies for recalculating correlations and controlling the graph shrinking process. We apply our approach to three standard benchmark problems: Multidimensional Knapsack (MDKP), Maximum Independent Set (MIS), and the Quadratic Assignment Problem (QAP). Empirical results show that our approach improves solution feasibility, reduces repair complexity, and enhances quantum optimization quality on hardware-limited instances. These findings demonstrate a scalable pathway for applying near-term quantum algorithms to classically challenging constrained optimization problems.

Figures

Figures reproduced from arXiv: 2506.14250 by the authors.

Figure 1
Figure 1. FIG. 1: Sequence of graph reductions. Starting with the [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
Figure 2
Figure 2. FIG. 2: Optimality gap (%) for various shrinking strategies on MDKP benchmark instances. Fixed strategies reduce [PITH_FULL_IMAGE:figures/full_fig_p014_2.png] view at source ↗
Figure 3
Figure 3. FIG. 3: Comparison of Relative Solution Quality (RSQ%) for MIS benchmark instances. RSQ is defined as the ratio [PITH_FULL_IMAGE:figures/full_fig_p015_3.png] view at source ↗
Figures from the paper (8 more)
Figure 4
Figure 4. Figure 4: FIG. 4: Comparison of Optimality Gap (%) for MDKP benchmark instances. The optimality gap measures the [PITH_FULL_IMAGE:figures/full_fig_p016_4.png]
Figure 5
Figure 5. Figure 5: FIG. 5: Comparison of Optimality Gap (%) for QAP benchmark instances. The optimality gap measures the [PITH_FULL_IMAGE:figures/full_fig_p017_5.png]
Figure 6
Figure 6. Figure 6: FIG. 6: Total runtime (log scale) vs. final graph size for MIS instances. Classical solvers are consistently efficient. [PITH_FULL_IMAGE:figures/full_fig_p017_6.png]
Figure 7
Figure 7. Figure 7: FIG. 7: Total runtime (log scale) vs. final solution size for MDKP instances. Classical solvers dominate in efficiency, [PITH_FULL_IMAGE:figures/full_fig_p018_7.png]
Figure 8
Figure 8. Figure 8: FIG. 8: Total runtime (log scale) vs. final solution size for QAP instances. Runtimes remain high due to problem [PITH_FULL_IMAGE:figures/full_fig_p018_8.png]
Figure 9
Figure 9. Figure 9: FIG. 9: Phase-wise runtime breakdown (log scale) for MIS instances. Each bar represents an instance with segments [PITH_FULL_IMAGE:figures/full_fig_p020_9.png]
Figure 10
Figure 10. Figure 10: FIG. 10: Phase-wise runtime breakdown (log scale) for MDKP instances. Shrinking and solving phases dominate [PITH_FULL_IMAGE:figures/full_fig_p021_10.png]
Figure 11
Figure 11. Figure 11: FIG. 11: Phase-wise runtime breakdown (log scale) for QAP instances. Due to the complexity of QAP, time spent [PITH_FULL_IMAGE:figures/full_fig_p022_11.png]

Discussion (0). Sign in 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. Cutting Slack: Quantum Optimization with Slack-Free Methods for Combinatorial Benchmarks

    quant-ph 2025-07 reject novelty 4.0 of 10

    Using Lagrangian multiplier updates instead of slack variables reduces qubit counts and sometimes improves solution quality on small quantum optimization benchmarks.

Reference graph

Works this paper leans on

40 extracted references · 37 canonical work pages · cited by 1 Pith paper

  1. [1]

    A review of simheuristics: Extending metaheuristics to deal with stochastic com- binatorial optimization problems

    Angel A Juan, Javier Faulin, Scott E Grasman, Markus Rabe, and Gonçalo Figueira. A review of simheuristics: Extending metaheuristics to deal with stochastic com- binatorial optimization problems. Operations Research Perspectives, 2:62–72, 2015. 1

    work page 2015

  2. [2]

    Springer Science & Business Media, 1998

    Dingzhu Du and Panos M Pardalos.Handbook of com- binatorial optimization, volume 4. Springer Science & Business Media, 1998. 1

    1998

  3. [3]

    Ma- chine learning for combinatorial optimization: a method- ological tour d’horizon.European Journal of Operational Research, 290(2):405–421, 2021

    Yoshua Bengio, Andrea Lodi, and AntoineProuvost. Ma- chine learning for combinatorial optimization: a method- ological tour d’horizon.European Journal of Operational Research, 290(2):405–421, 2021. 1

    work page 2021

  4. [4]

    Optimal inapproximability results for max- cut and other 2-variable csps?SIAM Journal on Com- puting, 37(1):319–357, 2007

    Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell. Optimal inapproximability results for max- cut and other 2-variable csps?SIAM Journal on Com- puting, 37(1):319–357, 2007. 1

    work page 2007

  5. [5]

    A quantum approximate optimization algorithm, 2014

    Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm, 2014. 1

    work page 2014

  6. [6]

    A variational eigenvalue solver on a photonic quantum processor.Nature commu- nications, 5(1):4213, 2014

    Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man- Hong Yung, Xiao-Qi Zhou, Peter J Love, Alán Aspuru- Guzik, and Jeremy L O’brien. A variational eigenvalue solver on a photonic quantum processor.Nature commu- nications, 5(1):4213, 2014. 1

    work page 2014

  7. [7]

    Quantum optimization using a 127- qubit gate-model ibm quantum computer can outper- form quantum annealers for nontrivial binary optimiza- tion problems

    Natasha Sachdeva, Gavin S Hartnett, Smarak Maity, Samuel Marsh, Yulun Wang, Adam Winick, Ryan Dougherty, Daniel Canuto, You Quan Chong, Michael Hush, et al. Quantum optimization using a 127- qubit gate-model ibm quantum computer can outper- form quantum annealers for nontrivial binary optimiza- tion problems. arXiv preprint arXiv:2406.01743, 2024. 1

    arXiv 2024

  8. [8]

    Herzog, Friedrich Wagner, Christian Ufrecht, Lilly Palackal, Axel Plinge, Christopher Mutschler, and Daniel D

    Laura S. Herzog, Friedrich Wagner, Christian Ufrecht, Lilly Palackal, Axel Plinge, Christopher Mutschler, and Daniel D. Scherer. Improving quantum and classical de- composition methods for vehicle routing, 2024. 2

    work page 2024

Show all 40 references
  1. [9]

    Victor Fischer, Maximilian Passek, Friedrich Wagner, Jernej Rudi Finžgar, Lilly Palackal, and Christian B. Mendl. Quantum and classical correlations in shrinking algorithms for optimization, 2024. 2, 6

    2024

  2. [10]

    Experiments in quadratic 0–1 programming

    Francisco Barahona, Michael Jünger, and Gerhard Reinelt. Experiments in quadratic 0–1 programming. Mathematical programming, 44(1):127–137, 1989. 2, 5, 12

    1989

  3. [11]

    Springer, 2004

    Hans Kellerer, Ulrich Pferschy, David Pisinger, Hans Kellerer, Ulrich Pferschy, and David Pisinger.Multidi- mensional knapsack problems. Springer, 2004. 2

    2004

  4. [12]

    Find- ing a maximum independent set.SIAM Journal on Com- puting, 6(3):537–546, 1977

    Robert Endre Tarjan and Anthony E Trojanowski. Find- ing a maximum independent set.SIAM Journal on Com- puting, 6(3):537–546, 1977. 2

    1977

  5. [13]

    Assign- ment problems and the location of economic activities

    Tjalling C Koopmans and Martin Beckmann. Assign- ment problems and the location of economic activities. Econometrica: journal of the Econometric Society, pages 53–76, 1957. 2

    1957

  6. [14]

    Benchmark instances for the multidimen- sional knapsack problem

    JH Drake. Benchmark instances for the multidimen- sional knapsack problem. Available from ResearchGate, at, 2015. 2

    2015

  7. [15]

    N. J. A. Sloane. Challenge problems: Independent sets in graphs, 2000. Online; accessed February 10, 2025

    2000

  8. [16]

    Burkard, Stefan E

    Rainer E. Burkard, Stefan E. Karisch, and Franz Rendl. QAPLIB–a quadratic assignment problem library.Jour- nal of Global Optimization, 10(4):391–403, 1997

    1997

  9. [17]

    QAPLIB: Quadratic Assignment Problem Library – Problem Instances and Solutions

    QAPLIB Committee. QAPLIB: Quadratic Assignment Problem Library – Problem Instances and Solutions. https://coral.ise.lehigh.edu/data-sets/qaplib/ qaplib-problem-instances-and-solutions/, 2011. Accessed: 2025-06-08. 2

    2011

  10. [18]

    Lotshaw, Sarah Powers, George Siopsis, Travis Humble, and James Ostrowski

    Moises Ponce, Rebekah Herrman, Phillip C. Lotshaw, Sarah Powers, George Siopsis, Travis Humble, and James Ostrowski. Graph decomposition techniques for solv- ing combinatorial optimization problems with variational quantum algorithms. arXiv preprint arXiv:2306.00494,

    arXiv

  11. [19]

    Seymour and Robin Thomas

    Paul D. Seymour and Robin Thomas. Call routing and the ratcatcher. Combinatorica, 14:217–241, 1994. 2

    1994

  12. [20]

    Bridging classical and quan- tum with sdp initialized warm-starts for qaoa, 2022

    Reuben Tate, Majid Farhadi, Creston Herold, Greg Mohler, and Swati Gupta. Bridging classical and quan- tum with sdp initialized warm-starts for qaoa, 2022. 2

    2022

  13. [21]

    A branch-and- cut algorithm for the resolution of large-scale symmetric travelingsalesmanproblems

    Manfred Padberg and Giovanni Rinaldi. A branch-and- cut algorithm for the resolution of large-scale symmetric travelingsalesmanproblems. SIAM review, 33(1):60–100,

  14. [22]

    Author and B

    A. Author and B. Author. State-space reduction tech- nique inspired by quantum walk algorithms.Journal of Quantum Computing, 10(2):123–456, 2024. 2

    2024

  15. [23]

    Quantum approximate optimization of non-planar graph problems on a planar superconducting processor.Nature Physics, 17(3):332–336, 2021

    Matthew P Harrigan, Kevin J Sung, Matthew Neeley, Kevin J Satzinger, Frank Arute, Kunal Arya, Juan Ata- laya, JosephCBardin, RamiBarends, SergioBoixo, etal. Quantum approximate optimization of non-planar graph problems on a planar superconducting processor.Nature Physics, 17(3...

    2021

  16. [24]

    Quantum-informed recursive optimization algorithms

    John Smith and Jane Doe. Quantum-informed recursive optimization algorithms. Physical Review X Quantum, 5(2):020327, 2024. 3

    2024

  17. [25]

    A separator theorem for planar graphs

    Richard J Lipton and Robert Endre Tarjan. A separator theorem for planar graphs. SIAM Journal on Applied Mathematics, 36(2):177–189, 1979. 3

    1979

  18. [26]

    Finding near-optimal independent sets at scale

    Sebastian Lamm, Peter Sanders, Christian Schulz, Dar- ren Strash, and Renato F Werneck. Finding near-optimal independent sets at scale. In 2016 Proceedings of the eighteenth workshop on algorithm engineering and exper- iments (ALENEX), pages 138–150. SIAM, 2016. 3

    2016

  19. [27]

    Wahl and Sergii Strelchuk

    Thorsten B. Wahl and Sergii Strelchuk. Simulating quan- tum circuits using efficient tensor network contraction al- gorithms with subexponential upper bound.Phys. Rev. Lett., 131:180601, Oct 2023. 3

    2023

  20. [28]

    Multilevel combinatorial optimization across quantum architectures.ACM Transactions on Quantum Computing, 2(1):1–29, 2021

    Hayato Ushijima-Mwesigwa, Ruslan Shaydulin, Chris- tian FA Negre, Susan M Mniszewski, Yuri Alexeev, and Ilya Safro. Multilevel combinatorial optimization across quantum architectures.ACM Transactions on Quantum Computing, 2(1):1–29, 2021. 3

    2021

  21. [29]

    A constraint programming approach for qubo solving and quantum annealing

    Philippe Codognet. A constraint programming approach for qubo solving and quantum annealing. In Compan- ion Proceedings of the 8th International Conference on the Art, Science, and Engineering of Programming, pages 126–132, 2024. 3

    2024

  22. [30]

    Ising formulations of many np problems

    Andrew Lucas. Ising formulations of many np problems. Frontiers in physics, 2:5, 2014. 3, 4

    2014

  23. [31]

    Quantum approximate optimization with parallelizable gates

    Wolfgang Lechner. Quantum approximate optimization with parallelizable gates. IEEE Transactions on Quan- tum Engineering, 1:1–6, 2020. 4

    2020

  24. [32]

    Improved approximation algorithms for maximum cut and satisfia- 24 bility problems using semidefinite programming.Journal of the ACM (JACM), 42(6):1115–1145, 1995

    Michel X Goemans and David P Williamson. Improved approximation algorithms for maximum cut and satisfia- 24 bility problems using semidefinite programming.Journal of the ACM (JACM), 42(6):1115–1145, 1995. 5

    1995

  25. [33]

    A unified framework for optimization-based graph coarsen- ing

    Manoj Kumar, Anurag Sharma, and Sandeep Kumar. A unified framework for optimization-based graph coarsen- ing. Journal of Machine Learning Research, 24(118):1– 50, 2023. 8

    2023

  26. [34]

    Graph coars- ening with preserved spectral properties

    Yu Jin, Andreas Loukas, and Joseph JaJa. Graph coars- ening with preserved spectral properties. InInternational Conference on Artificial Intelligence and Statistics, pages 4452–4462. PMLR, 2020

    2020

  27. [35]

    Spectrally approximating large graphs with smaller graphs

    Andreas Loukas and Pierre Vandergheynst. Spectrally approximating large graphs with smaller graphs. InIn- ternational conference on machine learning, pages 3237–

  28. [36]

    Dey, Pan Peng, Alfred Rossi, and Anasta- sios Sidiropoulos

    Tamal K. Dey, Pan Peng, Alfred Rossi, and Anasta- sios Sidiropoulos. Spectral concentration and greedy k- clustering, 2018. 8

    2018

  29. [37]

    A review on quantum approximate optimization algorithm and its variants.Physics Reports, 1068:1–66, June 2024

    Kostas Blekos, Dean Brand, Andrea Ceschini, Chiao-Hui Chou, Rui-Hao Li, Komal Pandya, and Alessandro Sum- mer. A review on quantum approximate optimization algorithm and its variants.Physics Reports, 1068:1–66, June 2024. 12

    2024

  30. [38]

    Approximate solutions of combinatorial problems via quantum relaxations

    Bryce Fuller, Charles Hadfield, Jennifer R Glick, Takashi Imamichi, Toshinari Itoko, Richard J Thompson, Yang Jiao, Marna M Kagele, Adriana W Blom-Schieber, Rudy Raymond, et al. Approximate solutions of combinatorial problems via quantum relaxations. IEEE Transactions on Quant...

    2024

  31. [39]

    Our method consistently produced feasible solutions across all instances and achieved competitive optimality gaps

    Results Tables I and II present the performance of our graph shrinking framework on benchmark instances of the Multidi- mensional Knapsack Problem (MDKP) and the Maximum Independent Set (MIS) problem, respectively. Our method consistently produced feasible solutions across all...

  32. [40]

    Fixed- ratio strategies reduced the problem to⌊2/3 · n⌋ and ⌊1/2 · n⌋ variables (qubits), wheren is the original problem size

    Observations Our graph shrinking framework significantly reduced problem sizes while maintaining high-quality solutions. Fixed- ratio strategies reduced the problem to⌊2/3 · n⌋ and ⌊1/2 · n⌋ variables (qubits), wheren is the original problem size. Additionally, the Adaptive Gr...

Pith tools

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