A comprehensive benchmark of an Ising machine on the Max-Cut problem

Christian M\"unch; Fritz Schinkel; Markus Kirsch; Marten Winkler; Martin Kliesch; Salwa Shaglel; Stefan Walter

REVIEW 3 major objections 4 minor 75 references

A comprehensive benchmark of an Ising machine on the Max-Cut problem

T0 review · 3 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read Fujitsu's Digital Annealer beats top classical Max-Cut heuristics on roughly 69 percent of MQLib instances.

desk verdict A transparent, large-scale benchmark shows the DA is competitive, but the headline win rates are conditional on a stale heuristic selection and a proxy time budget. read the letter →

arxiv 2507.22117 v1 pith:TVAVIPRM submitted 2025-07-29 quant-ph cs.ET

Salwa Shaglel , Markus Kirsch , Marten Winkler , Christian Münch , Stefan Walter , Fritz Schinkel , Martin Kliesch This is my paper

classification quant-phcs.ET MSC 05C8568W2090C27

keywords DigitalAnnealerMax-CutQUBOIsingmachinebenchmarkMQLibsimulatedannealingquantum-inspiredoptimization

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 benchmarks Fujitsu's Digital Annealer, a quantum-inspired CMOS chip that runs an enhanced simulated annealing search, against the strongest classical heuristics on the Max-Cut problem. On a large, diverse set of 2,125 MQLib graph instances up to about 53,000 variables, the second-generation Digital Annealer (DAv2) finds a better cut than the selected classical heuristic in about 69.2 percent of the medium-to-large cases, and the third-generation machine (DAv3) does so in about 60.8 percent. The authors argue that a QUBO/Ising-machine solver can today compete with and often beat purpose-built classical heuristics in wall-clock time on practical Max-Cut problems, and they highlight fast convergence as a practical strength.

What carries the argument

The Digital Annealer Unit (DAU) is a CMOS ASIC that executes an enhanced simulated annealing algorithm directly on QUBO problems with arbitrary connectivity and up to 8,192 variables. It uses parallelized rejection-free search, dynamic energy offsetting, and parallel tempering, plus for DAv3 a software layer with global search that extends the usable size to 100,000 variables. The comparison protocol the paper adopts is the Dunning et al. time-limit methodology: each instance receives a time budget equal to the mean runtime of a simple greedy local search; DAv2 is fitted to that budget through runtime models, DAv3 gets a buffered limit, and the classical heuristics are rerun under these new limits.

What would settle it

Re-running the comparison with either (a) time limits based on the typical runtime of the strongest classical heuristics themselves, or (b) all 37 MQLib heuristics under the paper's greedy-derived limits, would settle whether the reported win rates persist.

Watch

Extended reading notes

Core claim

The paper claims that the Digital Annealer is a competitive Max-Cut heuristic on the MQLib benchmark suite. Across 738 medium-and-large instances, DAv2 beats the category-best classical heuristic (BURER2002, PAL2004bMTS2, or MERZ1999GLS) with a 69.24 percent win rate and an 11.92 percent tie rate; DAv3 over 819 instances has a 60.81 percent win rate and a 17.33 percent tie rate. In a complementary comparison on 45 instances chosen by D-Wave's hybrid solver, DAv3 beats or ties D-Wave HS on most integer-weighted instances, and on 16 sparse G-set instances against the QIS3 metaheuristic, one or both DA versions match or beat QIS3 on 14 instances. The paper attributes remaining losses mainly to floating-point coefficients, since the DA evaluates integer QUBOs and rounds scaled floats, and to instances exceeding the single-DAU 8,192-variable capacity.

Load-bearing premise

The benchmark's fairness rests on the assumption that the time limit derived from a simple greedy local search is a valid measure of how hard each instance is, so that all solvers are compared under equally meaningful time budgets.

Editorial extensions

If this is right

For practitioners with QUBO-encodable problems, the DA offers a fast, out-of-the-box alternative to tuning classical heuristics, with high-quality solutions often found in the first seconds.
The benchmark suggests that the practical frontier of large QUBO solving is already accessible today, up to tens of thousands of variables, on quantum-inspired hardware.
The integer-only precision of the DA is a real constraint: float-weighted instances lose accuracy under scaling and rounding, so integer or well-conditioned QUBO models are the favorable application regime.
The per-instance results indicate that solver performance is highly dependent on graph size, density, and weight type, motivating hybrid workflows that dispatch instances to different solvers.
The paper's methodological checklist for benchmarking quantum and quantum-inspired solvers, including instance-dependent time limits and reporting actual runtimes, could become a standard for transparent hardware comparisons.

Reading between the lines

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

