{"id":"e350e37a-ac02-41e6-97b5-02f2fcb7c061","arxiv_id":"2412.07460","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"On 139 Max-Cut instances, classical simulated annealing and Toshiba's SBM match or beat D-Wave's Hybrid solver on large graphs, and the fast-annealing QPU misses the global optimum on nearly all small instances.","lead":"This paper tests four solvers, including D-Wave's quantum processing unit and hybrid service, on 139 Max-Cut instances of 100 to 10,000 nodes. It finds that classical simulated annealing with enough time, and Toshiba's simulated bifurcation machine, give the best solutions, while the quantum unit trails on all but the smallest cases.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Large-instance conclusion rests on unverified, non-peer-reviewed SBM numbers; constant 10.00 s 'tSBM' entries look like fixed budgets, and the Discussion's 'factor 10000' contradicts its own tables.","rationale":"The reader's weakest assumption is exactly the load-bearing point. The first two datasets are internally consistent: all solvers reach known optima or best-known values, and the QPU shortfall on small instances is credible even if solver parameters are not fully reported. The G-set is where the paper's qualitative conclusions diverge, and there the SBM comparison is entirely outsourced. The constant 10.00 s tSBM entries are a red flag because they look like a fixed stopping budget rather than measured runtimes, so efficiency claims about SBM are not supported by the paper's data. The 'factor 10000' sentence in Section 4.2 is inconsistent with the tables by about two orders of magnitude, which suggests the external numbers were not scrutinized. This is an epistemic concern about the evidence base, not an accusation about author conduct: the SBM results may well be accurate, but the paper has not supplied the verification needed to rely on them for its central claim. The datasets and the small/medium-instance findings remain valuable, and the appropriate verdict is still conditional: the large-instance comparison should not be taken at face value until the SBM results are independently reproduced or explicitly and substantially caveated. No change to the reader's verdict is needed.","tokens_in":17189,"tokens_out":3012,"duration_ms":29936,"concrete_test":"Independently rerun the SBM on the same 69 G-set instances, using either Toshiba's SBM API or an open-source reimplementation of the simulated bifurcation algorithm, with the same per-instance time budgets implied by Tables 3-4 and with wall-clock time and best cut value logged over multiple runs. If the reproduced SBM values match the reported values within 0.1% and the runtimes are genuinely as small as stated, the concern is resolved; if values differ materially on more than a few instances, or if the reported times are actually fixed budgets, the large-instance comparison must be revised. A cheaper ancillary check is to compare the reported SBM values directly against the Medium post [4] and the known best-known G-set values in the literature.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central G-set claim that SBM and SA2 are highly competitive while Hybrid and SA1 are noticeably worse is established only if the SBM column in Tables 3 and 4 is reliable and comparable. The authors did not run SBM; they transcribe values from a non-peer-reviewed Medium post [4]. The tSBM column is nearly constant at 10.00 s for all large instances (e.g., G35-G39, G55-G63, G70, G72, and also G14, G23), which is the signature of a fixed time budget rather than a measured runtime. If [4] reports a stopping limit rather than time-to-solution, the paper's statements about SBM's computational efficiency are unsupported. Moreover, the Discussion states that SA2 takes 'factor 10000' more time than SBM, but Tables 3-4 show SA2/SBM ratios of roughly 60-100 for large instances, an internal inconsistency indicating the external numbers were not carefully checked. Without independent verification of the SBM values and times, the large-instance comparison rests on a single unverified source, so the headline conclusion cannot be taken at face value.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper presents a benchmark of four approximate solvers for the Max-Cut problem on 139 instances drawn from three datasets (be, bqp, and G). The solvers are D-Wave's fast-annealing QPU, D-Wave's Hybrid solver, two variants of a simulated-annealing algorithm (SA1, SA2) from Myklebust, and Toshiba's Simulated Bifurcation Machine (SBM), with the SBM results transcribed from a non-peer-reviewed Medium post. For instances with at most 251 vertices, the paper reports certified global optima obtained with the BiqBin and MADAM exact solvers; for larger instances it uses best-known values from the literature. The main reported findings are that Hybrid, SA1, and SA2 always match the global optimum on the small instances while the QPU does not, and that on the G-set SBM and SA2 deliver the best solution values while Hybrid and SA1 perform noticeably worse. The paper also reports computation times and argues that Hybrid and SBM are fast while SA2 trades time for quality. The underlying datasets are made publicly available.","tokens_in":17491,"tokens_out":5634,"duration_ms":52352,"significance":"If the small-instance results hold, they provide a credible additional negative data point for the fast-annealing D-Wave QPU on Max-Cut, and the open datasets with certified optima are a useful community resource. The comparison on the G-set is potentially important because it suggests that a classical SA tuned for Max-Cut can match or beat a commercial hybrid quantum-classical solver when given enough runtime. However, the large-instance conclusion rests on SBM values and times taken from a Medium post that the authors did not run or independently verify, and several entries have a suspicious constant 10.00 s runtime that looks like a fixed time budget rather than a measured time-to-solution. The paper honestly discloses that [4] is not peer-reviewed, but that disclosure does not cure the reliability problem. With that caveat, the paper's own SA1/SA2/Hybrid comparisons on the G-set are internally consistent and are a valid contribution; the SBM-based efficiency claims are not.","major_comments":[{"comment":"The central large-instance conclusion that 'SBM and SA2 are very competitive' while Hybrid and SA1 are worse depends entirely on the SBM column transcribed from the non-peer-reviewed Medium post [4]. Many tSBM entries are exactly 10.00 s (e.g., G35-G39, G55, G57, G60-G63, G70, G72, and also G14, G23, G53, G54), which strongly suggests that these are fixed time budgets rather than measured computation times. If [4] reports a stopping limit rather than time-to-solution, the paper's claims about SBM's computational efficiency are unsupported. The authors should either run the SBM code (or a comparable simulated-bifurcation implementation) themselves, or clearly label the SBM column as externally reported values and avoid time-based efficiency claims that depend on unknown stopping rules.","section":"Section 4.2, Tables 3-4"},{"comment":"The statement that SA2 takes 'factor 10000' more time than SBM is internally inconsistent with the reported tables. For most G-set instances with tSBM capped at 10.00 s, the ratio tSA2/tSBM is about 60-100 (e.g., G35: 683.91/10.00 ≈ 68, G67: 630.33/10.01 ≈ 63), and a factor of 10000 holds only for a few instances with tSBM ≈ 0.02 s such as G1 and G6. This discrepancy indicates that the externally sourced time data were not checked against the other columns; the text should report actual ratios or remove the factor.","section":"Section 5, Discussion vs. Tables 3-4"},{"comment":"The QPU benchmark is not reproducible as reported. The paper does not give the annealing time, the number of reads, the embedding parameters, or whether any post-processing (e.g., majority vote or multiple restarts) was applied, and no QPU computation times are reported in Table 1 even though computational efficiency is part of the paper's stated objectives. These parameters are essential for interpreting the QPU's solution quality and for comparing it with the other solvers; please add them or state explicitly that they are unavailable.","section":"Section 3 and Section 4.2"}],"minor_comments":[{"comment":"The sentence 'for problem sizes below 500, these are global optima calculated using exact solvers BiqBin and MADAM' is imprecise: the bqp500 instances have n = 501 and are later described as having only best-known values without a certificate of optimality (Section 4.2).","section":"Section 1.1"},{"comment":"The column header 'tSBAM(s)' contains a typo; it should be 'tSBM(s)' to match the rest of the text.","section":"Tables 3 and 4"},{"comment":"The objective values in Table 1 are negative (because the D-Wave input was formulated as a minimization problem), but the text consistently discusses Max-Cut maximization; an explicit note explaining the sign convention would prevent confusion.","section":"Table 1"},{"comment":"The sentence that SA1 'often slightly more than SBM' is not supported by the tables: for the largest G-set instances SA1 times are typically 1.5-3 s while many SBM times are 10.00 s, so SA1 is often faster; please rephrase.","section":"Section 4.2"},{"comment":"The claim that the bold values in Tables 3-4 'are also the best-known solutions so far' is stronger than what the authors can support from the cited literature alone; suggest 'best among the compared solvers' or 'best-known to the authors'.","section":"Section 4.2"}],"recommendation":"major_revision","confidential_remarks":"The small-instance part of the paper is solid and useful, and the open datasets are a positive contribution. The large-instance conclusion is the paper's headline, but it hinges on unverified SBM numbers from a non-peer-reviewed source, and the constant 10.00 s entries raise concrete doubts about the reported times. If the authors cannot independently verify or clearly caveat the SBM column, the G-set conclusions should be substantially weakened or re-scoped to the solvers they actually ran. The 'factor 10000' statement is a tell-tale sign that the external data were not scrutinized."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nWorth a look for two concrete artifacts: a first (to my knowledge) benchmark of D-Wave's fast-annealing QPU on Max-Cut, and a converted, DOI'd dataset of 139 Max-Cut/QUBO instances with certified optima for n ≤ 251. The small-instance results are clean: Hybrid and SA1/SA2 hit every BiqBin-certified optimum, QPU misses many. That part is solid and reproducible.\n\nThe large-instance story has a load-bearing soft spot. The claim that SBM and SA2 are 'very competitive' rests entirely on SBM numbers transcribed from a non-peer-reviewed Medium post, which the authors didn't run. Many tSBM entries are exactly 10.00 s, which looks like a fixed time budget, not a measured runtime. If so, the efficiency comparison for SBM is unsupported. The Discussion's 'factor 10000' time advantage for SBM over SA2 directly contradicts Tables 3 and 4, where the ratios are roughly 60–100 (or much larger on very small times). That is a red flag that the external numbers were not checked. The authors do disclose the source and admit it is not a journal, which is honest, but they still build the headline ranking on it.\n\nThe SA2-vs-Hybrid comparison on the G-set is their own data, and it does support the claim that SA2 beats Hybrid on many instances at much higher time cost. That part stands. The apparent new best for G35 (7686) is a small but real data point.\n\nMinor: QPU and Hybrid parameters (annealing time, number of reads, time limits) are not reported, which makes reproduction harder. The self-citations to BiqBin/MADAM are fine; those solvers produce certificates.\n\nBottom line: the small-instance evidence and dataset are ready; the large-instance conclusions need either independent SBM runs or strong caveats, plus a corrected timing statement. I would send it to review—it deserves referee time—but expect major revision.","headline":"Useful small-instance benchmark and dataset, but the G-set conclusion leans on unverified SBM numbers and a time statement that contradicts the paper's own tables.","tokens_in":17985,"tokens_out":2968,"would_cite":true,"duration_ms":25791,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q12","90C27","90C26","90C59"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper reports that on all small Max-Cut instances with known optima, the D-Wave Hybrid solver and two classical simulated-annealing variants reached the global optimum while the fast-annealing QPU usually fell short, and on the…","keywords":["Max-Cut","QUBO","quantum annealing","simulated annealing","simulated bifurcation machine","D-Wave","global optimum","benchmark"],"falsifier":"If any be or bqp instance is found where the Hybrid solver or either SA variant returns a cut value strictly below the optimum computed by the exact solvers, the paper's claim that these solvers consistently achieve the global optimum is false. For the large-instance ranking, running the simulated bifurcation machine (or an equivalent implementation) on the G-dataset under matched time budgets and hardware, with independently recorded wall-clock times, would confirm or overturn the reported SBM advantage, since the current numbers are taken from the external benchmark.","tokens_in":17038,"feed_emoji":"⚛️","tokens_out":10231,"duration_ms":94120,"temperature":0.7,"pith_summary":"This paper tries to establish where current quantum, hybrid, and classical solvers actually stand on the NP-hard Max-Cut problem, measuring how close each solver gets to known global optima or best-known solutions. The authors benchmark D-Wave's fast-annealing QPU and hybrid cloud solver against two tuned variants of classical simulated annealing and Toshiba's simulated bifurcation machine across 139 instances with 100 to 10,000 nodes. Their central finding is that on small instances the hybrid solver and both classical annealing variants always reached the global optimum while the QPU usually landed far from it, and on large instances the simulated bifurcation machine and the slower annealing variant produced the best solutions, with the hybrid solver and the faster annealing variant noticeably worse. If this is right, the fast-annealing QPU hardware is not competitive for Max-Cut, and a well-tuned classical annealing with enough runtime is the quality leader alongside the simulated bifurcation machine.","feed_headline":"Fast-annealing D-Wave QPU trails classical solvers on Max-Cut","feed_subtitle":"On 139 instances, D-Wave hybrid and slow classical annealing hit known optima; the fast QPU fell short.","key_machinery":"The central object is the Max-Cut objective written as $\\frac{1}{4}x^T L x$ for a cut vector $x\\in\\{\\pm1\\}^n$, with $L$ the graph Laplacian; this is the Ising/QUBO Hamiltonian that all solvers approximately minimize. The benchmark machinery is the three-dataset suite: the be and bqp instances with exact optima computed by two exact solvers, and the G-dataset with best-known values from the literature. The two simulated-annealing variants SA1 and SA2 are the same algorithm with different annealing schedules, so they isolate the effect of search time on solution quality. The D-Wave Hybrid solver is a black-box cloud method that combines classical samplers with the QPU through an undisclosed graph decomposition, while the SBM results are taken directly from an external benchmark rather than run by the authors.","core_discovery":"The central discovery is an empirical ranking of four approximate solvers on the Max-Cut problem. On the be and bqp datasets, where global optima are known for instances up to 251 nodes, the Hybrid solver and both simulated-annealing variants recovered the exact optimum on every instance, while the D-Wave fast-annealing QPU returned the optimum on only one of the fifty small instances and otherwise landed thousands of objective units below it. On the G-dataset of 69 instances with 800 to 10,000 nodes, the paper reports that Toshiba's simulated bifurcation machine and the slower simulated-annealing schedule produced the best cut values, the Hybrid solver was noticeably worse in quality but similar in speed, and the faster annealing schedule was the weakest. The conclusion the authors draw is that the new fast-annealing feature of the QPU does not translate into competitive solution quality for Max-Cut, and the leading solvers in this comparison are classical or classical-hybrid.","pith_inferences":["The paper's negative QPU result is for generic Max-Cut instances; earlier work cited in the paper suggests tunneling-friendly planted problems can favor quantum annealing, so the finding should not be extrapolated to such structures.","A fair time-equality comparison is missing: SA2 runs for roughly 600 to 1000 seconds while SBM is credited with about 10 seconds, so it remains an open question how SA2 would perform if capped at SBM's time budget.","The Hybrid solver's black-box decomposition prevents isolating why it loses quality on large instances; testing it on sparse versus dense subgraphs or varying decomposition parameters would localize the bottleneck."],"forward_implications":["For Max-Cut instances with known optima up to 251 nodes, the D-Wave Hybrid solver and both simulated-annealing schedules are equivalent in solution quality, so any claim of quantum advantage for these cases must beat a classical baseline that never misses the optimum.","The fast-annealing QPU, as configured out of the box, cannot be recommended as a near-optimal solver for Max-Cut: it produced the optimum on only one of the fifty small instances and could not handle instances above 151 nodes.","On large G-instances, solution quality for simulated annealing is bought with runtime: the slow SA2 schedule beats the fast SA1 schedule, so reported runtimes for SA are meaningful only together with the annealing schedule.","The Hybrid solver's overall quality on the G-dataset sits between the fast and slow classical schedules, with speed comparable to the simulated bifurcation machine, making it a fast but not the best-quality option.","SBM and SA2 are the two leading solvers by solution quality on the G-dataset, with SA2 orders of magnitude slower, so the practical choice depends on whether runtime or best cut value matters."],"supporting_citations":[{"why":"Supplies the classical simulated-annealing implementation for Max-Cut from which the authors derive the SA1 and SA2 schedules; its results are the classical baselines.","marker":"[3]"},{"why":"Supplies the Toshiba SBM solution values and computation times for the G-dataset; the paper's claim that SBM is competitive rests entirely on this external source.","marker":"[4]"},{"why":"Exact branch-and-bound solver used to compute global optima for the be and bqp instances up to 251 nodes.","marker":"[5]"},{"why":"Exact solver used together with [5] to verify the reported optima for small instances.","marker":"[6]"},{"why":"Source of the be and bqp benchmark instances, originally formulated as QUBO and reformulated as Max-Cut by the authors.","marker":"[50]"},{"why":"Library reference for the same be and bqp instances used to build the benchmark datasets.","marker":"[51]"},{"why":"Provides the G-dataset graphs generated with the rudy generator, used as the large-instance benchmark.","marker":"[52]"}],"fun_headline_variants":["D-Wave fast anneal beaten by simulated annealing on Max-Cut","Quantum solver falls short: classical and hybrid win on Max-Cut","Max-Cut benchmark: D-Wave QPU trails SBM and slow SA"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The large-instance conclusion that the simulated bifurcation machine matches the slower classical annealing depends on SBM solution values and runtimes taken from an external, non-peer-reviewed benchmark that the authors did not run, verify, or compare on equal hardware; if those numbers are inaccurate or not comparable, the G-dataset ranking is not established.","fun_headline_variants_meta":{"raw":{"variants":["D-Wave fast anneal beaten by simulated annealing on Max-Cut","Quantum solver falls short: classical and hybrid win on Max-Cut","Max-Cut benchmark: D-Wave QPU trails SBM and slow SA"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000306,"raw_usage":{"total_tokens":1774,"prompt_tokens":989,"completion_tokens":785,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":605,"completion_tokens_details":{"reasoning_tokens":722}},"tokens_in":605,"tokens_out":785,"duration_ms":7660,"temperature":1.0,"reasoning_tokens":722,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T18:49:32.207735+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"If any be or bqp instance is found where the Hybrid solver or either SA variant returns a cut value strictly below the optimum computed by the exact solvers, the paper's claim that these solvers consistently achieve the global optimum is false. For the large-instance ranking, running the simulated bifurcation machine (or an equivalent implementation) on the G-dataset under matched time budgets and hardware, with independently recorded wall-clock times, would confirm or overturn the reported SBM advantage, since the current numbers are taken from the external benchmark.","supporting_citations":[{"cited_title":"Solving maximum cut problems by simulated annealing","cited_arxiv_id":"1505.03068","evidence_quote":"Supplies the classical simulated-annealing implementation for Max-Cut from which the authors derive the SA1 and SA2 schedules; its results are the classical baselines."},{"cited_title":"Benchmarking the MAX-CUT problem on the Simulated Bifurcation Machine","cited_arxiv_id":null,"evidence_quote":"Supplies the Toshiba SBM solution values and computation times for the G-dataset; the paper's claim that SBM is competitive rests entirely on this external source."},{"cited_title":"BiqBin: a parallel branch-and-bound solver for binary quadratic problems with linear constraints","cited_arxiv_id":null,"evidence_quote":"Exact branch-and-bound solver used to compute global optima for the be and bqp instances up to 251 nodes."},{"cited_title":"MADAM: a parallel exact solver for max-cut based on semidefinite programming and ADMM","cited_arxiv_id":null,"evidence_quote":"Exact solver used together with [5] to verify the reported optima for small instances."},{"cited_title":"Biq Mac Library – A collection of Max-Cut and quadratic 0-1 programming instances of medium size","cited_arxiv_id":null,"evidence_quote":"Source of the be and bqp benchmark instances, originally formulated as QUBO and reformulated as Max-Cut by the authors."},{"cited_title":"BiqMac Library","cited_arxiv_id":null,"evidence_quote":"Library reference for the same be and bqp instances used to build the benchmark datasets."},{"cited_title":"A spectral bundle method for semidefinite programming","cited_arxiv_id":null,"evidence_quote":"Provides the G-dataset graphs generated with the rudy generator, used as the large-instance benchmark."}],"review_version":1}