{"id":"27c76e7c-0a3c-49b8-b075-1d9f9df41653","arxiv_id":"2502.06542","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"A family of QUBO Hamiltonians for binary clustering that encodes cluster centroids via cluster-size variables, enabling combined intracluster, intercluster, and constrained objectives.","lead":"This paper rewrites centroid-based clustering as an energy-minimization problem that quantum computers can solve. The authors encode cluster centers directly into the objective and show a specific formulation runs stably on D-Wave quantum annealing hardware.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The reported Intra* vs weighted MaxCut results contradict their proven equivalence, so the experimental pipeline behind the headline D-Wave claim is unverified.","rationale":"The paper's central mathematical contribution is a family of QUBO Hamiltonians for centroid-based clustering, including the combined intra/intercluster objective that simplifies to Eq. (13) and the pairwise Hamiltonian Eq. (A27). I verified the key algebraic identity in Appendix A.3: the bracket in Eq. (A22) equals -N/(N_+^2 N_-^2) L^2 with L = N_- sum_+ x - N_+ sum_- x = N_+ N_- (mu_+ - mu_-), so Eq. (12) equals -N N_+^2 N_-^2 ||mu_+ - mu_-||^2. The subsequent simplification to a quadratic form in Eq. (A26)/(A27) is also algebraically consistent, because L is linear in z. Thus the reduction is not an approximation and does preserve minimizers. The theoretical framework is internally coherent. The load-bearing weakness is empirical: the paper claims Intra* and weighted MaxCut are part of a single framework, and the math shows they are the same optimization problem up to scaling, yet the experiments report different outcomes. This is not merely a missing detail; it indicates that the experimental implementation or reporting is unreliable. Without code or data, a reader cannot tell which results are correct. The D-Wave result for the combined Hamiltonian, including the zero-chain-break claim, is produced by the same pipeline and therefore inherits this uncertainty. The outlier-driven clustering concern raised by the reader is a legitimate limitation of the objective, but it is a property of the formulation rather than a contradiction; the Intra*/MaxCut discrepancy is a concrete inconsistency in the evidence for the central claim. I recommend keeping the verdict at CONDITIONAL, because the mathematical core is defensible but the experimental verification must be clarified or corrected before the practical quantum-annealing claim is fully supported.","tokens_in":22918,"tokens_out":17076,"duration_ms":141945,"concrete_test":"Implement Eqs. (A16)/(A17) and the weighted MaxCut QUBO with a_ij = ||x_i - x_j||^2 on the same fixed Iris and Wine samples (same 150 random 16-point subsets for exact search, same full datasets for simulated annealing), using identical brute-force and annealing schedules, and verify that the ground-state assignments and RI/SS values are identical for both formulations. If they differ, the published experimental results contain an implementation or reporting error that must be resolved before the D-Wave performance claims can be accepted.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section III.A and Appendix A.1 show that Intra* (Eq. A16/A17) reduces exactly to sum_{i<j} 1/2 ||x_i - x_j||^2 z_i z_j, while weighted MaxCut (Section III) minimizes sum_{i<j} ||x_i - x_j||^2 z_i z_j. These objectives differ only by a positive scalar 1/2, so any exact optimizer must return identical ground-state assignments and therefore identical Rand Index and Silhouette Score. Yet Table II reports exact-search RI 0.858 for Intra* versus 0.847 for weighted MaxCut on Iris, and Table III reports simulated-annealing RI 0.939 versus 0.922 on Iris. This inconsistency is impossible under correct implementation unless the methods were evaluated on different random subsamples or the objective implementations differ from the published equations. The paper does not disclose code, data, or random-seed controls, and it does not discuss this discrepancy. Since the same experimental pipeline also produced the central D-Wave results (zero chain breaks, RI at or above k-means), the reliability of the headline empirical claim is called into question. The algebraic derivations appear sound, but the experimental support is not internally consistent as reported.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript proposes a unified QUBO/Ising Hamiltonian framework for binary centroid-based clustering. It introduces distance functions for intracluster and intercluster objectives, constructs optimization problems for intra-only, inter-only, and combined cases, and derives explicit Pauli--Z Hamiltonians in Appendix A. The combined objective is shown to reduce to maximizing a weighted squared distance between cluster centroids. The authors also add penalty-term constructions for must-link, cannot-link, labeling, and cardinality constraints, and present a recursive algorithm for k-clustering. Experiments use exact enumeration, simulated annealing, and the D-Wave Advantage 6.4 quantum annealer on Iris, Wine, a synthetic overlapping Gaussian dataset, and a 0/1 MNIST subset, with claims of zero chain breaks for the intra-inter combined Hamiltonian.","tokens_in":23103,"tokens_out":13506,"duration_ms":111873,"significance":"The algebraic part of this work is useful: Appendix A provides explicit reductions of centroid-based objectives to Ising Hamiltonians, including the nontrivial simplification of the combined intra-inter objective to a pairwise Hamiltonian, and the derivation appears internally consistent. The constrained-clustering extensions are also valuable because they show how practical requirements can be folded into the same Hamiltonian framework. If the experiments were internally consistent, the zero-chain-break observation on a current quantum annealer would be a genuinely interesting data point for the quantum-annealing clustering community. However, the reported experimental tables contain a direct contradiction with the paper's own algebra, and this undermines the reliability of the empirical pipeline, including the D-Wave results, until it is resolved.","major_comments":[{"comment":"Equation (A16) and the resulting Hamiltonian (A17) show that the objective labeled Intra* is exactly (1/2) sum_{i<j} ||x_i - x_j||^2 z_i z_j. This is a positive scalar multiple of the weighted MaxCut objective defined in Section III with a_ij = ||x_i - x_j||^2. Positive scaling preserves the full set of energy orderings and minimizers, so any optimizer of one objective is an optimizer of the other. Yet Table II reports exact-search Rand Index 0.858 for Intra* versus 0.847 for weighted MaxCut on Iris, with Silhouette Scores 0.422 versus 0.418, and Table III reports simulated-annealing Rand Index 0.939 versus 0.922. These differences are impossible as reported unless the two methods were evaluated on different random subsamples, implemented different objective functions, or used undocumented tie-breaking among degenerate ground states. The authors must reconcile this discrepancy, because the same experimental pipeline produced the central D-Wave claims.","section":"Section III and Appendix A.1, vs. Tables II and III"},{"comment":"The conclusion that 'at least one of our proposed Hamiltonians outperforms the weighted MaxCut' is not supported for Intra*, since Intra* is merely a positively scaled version of weighted MaxCut. Any apparent advantage of Intra* over weighted MaxCut in Figures 2 and 3 must therefore be an artifact of tie-breaking, sampling, or implementation details rather than evidence that centroid information improves clustering. The authors should remove or reinterpret this comparison after correcting the experimental pipeline.","section":"Section V and Figures 2-3"},{"comment":"The central quantum-annealing claim is that the Intra-Inter combined Hamiltonian achieves zero chain breaks while Intra, Intra*, and weighted MaxCut produce near-random solutions on the same complete-graph problems. This is surprising because Intra* and weighted MaxCut are mathematically identical problems, and the combined Hamiltonian is also a pairwise Hamiltonian on the same complete graph. The paper does not report the chain strengths used, the embedding parameters returned by the clique sampler, the post-processing rule for broken chains, or the precise sampling protocol. Without these details, the qualitative difference in chain-break behavior cannot be reproduced or assessed; please provide these parameters and, ideally, the raw solver configuration for each Hamiltonian.","section":"Section IV.C, Table IV, and Figure 5"}],"minor_comments":[{"comment":"Equation (A23) contains a typographical artifact in the factor written as '2N+1N-1'; this should read '2 N_+ N_-'.","section":"Appendix A.3, Eq. (A23)"},{"comment":"Several rows in Table IV report zero standard deviation for the Intra-Inter combined method; please state explicitly whether these are single-run values or averages over multiple runs, and how many quantum annealing repetitions were used for each entry.","section":"Appendix B, Table IV"},{"comment":"The constrained-clustering experiments depend on the penalty hyperparameter lambda_p, but the paper does not report the values used for Figures 6 and 7. Since the Inter method's variability is attributed to sensitivity to lambda_p, reporting the chosen values is necessary for reproducibility.","section":"Section IV.D"},{"comment":"No code or data repository is provided. Given the role of random subsampling, tie-breaking, and hyperparameters in the reported results, a public artifact would materially strengthen the paper's reproducibility.","section":"General"}],"recommendation":"major_revision","confidential_remarks":"The algebraic contribution is sound and the paper is worth a revision rather than rejection. The Intra*/weighted MaxCut contradictions in Tables II and III are the key problem; they need a genuine reconciliation, not just a textual clarification. If the authors re-run the experiments and the equivalent objectives still yield different results, that would point to an implementation error that also affects the D-Wave pipeline. I would therefore not accept the manuscript until the experimental tables are corrected and the hardware parameters are fully reported."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's the take. Seong and Park give a clean QUBO formulation trick: introduce N_+ and N_- as derived variables, multiply distance functions by powers of N to clear denominators, and get pairwise Hamiltonians for intracluster, intercluster, and combined objectives. The combined objective in Eq. (12) reduces to maximizing weighted squared centroid distance (Eq. 13), which is neat and not in prior work. The algebra in Appendix A checks out as far as I can see. The D-Wave result, zero chain breaks for the combined Hamiltonian, is interesting if true.\n\nBut there is a real problem. Appendix A.1 shows Intra* is exactly 1/2 times the weighted MaxCut objective (Eq. A16/A17 vs Eq. 4). So their ground states are identical. Yet Table II reports exact-search RI 0.858 for Intra* and 0.847 for weighted MaxCut on Iris. That cannot happen if both were exactly optimized on the same data. Table III shows a similar discrepancy under simulated annealing. Since the paper does not ship code, data, or seeds, I cannot tell whether the methods ran on different subsamples or the implementations diverge from the published Hamiltonians. Either way the experimental layer is not internally consistent, and this is the same pipeline that produced the headline D-Wave claim. The stress-test note is right to call this out.\n\nMinor issues: the \"path to quantum advantage\" framing is overstated for experiments with fewer than 200 points and marginal RI gains, and the k-clustering algorithm is from Ref. [35], which the authors acknowledge. There are also no pathological examples like singleton clusters.\n\nWho is this for? People building QUBO formulations for clustering and benchmarking quantum annealers. They will find the N_+ N_- scaling trick and the combined objective worth citing. But they should not rely on the performance tables until the contradiction is explained.\n\nRecommendation: send it to serious peer review. The theoretical contribution is coherent and original enough to deserve referee time, but I would make a corrected and fully specified experimental report a condition of acceptance.","headline":"Clean QUBO trick and a neat combined objective, but the reported Intra* vs weighted MaxCut results contradict their proved equivalence, so the experiments need correction before the empirical claims can be trusted.","tokens_in":23630,"tokens_out":2056,"would_cite":true,"duration_ms":30581,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Centroid-based clustering can be written as a spin-Hamiltonian ground-state search, and the combined intracluster/intercluster objective turns out to be equivalent to maximizing the size-weighted squared centroid distance.","keywords":["Hamiltonian clustering","centroid-based clustering","QUBO","quantum annealing","k-means","intracluster distance","intercluster distance","constrained clustering"],"falsifier":"Take a data set of two compact, well-separated Gaussian clusters plus one distant outlier, and compute the exact ground state of the pairwise Hamiltonian in Eq. (A27) by brute force. If the minimizing assignment puts the outlier alone in one cluster, a near-singleton, while standard k-means assigns it to the nearest cluster, then the claimed equivalence between centroid-based clustering and the size-weighted centroid-separation objective fails on skewed data.","tokens_in":22706,"feed_emoji":"⚛️","tokens_out":6647,"duration_ms":63579,"temperature":0.7,"pith_summary":"This paper tries to show that centroid-based clustering—grouping points around their means—can be reformulated as finding the ground state of a spin Hamiltonian, so that quantum computers and annealers can solve it. The central move is to treat the number of points in each cluster, which normally appears as an awkward denominator in centroid formulas, as variables inside the objective and then multiply them away, converting rational objective functions into quadratic binary Hamiltonians. The strongest result is for the objective that combines intracluster tightness with intercluster separation: the paper proves this combined objective is equivalent to maximizing the cluster-size-weighted squared distance between the two centroids, and the resulting pairwise Hamiltonian ran on D-Wave Advantage with zero chain breaks, achieving Rand Index values at or above k-means on Gaussian, Iris, Wine, and 0-1 MNIST data. The wider claim is that this gives a flexible unified framework for clustering—combining multiple objectives and constraints such as must-link/cannot-link and cardinality—that is compatible with both gate-based quantum algorithms and quantum annealing.","feed_headline":"Clustering objective runs on D-Wave with zero chain breaks","feed_subtitle":"Combined intra-plus-intercluster distance becomes a pairwise Hamiltonian that beats k-means on four benchmarks.","key_machinery":"The central object is the size-weighted centroid-separation identity, Eq. (12) = Eq. (13): the combined intracluster/intercluster objective equals $-N N_+^2 N_-^2 \\|\\mu_+-\\mu_-\\|_2^2$. The machinery that carries the argument is the substitution of the cluster-size variables $N_\\pm = \\sum_i (1\\pm z_i)/2$ and centroid formulas into the distance function $l(\\mu,z,s)$, followed by multiplication by $N_+^2 N_-^2$ to clear denominators. For the combined objective, every denominator cancels and all higher-order terms telescope, leaving only quadratic terms $Z_i Z_j$; this is the property that makes the Hamiltonian embeddable on the D-Wave clique sampler, a complete graph of up to 175 logical qubits, without slack variables. The same machinery produces the intra-only quadratic variant and the inter-only variant, which contains higher-order terms and requires slack variables, making it less hardware-friendly.","core_discovery":"On the paper's own terms, the discovery is that the combined intracluster/intercluster objective is not just a compromise but collapses exactly: minimizing Eq. (12) is equivalent to minimizing $-N N_+^2 N_-^2 \\|\\mu_+ - \\mu_-\\|_2^2$, i.e., maximizing the squared distance between the two cluster centroids weighted by the sizes of both clusters. Because the denominators $N_\\pm$ are canceled by multiplying the combined objective by $N_+^2 N_-^2$, the resulting expression is quadratic in the binary cluster-assignment variables and can be written as a pairwise spin Hamiltonian, Eq. (A27), with no higher-order terms. This pairwise form is what makes the combined objective embeddable on D-Wave Advantage's Pegasus topology with zero chain breaks, while the other tested Hamiltonians—intra, intra*, and weighted max-cut—suffered chain breaks that destroyed solution quality. Empirically, the combined Hamiltonian produced Rand Index values higher than or equal to k-means on all four benchmark datasets while keeping comparable Silhouette Scores.","pith_inferences":["Not tested in the paper: on skewed data with a distant outlier, the size-weighted centroid-separation objective may favor isolating the outlier as a singleton cluster, because that maximizes $\\|\\mu_+-\\mu_-\\|^2$; this would be a failure mode for imbalanced real-world data.","The zero-chain-break finding may reflect the combined Hamiltonian's simple quadratic connectivity rather than a special property of clustering objectives; comparing it against a random quadratic Hamiltonian on the same graph would separate hardware embedding effects from clustering content.","The constrained-clustering curves show an initial drop in Rand Index when 10–30 percent of labels are revealed; a systematic sweep of the penalty weight $\\lambda_p$ could determine whether that drop is an artifact of penalty calibration rather than a property of the objective.","A natural next step, consistent with the paper's own future-work list, is to use the centroid-separation value itself as a stopping criterion in the hierarchical splitting algorithm, thereby choosing $k$ from data instead of fixing it in advance."],"forward_implications":["The combined objective's ground state is exactly a maximum of the size-weighted squared centroid distance, so tuning this objective means tuning a single interpretable quantity rather than two competing distance sums.","Because the combined Hamiltonian is purely quadratic, it can be targeted not only by quantum annealing but also by QAOA, VQE, or any quantum ground-state technique that handles Ising models, without extra slack qubits.","Constraints such as labeling, cardinality, and must-link/cannot-link can be appended as linear or quadratic penalty terms to the same objective, letting users enforce domain knowledge within a single QUBO.","The hierarchical k-clustering algorithm extends the binary Hamiltonian to $k > 2$ clusters by repeated binary splits, avoiding one-hot encodings and exclusivity penalties.","The intercluster-only objective requires higher-order terms and slack variables, so among the proposed Hamiltonians the combined form is the one best matched to current annealer hardware."],"supporting_citations":[{"why":"Supplies the standard mapping from combinatorial optimization problems to Ising spin Hamiltonians, which the whole formulation relies on.","marker":"[15]"},{"why":"Defines the Silhouette Score used to compare clustering quality with k-means.","marker":"[27]"},{"why":"Defines the Rand Index, the main accuracy metric on which the combined Hamiltonian matches or beats k-means.","marker":"[28]"},{"why":"Provides the scikit-learn k-means implementation used as the classical baseline throughout the experiments.","marker":"[29]"},{"why":"Documents the D-Wave Advantage System 6.4 qubit count and Pegasus topology used in the quantum annealing runs.","marker":"[30]"},{"why":"An earlier centroid-in-QUBO formulation restricted to equal cluster sizes; the paper removes that assumption by making cluster sizes objective variables.","marker":"[32]"},{"why":"The iterative fractional-cost QUBO approach for uneven data distributions, the prior alternative the paper compares against.","marker":"[34]"},{"why":"Earlier quantum clustering work that introduced the hierarchical splitting idea and is the basis for the Hamiltonian k-clustering algorithm.","marker":"[35]"},{"why":"Supplies the Must-Link/Cannot-Link penalty term used for the constrained clustering experiments.","marker":"[38]"},{"why":"Provides the clique embedding routine used to map the fully connected clustering graph onto D-Wave's hardware.","marker":"[41]"}],"fun_headline_variants":["Clustering as Hamiltonian: zero chain breaks on D-Wave","Pairwise spin Hamiltonian beats k-means on D-Wave","Quantum clustering: combined objective avoids chain breaks","Zero chain breaks: clustering Hamiltonian outperforms k-means","Centroid clustering via Hamiltonians: D-Wave zero chain breaks"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole approach rests on the assumption that maximizing the cluster-size-weighted squared distance between the two centroids is a sensible clustering objective on real data, and that the algebraic clearing of denominators in Appendix A.3 preserves exactly which assignments are optimal; the paper tests this on only four small benchmark sets and does not analyze pathological cases such as singleton clusters.","fun_headline_variants_meta":{"raw":{"variants":["Clustering as Hamiltonian: zero chain breaks on D-Wave","Pairwise spin Hamiltonian beats k-means on D-Wave","Quantum clustering: combined objective avoids chain breaks","Zero chain breaks: clustering Hamiltonian outperforms k-means","Centroid clustering via Hamiltonians: D-Wave zero chain breaks"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000782,"raw_usage":{"total_tokens":3493,"prompt_tokens":1027,"completion_tokens":2466,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":643,"completion_tokens_details":{"reasoning_tokens":2384}},"tokens_in":643,"tokens_out":2466,"duration_ms":15545,"temperature":1.0,"reasoning_tokens":2384,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T15:08:44.436204+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a data set of two compact, well-separated Gaussian clusters plus one distant outlier, and compute the exact ground state of the pairwise Hamiltonian in Eq. (A27) by brute force. If the minimizing assignment puts the outlier alone in one cluster, a near-singleton, while standard k-means assigns it to the nearest cluster, then the claimed equivalence between centroid-based clustering and the size-weighted centroid-separation objective fails on skewed data.","supporting_citations":[{"cited_title":"A comprehensive survey of clustering algorithms: State-of-the-art machine learning applications, tax- onomy, challenges, and future research prospects","cited_arxiv_id":null,"evidence_quote":"Supplies the standard mapping from combinatorial optimization problems to Ising spin Hamiltonians, which the whole formulation relies on."},{"cited_title":"Effi- cient combinatorial optimization by quantum-inspired parallel annealing in analogue memristor crossbar","cited_arxiv_id":null,"evidence_quote":"Defines the Silhouette Score used to compare clustering quality with k-means."},{"cited_title":"Silhouettes: a graphical aid to the interpreta- tion and validation of cluster analysis.Journal of Computational and Applied Mathematics, 20:53–65, 1987","cited_arxiv_id":null,"evidence_quote":"Defines the Rand Index, the main accuracy metric on which the combined Hamiltonian matches or beats k-means."},{"cited_title":"Objective criteria for the evaluation of clus- tering methods","cited_arxiv_id":null,"evidence_quote":"Provides the scikit-learn k-means implementation used as the classical baseline throughout the experiments."},{"cited_title":"Scikit- learn: Machine learning in python","cited_arxiv_id":null,"evidence_quote":"Documents the D-Wave Advantage System 6.4 qubit count and Pegasus topology used in the quantum annealing runs."},{"cited_title":"Ising models for binary clustering via adiabatic quantum computing","cited_arxiv_id":null,"evidence_quote":"An earlier centroid-in-QUBO formulation restricted to equal cluster sizes; the paper removes that assumption by making cluster sizes objective variables."},{"cited_title":"A qubo formulation of the k-medoids prob- lem","cited_arxiv_id":null,"evidence_quote":"The iterative fractional-cost QUBO approach for uneven data distributions, the prior alternative the paper compares against."},{"cited_title":"Distance-based clustering using qubo formula- tions","cited_arxiv_id":null,"evidence_quote":"Earlier quantum clustering work that introduced the hierarchical splitting idea and is the basis for the Hamiltonian k-clustering algorithm."},{"cited_title":"Constrained clustering: Current and new trends","cited_arxiv_id":null,"evidence_quote":"Supplies the Must-Link/Cannot-Link penalty term used for the constrained clustering experiments."},{"cited_title":"Practi- cal bayesian optimization of machine learning algorithms","cited_arxiv_id":null,"evidence_quote":"Provides the clique embedding routine used to map the fully connected clustering graph onto D-Wave's hardware."}],"review_version":1}