A striking hidden implication is that the comparison metric depends on the choice of the single 'best' heuristic per category; rerunning all 37 MQLib heuristics with the new time limits could change the win statistics substantially, likely in the classical heuristics' favor.
Because the time budget is calibrated to a simple greedy local search, harder-than-greedy instances should favor solvers with aggressive search heuristics, so the win/loss statistics may partly measure how much search effort each solver packs into the greedy-calibrated budget.
The reported rapid convergence suggests a testable extension: measuring time-to-cut-value curves with even shorter budgets might reveal that for many instances the DA's advantage comes almost entirely from its first few seconds of search.
The float-instance losses imply a concrete fix worth testing: normalizing or scaling floating weights specifically for Max-Cut before the DA's internal rounding could recover some of the apparent quality gap.

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.

Desk Editor's Note

read the letter

Short version: this is the most complete public benchmark of a commercial Ising machine I've seen, and the authors deserve credit for the transparency. But the headline win rates are computed against heuristic baselines that were picked using the original Dunning et al. data, not re-selected under the new time budgets, so the specific numbers are softer than the abstract suggests.

The genuinely new part is the scale: 2,125 MQLib instances, up to 53k variables, plus head-to-head runs against D-Wave's hybrid solver on their 45 instances and QIS3 on 16 G-set instances. The paper also does several things right: it publishes actual runtimes and deviations from limits, provides solution files and seeds in a public repo, models DAv2's runtime in detail, and discloses the Fujitsu funding and employment. The treatment of the float-instance rounding problem is honest and shows the losses cluster exactly there.

The main soft spot is the baseline selection. Section 3.3 picks the 'best' MQLib heuristic per category from Dunning et al.'s original results, then reruns only those three under the new, often shorter, time limits. If another of the 37 heuristics would perform better under these budgets, the comparison is not against the best classical heuristics. That's a real possibility, and it is testable. The 69.2% and 60.8% figures should be treated as conditional on that selection. The time-limit calibration is also a proxy—a first-improving local search with 1500 restarts—but the authors at least document its behavior in Appendix D.

Minor quibbles: only best-of-5 cut values are reported without variance, and the integer-only win rates would be more informative given the DA's integer limitation. The QIS3 comparison uses the original paper's results rather than fresh runs, which is fine but limits the strength of that claim.

None of this sinks the paper. The central finding that the DA is competitive on medium-to-large sparse and integer-weighted instances is likely correct. Who benefits: practitioners choosing solvers and anyone studying benchmarking methodology. It deserves a serious referee, but the authors should be asked to re-select baselines under the new time limits and report integer-only numbers. That would turn a good benchmark into a very solid one.

Referee Report

3 major / 4 minor

Summary. This paper benchmarks Fujitsu's Digital Annealer (DAv2 and DAv3) on Max-Cut against three classical MQLib heuristics on 2,125 instances, against D-Wave's hybrid solver on 45 instances, and against the QIS3 heuristic on 16 G-set instances. Following Ref. [17], the authors assign instance-specific time limits, recalculated from the runtime of a first-improving greedy local search with 1500 restarts, and run every solver with five seeds, reporting best cut and wall-clock time while publishing solution files. The main quantitative claims are that DAv2 finds a better cut than the category-best MQLib heuristic on 69.2% of the medium-and-large benchmarked instances and DAv3 does so on 60.8%, with many losses attributed to floating-point coefficient rounding on the integer-only DA hardware.

Significance. If the benchmark conditions are accepted, this is a valuable and unusually transparent large-scale comparison of an Ising machine against established classical heuristics. The paper follows many of its own stated best-practice criteria: runtime handling is discussed in detail, five-seed statistics are reported, solution configurations are made available, the conflict of interest is declared, and known deficiencies of the DA are explicitly examined rather than hidden. The broad claim that the DA is competitive on medium-to-large, mostly sparse Max-Cut instances is plausible and worth publishing. However, two load-bearing methodological choices—the stale selection of the category-best heuristics and the use of one greedy-search proxy to calibrate all time budgets—mean that the headline win rates are not yet established as rates against the best classical heuristics under the benchmark's own conditions. The issues are testable and appear fixable within the scope of a revision.

major comments (3)

[§3.3, Table 3] The 'best-performing MQLib heuristic' per category is selected using the original results of Dunning et al. [17], while the comparisons themselves are run under the newly calibrated instance-specific time limits of §3.1. Appendix D shows that under those new limits BURER2002 and PAL2004bMTS2 exceed the 10% safety margin on a noticeable number of instances, so the budget materially changes heuristic behavior. The paper provides no evidence that the three selected heuristics remain the best of the 37 under the new budgets. The headline win rates of 69.2% and 60.8% therefore compare against heuristics that are assumed, not verified, to be the strongest classical baselines. Please either re-run a larger shortlist (or the full pool) under the new time limits and re-select, or report a sensitivity analysis and adjust the claims accordingly.
[§3.1] The instance-specific time limit is the mean runtime of a first-improving greedy local search with 1500 restarts. This single proxy determines the budget for every solver, including heuristics with very different search mechanisms such as iterated tabu search and genetic local search. If this greedy procedure is not representative of the time those heuristics need to reach their best solutions, the win/loss statistics can be partly an artifact of budget mis-calibration. A concrete test would be to recompute the main win/tie/loss counts under, for example, half and double the baseline time limits, or under an alternative difficulty proxy, and to show that the qualitative conclusion is stable.
[§4.1, Figs. 3 and 5] The aggregate win rates include instances with floating-point weights, for which the DA's integer conversion is known to alter the objective (Section 4.1). The text states that nearly all DAv2 losses below 0.998 accuracy and most DAv3 losses in [0.998, 1) are float instances, yet the headline win rate is reported over the combined set. The reader therefore cannot tell whether the DA is competitive on integer instances alone, which is the case least affected by a known hardware limitation. Please report integer-only and float-only win/tie/loss rates (and ideally accuracy-ratio summaries) for the main benchmark; this materially affects the practical scope of the central claim.

minor comments (4)

[Abstract and Section 5] The 69.2% and 60.8% win rates refer to the filtered medium/x-large subsets (738 and 819 instances), not to all 2,125 instances; Appendix A reports a materially different profile for DAv2 on x-small/small instances (46.9% wins, 38.7% ties). Please state this explicitly in the abstract and conclusion to prevent the rates from being read as overall statistics for the full benchmark set.
[Figure 12 caption] The caption spells one heuristic as 'PALUBECKIS2004bMTS2'; this should be 'PAL2004bMTS2' everywhere for consistency with the text and Table 3.
[§4.1, Figs. 2 and 4] For categories with small instance counts (for example the balanced-medium and dense-medium cells), the cumulative-bar proportions should be accompanied by the raw instance counts or confidence intervals; without them, the visual comparison can appear stronger than the data support.
[Table 4] Add a table footnote that G66 and G72 are not run with DAv2 because they exceed the 8192-variable DAU capacity; the text explains this, but the table would be self-contained with the footnote.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the DA performance claims are measured against external MQLib heuristics and published baselines, and no prediction reduces to a fitted input.

full rationale

This paper is a measurement benchmark rather than a derivation. The central claims (DAv2 wins ~69.2%, DAv3 ~60.8% against selected MQLib heuristics) are based on cut values obtained from running solvers under instance-specific time limits; the limits are a benchmarking budget, not a fitted predictor of the outcome. The best-heuristic-per-category selection (Section 3.3) comes from the external Dunning et al. data [17] and was not chosen using DA results, so the comparison is not self-definitional. The DAv2 runtime model (Appendix B) and DAv3 offset choice (Appendix C) calibrate solver runtimes to the baseline budget; although tuning on the benchmark set is a soundness concern, the fitted quantities are runtimes, not the reported cut values, so the win/loss statistics are not forced by construction. Self-citations ([52] used for DA temperature sampling and [58] for a prior application) describe implementation details and prior use, and are not load-bearing for the performance conclusions. No equation in the paper defines the claimed result in terms of itself, and no known result is merely renamed. The stale-baseline and time-budget concerns raised in the skeptic view are potential biases in benchmark fairness, not instances of circular reasoning.

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

The benchmark claim depends on several choices: the time limit calibration (greedy local search baseline), the heuristic selection per category, the integer scaling of weights, and the best-of-5 reporting. These are transparently described, but they are choices rather than fixed facts, so the claim rests on them.

free parameters (5)

DAv3 time limit offset (Eq. 5, Appendix C) = 3 seconds
Empirically chosen to balance runtime compliance and average accuracy; directly sets DAv3 time limits in the benchmark.
DAv2 runtime model coefficients (Table 5, Eqs. 6-7) = a,b,c,d,e,k,g,h per size category
Fitted to measured DAv2 runtimes to estimate run/iteration counts; these estimated time limits affect all DAv2 comparisons.
Instance filtering thresholds (Section 3.2) = baseline time > 0.25s; sizes 2048-8192 (DAv2) and >=2048 (DAv3)
Chosen by hand to avoid small-instance runtime overshoot; the reported headline win rates are on the resulting subset, not the full MQLib set.
Baseline local search restarts (Section 3.1) = 1500
Number of restarts in the greedy local search that defines the baseline time limit for every instance; an arbitrary protocol constant.
Number of runs per solver (Section 4) = 5 seeds
Results are best-of-5; the choice of 5 seeds affects the reported best cut values and the stability of win/loss rates.

assumptions (5)

standard math QUBO formulation of Max-Cut is exact (Eq. 3)
Used to encode Max-Cut instances for all solvers; a standard reduction from [2,3].
domain assumption MQLib instance set represents real-world Max-Cut problem diversity
The benchmark's external validity depends on this; Section 3.2 justifies this with instance sources but does not prove representativeness.
domain assumption Integer scaling and rounding of QUBO coefficients preserves solution quality for integer instances
Assumed in Section 2.2; Section 4 shows it is violated for float instances, where DAv3 loses precision and performance.
domain assumption Best-of-5 runs with 5 seeds yield a stable performance estimate
All solvers are compared on the best of 5 seeds (Section 4); no variance or confidence intervals are reported, so statistical significance is assumed.
ad hoc to paper Baseline time limits from greedy local search are a fair basis for comparing heterogeneous solvers
The central methodological premise of the paper (Section 3.1); if the greedy local search underestimates or overestimates instance difficulty, the win/loss rates could change.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A comprehensive benchmark of an Ising machine on the Max-Cut problem." pith.science (2026). https://pith.science/paper/TVAVIPRM

@misc{pith2026250722117,
  author       = {Pith},
  title        = {Pith review of: A comprehensive benchmark of an Ising machine on the Max-Cut problem},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TVAVIPRM}},
  note         = {Machine review of arXiv:2507.22117}
}

read the original abstract

QUBO formulations of combinatorial optimization problems allow for solving them using various quantum heuristics. While large-scale quantum computations are currently still out of reach, we can already numerically test such QUBO formulations on a perhaps surprisingly large scale. In this work, we benchmark Fujitsu's Digital Annealer (DA) on the Max-Cut problem, which captures the main complexity of the QUBO problem. We make a comprehensive benchmark against leading other heuristic algorithms on graphs with up to 53,000 variables by focusing on the wall-clock time. Moreover, we compare the DA performance against published performance results of the D-Wave hybrid quantum-classical annealer and the recently proposed QIS3 heuristic. Based on performance statistics for over 2,000 graphs from the MQLib, we find that the DA yields competitive results. We hope that this benchmark demonstrates the extent to which large QUBO instances can be heuristically solved today, yielding consistent results across different solvers.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

75 extracted references · 58 canonical work pages

[17]

Dunning, S

I. Dunning, S. Gupta, and J. Silberholz,What works best when? a sys- tematic evaluation of heuristics for Max-Cut and QUBO, INFORMS J. on Computing30, 608–624 (2018)

work page 2018
[1]

Glover, G

F. Glover, G. A. Kochenberger, and Y. Du,Applications and computa- tional advances for solving the QUBO model, inSpringer eBooks(2022) p. 39–56

work page 2022
[2]

Lucas,Ising formulations of many NP problems, Frontiers in Physics 2, 5 (2014), arXiv:1302.5843 [cond-mat.stat-mech]

A. Lucas,Ising formulations of many NP problems, Frontiers in Physics 2, 5 (2014), arXiv:1302.5843 [cond-mat.stat-mech]

arXiv 2014
[3]

Glover, G

F. Glover, G. Kochenberger, and Y. Du,A Tutorial on Formulating and Using QUBO Models, arXiv:1811.11538 [cs.DS] (2018)

arXiv 2018
[4]

Ratke,List of QUBO formulations,https://blog.xa0.de/post/ List-of-QUBO-formulations/(2021), accessed 2025-06-19

D. Ratke,List of QUBO formulations,https://blog.xa0.de/post/ List-of-QUBO-formulations/(2021), accessed 2025-06-19

work page 2021
[5]

A. P. Punnen, ed.,The Quadratic Unconstrained Binary Optimization Problem: Theory, Algorithms, and Applications, 1st ed. (Springer Cham,

work page
[6]

Aaronson,The limits of quantum computers, Scientific American (2008)

S. Aaronson,The limits of quantum computers, Scientific American (2008)

work page 2008
[7]

H. Goto, K. Tatsumura, and A. R. Dixon,Combinatorial op- timization by simulating adiabatic bifurcations in nonlinear Hamiltonian systems, Science Advances5, eaav2372 (2019), https://www.science.org/doi/pdf/10.1126/sciadv.aav2372

doi:10.1126/sciadv.aav2372 2019

Show all 75 references

[8]

Tatsumura, M

K. Tatsumura, M. Yamasaki, and H. Goto,Scaling out Ising machines us- ing a multi-chip architecture for simulated bifurcation, Nature Electronics 4, 208 (2021)

2021
[9]

D-Wave Quantum Inc.,Performance gains in the D-Wave Advantage2 system at the 4,400-qubit scale, Whitepaper 14-1083A-A (D-Wave Quan- tum Inc., 2025) released May 12, 2025

2025
[10]

Okuyama, T

T. Okuyama, T. Sonobe, K.-i. Kawarabayashi, and M. Yamaoka,Binary optimization by momentum annealing, Phys. Rev. E100, 012111 (2019)

2019
[11]

Inagaki, Y

T. Inagaki, Y. Haribara, K. Igarashi, T. Sonobe, S. Tamate, T. Honjo, 32 A. Marandi, P. L. McMahon, T. Umeki, K. Enbutsu, O. Tadanaga, H. Takenouchi, K. Aihara, K. ichi Kawarabayashi, K. Inoue, S. Ut- sunomiya, and H. Takesue,A coherent Ising machine for 2000-node op- timizati...

2016
[12]

Honjo, T

T. Honjo, T. Sonobe, K. Inaba, T. Inagaki, T. Ikuta, Y. Yamada, T. Kazama, K. Enbutsu, T. Umeki, R. Kasahara, K. ichi Kawarabayashi, and H. Takesue,100,000-spin coherent Ising machine, Science Advances 7, eabh0952 (2021)

2021
[13]

Nakayama, J

H. Nakayama, J. Koyama, N. Yoneoka, and T. Miyazawa,Third Genera- tion Digital Annealer Technology, Tech. Rep. (Fujitsu Laboratories, 2021) accessed: 2025-07-23

2021
[14]

Mohseni, P

N. Mohseni, P. L. McMahon, and T. Byrnes,Ising machines as hardware solvers of combinatorial optimization problems, Nature Reviews Physics 4, 363 (2022), arXiv:2204.00276 [quant-ph]

2022 arXiv
[15]

M. X. Goemans and D. P. Williamson,Improved approximation algo- rithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM (JACM)42, 1115 (1995)

1995
[16]

S. Khot, G. Kindler, E. Mossel, and R. O’Donnell,Optimal inapproxima- bility results for MAX-CUT and other 2-variable CSPs?, SIAM Journal on Computing37, 319 (2007)

2007
[18]

F. Phillipson,Fair benchmarking combinatorial optimization solvers in the era of emerging computing paradigms, inInnovations for Community Services, Communications in Computer and Information Science, Vol. 2513, edited by S. Zielinski, G. Eichler, C. Erfurth, and G. Fahrnberge...

2025
[19]

D-Wave Systems Inc.,Hybrid solver service: An overview, https://www.dwavequantum.com/media/4bnpi53x/14-1039a-b_ d-wave_hybrid_solver_service_an_overview.pdf(2020), white Paper

2020
[20]

J. Yang, D. Wang, X. Zhao, H. Zhang, M. Gao, and L. Yang,A Novel Solver for QUBO Problems: Performance Analysis and Comparative Study with State-of-the-Art Algorithms, arXiv e-prints , arXiv:2506.04596 (2025), arXiv:2506.04596 [quant-ph]

2025 arXiv
[21]

Dunning, S

I. Dunning, S. Gupta, and J. Silberholz,Mqlib: Implementations of heuristics for Max-Cut and QUBO(2018), accessed: 2025-07-05. 33

2018
[22]

Ye,Gset collection of graphs for Max-Cut benchmarking,https:// web.stanford.edu/~yyye/yyye/Gset/(2003), accessed 2025-06-26

Y. Ye,Gset collection of graphs for Max-Cut benchmarking,https:// web.stanford.edu/~yyye/yyye/Gset/(2003), accessed 2025-06-26

2003
[23]

Farhi, J

E. Farhi, J. Goldstone, and S. Gutmann,A Quantum Approximate Opti- mization Algorithm, arXiv:1411.4028 [quant-ph] (2014)

2014 arXiv
[24]

Zhou, S.-T

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

2020
[25]

Blekos, D

K. Blekos, D. Brand, A. Ceschini, C.-H. Chou, R.-H. Li, K. Pandya, and A. Summer,A review on quantum approximate optimization algorithm and its variants, Physics Reports1068, 1 (2024), a review on Quantum Approximate Optimization Algorithm and its variants

2024
[26]

Farhi, J

E. Farhi, J. Goldstone, and S. Gutmann,A quantum approximate opti- mization algorithm applied to a bounded occurrence constraint problem, arXiv:1412.6062 [quant-ph] (2014)

2014 arXiv
[27]

Barak, A

B. Barak, A. Moitra, R. O’Donnell, P. Raghavendra, O. Regev, D. Steurer, L. Trevisan, A. Vijayaraghavan, D. Witmer, and J. Wright, Beating the random assignment on constraint satisfaction problems of bounded degree, arXiv:1505.03424 [cs.CC] (2015)

2015 arXiv
[28]

J. R. McClean, S. Boixo, V. N. Smelyanskiy, R. Babbush, and H. Neven, Barren plateaus in quantum neural network training landscapes, Nature Communications9, 10.1038/s41467-018-07090-4 (2018)

2018 doi
[29]

Bittel and M

L. Bittel and M. Kliesch,Training Variational Quantum Algorithms Is NP-Hard, Phys. Rev. Lett.127, 120502 (2021), arXiv:2101.07267 [quant- ph]

2021 arXiv
[30]

Bittel, S

L. Bittel, S. Gharibian, and M. Kliesch,Optimizing the depth of varia- tional quantum algorithms is strongly QCMA-hard to approximate,in38th Computational Complexity Conference (CCC 2023),LeibnizInternational Proceedings in Informatics (LIPIcs), Vol. 264, edited by A. Ta-Shma ...

2023
[31]

G. G. Guerreschi and A. Y. Matsuura,QAOA for Max-Cut re- quires hundreds of qubits for quantum speed-up, Scientific Reports9, 10.1038/s41598-019-43176-9 (2019)

2019 doi
[32]

S. Wang, E. Fontana, M. Cerezo, K. Sharma, A. Sone, L. Cincio, and P. J. Coles,Noise-induced barren plateaus in variational quantum algorithms, Nature Communications12, 10.1038/s41467-021-27045-6 (2021)

2021 doi
[33]

Y. R. Sanders, D. W. Berry, P. C. Costa, L. W. Tessler, N. Wiebe, C.Gidney, H.Neven,andR.Babbush,Compilation of fault-tolerant quan- tum heuristics for combinatorial optimization, PRX Quantum1, 020312 34 (2020)

2020
[34]

Z. Cai, R. Babbush, S. C. Benjamin, S. Endo, W. J. Huggins, Y. Li, J. R. McClean, and T. E. O’Brien,Quantum error mitigation, Reviews of Modern Physics95, 045005 (2023), arXiv:2210.00921 [quant-ph]

2023 arXiv
[35]

Hamerly, T

R. Hamerly, T. Inagaki, P. L. McMahon, D. Venturelli, A. Marandi, T. Onodera, E. Ng, C. Langrock, K. Inaba, T. Honjo, K. Enbutsu, T. Umeki, R. Kasahara, S. Utsunomiya, S. Kako, K.-i. Kawarabayashi, R. L. Byer, M. M. Fejer, H. Mabuchi, D. Englund, E. Rieffel, H. Takesue, and Y....

2019 doi
[36]

Boothby, P

K. Boothby, P. Bunyk, J. Raymond, and A. Roy,Next-generation topology of d-wave quantum processors(2020), arXiv:2003.00133 [quant-ph]

2020 arXiv
[37]

Hauke, H

P. Hauke, H. G. Katzgraber, W. Lechner, H. Nishimori, and W. D. Oliver, Perspectives of quantum annealing: methods and implementations, Re- ports on Progress in Physics83, 054401 (2020)

2020
[38]

C. D. Gonzalez Calaza, D. Willsch, and K. Michielsen,Garden optimiza- tion problems for benchmarking quantum annealers, Quantum Informa- tion Processing20, 10.1007/s11128-021-03226-6 (2021)

2021 doi
[39]

Willsch, M

D. Willsch, M. Willsch, C. D. Gonzalez Calaza, F. Jin, H. De Raedt, M. Svensson, and K. Michielsen,Benchmarking advantage and d-wave 2000q quantum annealers with exact cover problems, Quantum Informa- tion Processing21, 10.1007/s11128-022-03476-y (2022)

2022 doi
[40]

Matsubara, M

S. Matsubara, M. Takatsu, Toshiyuki Miyazawa, T. Miyazawa, T. Shibasaki, Y. Watanabe, K. Takemoto, and H. Tamura,Digital An- nealer for High-Speed Solving of Combinatorial optimization Problems and Its Applications, Asia and South Pacific Design Automation Con- ference , 667
[41]

Ikutaet al.,Solving the maximum cut benchmark with an optimization solver, Research Institute for Mathematical Sciences Kokyuroku1941, 49 (2015), (In Japanese)

T. Ikutaet al.,Solving the maximum cut benchmark with an optimization solver, Research Institute for Mathematical Sciences Kokyuroku1941, 49 (2015), (In Japanese)

2015
[42]

Ma and J.-K

F. Ma and J.-K. Hao,A multiple search operator heuristic for the max-k- cut problem(2015), arXiv:1510.09156 [cs.DM]

2015 arXiv
[43]

Huang, J

T. Huang, J. Xu, T. Luo, X. Gu, R. Goh, and W.-F. Wong,Benchmark- ing quantum(-inspired) annealing hardware on practical use cases, IEEE Transactions on Computers72, 1692 (2023)

2023
[44]

Oshiyama and M

H. Oshiyama and M. Ohzeki,Benchmark of quantum-inspired heuristic solvers for quadratic unconstrained binary optimization,ScientificReports 12, 10.1038/s41598-022-06070-5 (2022). 35

2022 doi
[45]

Şeker, N

O. Şeker, N. Tanoumand, and M. Bodur,Digital annealer for quadratic unconstrained binary optimization: A comparative performance analysis, Appl. Soft Comput.127, 10.1016/j.asoc.2022.109367 (2022)

2022
[46]

Gurobi Optimization, LLC,Gurobi Optimizer Reference Manual(2023)

2023
[47]

Achterberg,SCIP: solving constraint integer programs, Mathematical Programming Computation1, 1 (2009)

T. Achterberg,SCIP: solving constraint integer programs, Mathematical Programming Computation1, 1 (2009)

2009
[48]

Optim.12, 503 (2002)

S.Burer, R.D.C.Monteiro,andY.Zhang,Rank-two relaxation heuristics for max-cut and other binary quadratic programs, SIAM J. Optim.12, 503 (2002)

2002
[49]

Palubeckis,Multistart tabu search strategies for the unconstrained bi- nary quadratic optimization problem, Annals of Operations Research131, 259 (2004)

G. Palubeckis,Multistart tabu search strategies for the unconstrained bi- nary quadratic optimization problem, Annals of Operations Research131, 259 (2004)

2004
[50]

Jiang, Y.-C

J.-R. Jiang, Y.-C. Shu, and Q.-Y. Lin,Benchmarks and recommendations for quantum, digital, and GPU annealers in combinatorial optimization, IEEE Access12, 125014 (2024)

2024
[51]

Kowalsky, T

M. Kowalsky, T. Albash, I. Hen, and D. A. Lidar,3-regular three- XORSAT planted solutions benchmark of classical and quantum heuris- tic optimizers, Quantum Science and Technology7, 025008 (2022), arXiv:2103.08464 [quant-ph]

2022 arXiv
[52]

Münch, F

C. Münch, F. Schinkel, S. Zielinski, and S. Walter,Transformation- Dependent Performance-Enhancement of Digital Annealer for 3-SAT, arXiv e-prints , arXiv:2312.11645 (2023), arXiv:2312.11645 [quant-ph]

2023 arXiv
[53]

Kao, J.-L

Y.-T. Kao, J.-L. Liao, and H.-C. Hsu,Solving Combinatorial Optimiza- tion Problems on Fujitsu Digital Annealer, arXiv:2311.05196 [quant-ph] (2023)

2023 arXiv
[54]

D. Leib, T. Seidel, S. Jäger, R. Heese, C. Jones, A. Awasthi, A. Niederle, M. Bortz, and et al.,An optimization case study for solving a transport robot scheduling problem on quantum-hybrid and quantum-inspired hard- ware, Scientific Reports13, 18743 (2023)

2023
[55]

Lee, P.-H

C. Lee, P.-H. Wang, and Y. J. Tseng,Digital annealing optimization for natural product structure elucidation, Briefings in Bioinformatics25, bbae600 (2024)

2024
[56]

A. A. Jha, E. L. Stoyanoff, G. Khundzakishvili, P. Kairys, H. Ushijima- Mwesigwa, and A. Banerjee,Digital annealing route to complex magnetic phase discovery, in2021 International Conference on Rebooting Comput- ing (ICRC)(2021) pp. 119–123

2021
[57]

Maruo, H

A. Maruo, H. Igarashi, H. Oshima, and S. Shimokawa,Optimization of planar magnet array using digital annealer, IEEE Transactions on Mag- 36 netics56, 1 (2020)

2020
[58]

Dornemann, S

J. Dornemann, S. Shaglel, M. Kliesch, and A. Taraz,A hybrid quantum- inspired and deep learning approach for the capacitated vehicle routing problem with time windows, inTHE 19TH LEARNING AND INTELLI- GENT OPTIMIZATION CONFERENCE(2025)

2025
[59]

Shaglel and M

S. Shaglel and M. Kirsch,DA Maxcut Benchmark (DAMB),https:// github.com/SalwaShaglel/DAMB(2025)

2025
[60]

Cohn and M

H. Cohn and M. Fielding,Simulated annealing: Searching for an opti- mal temperature schedule, SIAM Journal on Optimization9, 779 (1999), https://doi.org/10.1137/S1052623497329683

1999 doi
[61]

S. Chen, J. S. Rosenthal, A. Dote, H. Tamura, and A. Sheikholeslami,Op- timization via rejection-free partial neighbor search, Statistics and Com- puting33, 131 (2023)

2023
[62]

S. Chen, J. S. Rosenthal, A. Dote, H. Tamura, and A. Sheik- holeslami,Sampling via rejection-free partial neighbor search, Commu- nications in Statistics - Simulation and Computation54, 837 (2025), https://doi.org/10.1080/03610918.2023.2266157

2025
[63]

Lipowski and D

A. Lipowski and D. Lipowska,Roulette-wheel selection via stochastic ac- ceptance, Physica A: Statistical Mechanics and its Applications391, 2193 (2012)

2012
[64]

global.fujitsu.com/apidoc/da/en/index.html, accessed: 2025-07- 22

Fujitsu,Digital annealer api documentation,https://portal.aispf. global.fujitsu.com/apidoc/da/en/index.html, accessed: 2025-07- 22

2025
[65]

Beasley,Or-library: A collection of test instances for or problems (1990)

J. Beasley,Or-library: A collection of test instances for or problems (1990)

1990
[66]

T. Koch, A. Martin, D. Rehfeldt, and S. Voss,Steinlib: A library for steiner tree problems
[67]

Johnson and M

D. Johnson and M. Trick, eds.,Cliques, Coloring, and Satisfiability: Sec- ond DIMACS Implementation Challenge, DIMACS Series in Discrete Mathematics and Theoretical Computer Science (1993). [68]Seventh DIMACS implementation challenge: Semidefinite and related op- timization pr...

1993
[70]

Reinelt,TSPLIB–a traveling salesman problem library, ORSA Journal on Computing3, 376–384 (1991)

G. Reinelt,TSPLIB–a traveling salesman problem library, ORSA Journal on Computing3, 376–384 (1991)

1991
[71]

Wiegele,Biq Mac library: Max-Cut and binary quadratic programming 37 instances(2007)

A. Wiegele,Biq Mac library: Max-Cut and binary quadratic programming 37 instances(2007)

2007
[72]

Culberson,Flat graph generator

J. Culberson,Flat graph generator
[73]

Hagberg, P

A. Hagberg, P. Swart, and D. Schult,NetworkX – Python package for complex network analysis(2008)

2008
[74]

Rinaldi,Rudy: A Rudimental Graph Generator(1995)

G. Rinaldi,Rudy: A Rudimental Graph Generator(1995)

1995
[75]

Merz and B

P. Merz and B. Freisleben,Genetic algorithms for binary quadratic pro- gramming, inProceedings of the 1st Annual Conference on Genetic and Evolutionary Computation - Volume 1, GECCO’99 (Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1999) p. 417–424. 38

1999
[2022]

XIII + 319, eBook published July 12, 2022

pp. XIII + 319, eBook published July 12, 2022

2022
[2023]

34:1–34:24, arXiv:2211.12519 [quant-ph]

pp. 34:1–34:24, arXiv:2211.12519 [quant-ph]

arXiv

Pith tools

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

[1] [17]

Dunning, S

I. Dunning, S. Gupta, and J. Silberholz,What works best when? a sys- tematic evaluation of heuristics for Max-Cut and QUBO, INFORMS J. on Computing30, 608–624 (2018)

work page 2018

[2] [1]

Glover, G

F. Glover, G. A. Kochenberger, and Y. Du,Applications and computa- tional advances for solving the QUBO model, inSpringer eBooks(2022) p. 39–56

work page 2022

[3] [2]

Lucas,Ising formulations of many NP problems, Frontiers in Physics 2, 5 (2014), arXiv:1302.5843 [cond-mat.stat-mech]

A. Lucas,Ising formulations of many NP problems, Frontiers in Physics 2, 5 (2014), arXiv:1302.5843 [cond-mat.stat-mech]

arXiv 2014

[4] [3]

Glover, G

F. Glover, G. Kochenberger, and Y. Du,A Tutorial on Formulating and Using QUBO Models, arXiv:1811.11538 [cs.DS] (2018)

arXiv 2018

[5] [4]

Ratke,List of QUBO formulations,https://blog.xa0.de/post/ List-of-QUBO-formulations/(2021), accessed 2025-06-19

D. Ratke,List of QUBO formulations,https://blog.xa0.de/post/ List-of-QUBO-formulations/(2021), accessed 2025-06-19

work page 2021

[6] [5]

A. P. Punnen, ed.,The Quadratic Unconstrained Binary Optimization Problem: Theory, Algorithms, and Applications, 1st ed. (Springer Cham,

work page

[7] [6]

Aaronson,The limits of quantum computers, Scientific American (2008)

S. Aaronson,The limits of quantum computers, Scientific American (2008)

work page 2008

[8] [7]

H. Goto, K. Tatsumura, and A. R. Dixon,Combinatorial op- timization by simulating adiabatic bifurcations in nonlinear Hamiltonian systems, Science Advances5, eaav2372 (2019), https://www.science.org/doi/pdf/10.1126/sciadv.aav2372

doi:10.1126/sciadv.aav2372 2019