REVIEW 4 major objections 4 minor 31 references
Quantum Annealing for Machine Learning: Applications in Feature Selection, Instance Selection, and Clustering
T0 review · 4 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash
Pith's one-line read This paper aims to show that quantum annealing can solve discrete machine-learning optimization problems—feature selection, instance selection, and clustering—competitively with classical simulated annealing, at about a tenth of the…
desk verdict Honest working-notes paper with two genuinely new heuristics; the QA-efficiency claim rests on an unvalidated timing comparison and the abstract overstates the clustering results. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the QUBO objective $f(x) = x^T Q x$, a quadratic function over binary variables that quantum annealers accept natively; every task in the paper is reduced to choosing the matrix $Q$ so that the minimum of $f$ encodes the desired subset or medoid selection. Feature selection puts importance scores on the diagonal and redundancy scores off the diagonal, with a penalty enforcing the number of selected features. Instance selection uses cosine similarities between embeddings off the diagonal and the paper's new SVC-distance or deletion-influence scores on the diagonal. Clustering uses the k-medoids QUBO objective, with pairwise distances converted by the Welsch M-estimator (a correntropy loss) and with the exact-k constraint generated through a dedicated quadratic constraint generator rather than a plain penalty; the quantum stage only refines medoids proposed by a classical clustering stage.
What would settle it
Run the same MQ2007 feature-selection QUBO many times on QA and SA with identical reads, and time the full pipeline from submission to returned samples; if QA's median time is not roughly one-tenth of SA's, or if the 13-feature outcome falls inside the run-to-run variance of the 15-feature outcome, the efficiency and competitiveness claim loses its support.
Extended reading notes
Core claim
On its own terms, the paper's central discovery is that a QUBO formulation of each task lets quantum annealing reach essentially the same solution quality as simulated annealing with far less compute. For feature selection on the MQ2007 collection, QA achieved a leaderboard nDCG@10 of 0.4552 with only 13 selected features, close to the top score of 0.4580 at 21 features, and did so in roughly one-tenth of the annealing time of SA. In instance selection, the paper extends the bcos QUBO with two new diagonal importance heuristics—distance to an SVM margin and an instance-deletion influence score—but finds no statistically significant difference among methods at 25% reduction on the provided datasets, which it argues are too easy. In clustering, the pipeline runs classical k-Medoids, HDBSCAN, or GMM to produce candidate medoids, then applies a fixed-k QUBO medoid refinement; the best submitted run outperformed the reported baselines, and the authors report consistent improvements in compactness and retrieval metrics.
Load-bearing premise
The central claims assume the timing comparison is apples-to-apples—same QUBO instance, same number of reads, and QA time reflecting solver time rather than queue or embedding overhead—and that the 13-feature QA result is a representative outcome rather than a lucky draw from a high-variance process.
Editorial extensions
If this is right
- Feature-selection QUBOs of the size tested here (tens of features) can be solved by QA with quality on par with SA at about a tenth of the annealing time, so time-sensitive ML pipelines could offload this step to an annealer.
- Very small feature subsets can carry most of the ranking signal: the 13-feature QA selection nearly matched a 21-feature leaderboard leader, so learned feature budgets may be tighter than commonly assumed.
- A hybrid classical-quantum clustering pipeline—classical candidates, quantum-constrained medoid refinement—can enforce exact k while improving compactness and retrieval metrics, pointing to refinement rather than full-problem solving as the practical role of current annealers.
- In instance selection, QUBO-based heuristics and random sampling are statistically indistinguishable on the provided sentiment datasets at 25% reduction, implying that harder benchmarks are needed before QA-based instance selection can show a measurable benefit.
- Fixed-k constraints encoded as quadratic penalty terms through a dedicated constraint generator are more stable on quantum hardware than simple linear or diagonal penalties, which matters for any QUBO task requiring exact cardinality.
Reading between the lines
- The reported 10x speedup is for annealing time, not end-to-end pipeline time; a full workflow benchmark that includes QUBO construction, embedding, and queue time would likely soften the advantage, so the competitive-efficiency claim should be read as solver-level, not system-level.
- The two identical QA feature-selection submissions returning 13 and 15 features suggest high run-to-run variance; leaderboard comparisons built on a single QA draw may overstate the method's typical performance, and repeated sampling would give a fairer estimate.
- The clustering pipeline's benefit probably depends on the upstream classical clustering quality: quantum refinement adds the most when classical candidates are noisy or overlapping, and could be neutral when classical clusters are already clean; this dependency is testable by ablating the refinement step.
- The instance-selection diagonal heuristics are computed per 80-document batch, so a natural next test is computing the importance scores globally before batching; the paper's own batching discussion implies this could remove a known inconsistency.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper reports a QuantumCLEF 2025 competition entry in which three machine-learning tasks—feature selection, instance selection, and clustering—are formulated as QUBO problems and solved with both D-Wave quantum annealing (QA) and simulated annealing (SA). For feature selection, the authors construct QUBO matrices from mutual-information- and permutation-importance-based terms, report leaderboard nDCG scores for two QA runs (0.4552 with 13 features and 0.4436 with 15 features), and claim that QA is about ten times faster than SA. For instance selection, they extend the bcos QUBO approach with SVC-margin and instance-deletion diagonal heuristics, reporting F1 scores at 25% reduction. For clustering, they build a classical-to-quantum pipeline that pre-clusters documents and then uses a constrained QUBO medoid-refinement stage; their k-Medoids submission achieved a leaderboard nDCG of 0.58. The overall conclusion is that QA can be a competitive and efficient tool for discrete ML optimization on current hardware.
Significance. If the efficiency and competitiveness claims were fully substantiated, the paper would provide useful evidence that quantum annealing can serve as a practical heuristic for small-scale discrete optimization problems and as a component in hybrid classical-quantum ML pipelines. The paper has notable strengths: all code is made publicly available through three GitHub repositories; the QUBO formulations are grounded in prior work rather than invented ad hoc; and the authors are unusually candid about limitations, including the lack of statistical significance in Task 2, the all-teams-below-baseline result on the Vader dataset, and the invalid clustering submissions caused by a dimensionality mismatch. These strengths make the manuscript a useful working-notes record. However, the headline claims go beyond what the reported evidence supports, mainly because the timing comparison in Task 1 lacks methodology, the QA feature-selection advantage rests on two unreplicated runs, and the clustering improvements are not shown to come from the quantum refinement stage.
major comments (4)
- [Section 4.1, Figure 2(b) and Table 2] The claim that QA is 'computationally more efficient' rests on an unvalidated timing comparison. Figure 2(b) reports annealing time in milliseconds, but the paper never states whether the QA figure is QPU anneal time, access time, or submission-to-result wall time, nor whether the SA figure is wall-clock or CPU time for the same QUBO instance and the same number of reads. On D-Wave hardware, anneal time per read is on the order of microseconds, while queue, embedding, programming, and readout overhead are typically excluded; comparing only that component to a full SA runtime can produce a large speedup that has nothing to do with algorithmic advantage. The authors should specify exactly what was measured for both solvers, confirm that the comparison used the same QUBO and read count, and report variance over repeated runs. Without this, the central efficiency claim is not supported as reported.
- [Section 4.1, Table 2] The two QA feature-selection submissions had identical code and QUBO configuration but returned different feature counts, k=13 and k=15, with leaderboard nDCG scores of 0.4552 and 0.4436. The paper attributes the divergence to 'inherent randomness and probabilistic nature' but provides no repeated trials, no mean/standard deviation, and no significance analysis. The better score may therefore be a favorable draw from a high-variance process rather than a systematic QA advantage. At minimum, the authors should report multiple QA runs for the same configuration and compare the distribution of solution quality and runtime against SA; otherwise the statement that QA achieved 'comparable effectiveness' with fewer features is not established.
- [Section 4.2, Table 3] The Task 2 results do not support any claim of QA or SA advantage. The paper's own text states that differences are not statistically significant for the Yelp dataset and that all teams perform worse than the baseline on the Vader dataset. The submitted QA run on Vader, for example, has F1 62.6(7.5) versus the baseline 88.9(0.8). The conclusion that 'QA often matched or exceeded the performance of SA in less time' therefore cannot be justified by the instance-selection experiments. The authors should either restrict their claims to feature selection and clustering or provide additional evidence, such as significance testing or a more difficult benchmark, before generalizing beyond Task 1.
- [Section 4.3, Table 4] The abstract claims 'consistent improvements in cluster compactness and retrieval metrics' from the classical-to-quantum medoid-refinement pipeline, but Table 4 does not demonstrate consistency. For example, at k=10 the internal nDCG values range from 0.32 to 0.60 across configurations, with several runs (e.g., Runs 5, 6, 14, 15) far below the corresponding baselines. Moreover, the two submitted UMAP-based clustering runs (Experiments 2 and 12) were invalid because dimensionality-reduced centroids were evaluated against full-dimensional queries, so only one of three official clustering submissions was valid. The table also lacks an ablation that compares the same classical clustering method with and without the quantum refinement stage, so any DBI improvement cannot be attributed to the QUBO refinement rather than to the choice of classical clustering algorithm. The authors should provide a direct before/after comparison and clarify which configurations actually support the consistency claim.
minor comments (4)
- [Section 3.4, Equations (2)-(5)] The equation numbering in Section 3.4 is inconsistent: the text refers to 'Eq. (2)', 'Eq. (3)', and 'Eq. (5)' when the displayed equations are numbered (4) and (5), and the earlier general QUBO is Eq. (1). Please renumber or re-reference the equations so that the medoid objective, the Welsch similarity, and the parameter choices (alpha, beta, gamma) are clearly tied to the correct displayed formulas.
- [Table 1 and Table 2] The tables would be easier to interpret if the number of runs and variance were reported. In particular, Table 2 lists only two QA runs with no repeated trials, and Table 1 mixes local validation scores with leaderboard scores in the same cells using parentheses; a clearer separation (e.g., two columns) would avoid ambiguity.
- [Section 4.2, text after Figure 3] There are several typos and awkward phrasings, including 'Another argument that supports this insight can is illustrated' and 'statisticaly' in the conclusion. These should be corrected in a final revision.
- [References and notation] Some reference markers are inconsistently formatted, such as '[ch. 31][15]' in Section 3.3, and the citation style for the D-Wave Ocean SDK and dimod constraint generator could be made more uniform. Also, the term 'centroid embeddings' in the abstract is used interchangeably with 'medoids' in the body; please define the relationship clearly.
Circularity Check
No significant circularity found: all central evaluations use external metrics, and no load-bearing step reduces to a fitted parameter or a self-citation.
full rationale
After walking the paper's claimed derivation chain, I find no step in which an output is equivalent to an input by construction, no fitted quantity is renamed as a prediction, and no load-bearing argument rests on a self-citation. The feature-selection QUBOs (Section 3.2) are built explicitly from MI/CMI/PFI/CPFI measures with a quadratic cardinality penalty, and the reported nDCG scores come from the qCLEF leaderboard, which is external to the Q-matrix construction and to the validation-based tuning of k. The instance-selection heuristics (Section 3.3) are evaluated by downstream F1 on held-out folds, and the paper explicitly reports that differences are not statistically significant, so no result is forced by construction. The clustering pipeline (Section 3.4) uses the k-medoids QUBO from Bauckhage et al. with a fixed-size constraint generated by dimod; the reported DBI and nDCG are computed on the original embedding space after reassignment, not on the optimized QUBO objective itself, so the claimed improvements are empirical rather than definitional. The only notable weakness is the timing comparison in Section 4.1 and Figure 2, where no timing methodology is given; that is an evidence-quality or correctness concern, not circularity. There are no author-overlapping self-citations and no imported uniqueness theorem that forbids alternatives. The paper's central claims are therefore self-contained against external benchmarks.
Assumptions & free parameters
free parameters (7)
- feature count k (Task 1) =
5 to 40; selected values 13, 15, 20, 25, etc.
- cluster count k (Task 3) =
10, 25, 50
- QUBO penalty weight lambda (Task 1) =
not reported
- alpha, beta, gamma (Task 3) =
alpha=1/k, beta=1/n, gamma=2
- fixed-k penalty scale multiplier (Task 3) =
2x maximum energy delta
- SVC hyperparameters (Task 2) =
rbf kernel, C=1.0
- UMAP reduction settings (Task 3) =
not reported
assumptions (4)
- domain assumption Quantum annealing reliably finds low-energy states of the QUBO objective.
- domain assumption The QUBO formulations from Mücke et al. [8], Pasin et al. [12], and Bauckhage et al. [17] correctly encode feature selection, instance selection, and k-medoids objectives.
- domain assumption The leaderboard metrics, nDCG@10, F1, and DBI, computed on held-out data are trusted as ground truth.
- standard math Quadratic penalties and dimod.generators.combinations enforce exact fixed-size selection constraints on the D-Wave hardware.
Cite this review
Pith. "Pith review of Quantum Annealing for Machine Learning: Applications in Feature Selection, Instance Selection, and Clustering." pith.science (2026). https://pith.science/paper/QQUQDSJ5
@misc{pith2026250715063,
author = {Pith},
title = {Pith review of: Quantum Annealing for Machine Learning: Applications in Feature Selection, Instance Selection, and Clustering},
year = {2026},
howpublished = {\url{https://pith.science/paper/QQUQDSJ5}},
note = {Machine review of arXiv:2507.15063}
}
read the original abstract
This paper explores the applications of quantum annealing (QA) and classical simulated annealing (SA) to a suite of combinatorial optimization problems in machine learning, namely feature selection, instance selection, and clustering. We formulate each task as a Quadratic Unconstrained Binary Optimization (QUBO) problem and implement both quantum and classical solvers to compare their effectiveness. For feature selection, we propose several QUBO configurations that balance feature importance and redundancy, showing that quantum annealing (QA) produces solutions that are computationally more efficient. In instance selection, we propose a few novel heuristics for instance-level importance measures that extend existing methods. For clustering, we embed a classical-to-quantum pipeline, using classical clustering followed by QUBO-based medoid refinement, and demonstrate consistent improvements in cluster compactness and retrieval metrics. Our results suggest that QA can be a competitive and efficient tool for discrete machine learning optimization, even within the constraints of current quantum hardware.
Figures
Figures from the paper (2 more)
Reference graph
Works this paper leans on
-
[1]
A. Pasin, M. F. Dacrema, W. Cuhna, M. A. Gonçalves, P. Cremonesi, N. Ferro, Quantumclef 2025: Overview of the second quantum computing challenge for information retrieval and recommender systems at CLEF, in: G. Faggioli, N. Ferro, P. Rosso, D. Spina (Eds.), Working Notes of CLEF 2025 - Conference and Labs of the Evaluation Forum, CEUR Workshop Proceedings, 2025
work page 2025
-
[2]
A. Pasin, M. F. Dacrema, W. Cuhna, M. A. Gonçalves, P. Cremonesi, N. Ferro, Overview of quantum- clef 2025: The second quantum computing challenge for information retrieval and recommender systems at CLEF, in: J. Carrillo-de-Albornoz, J. Gonzalo, L. Plaza, A. G. S. de Herrera, J. Mothe, F. Piroi, P. Rosso, D. Spina, G. Faggioli, N. Ferro (Eds.), Experimen...
work page 2025
- [3]
-
[4]
K. Boothby, P. Bunyk, J. Raymond, A. Roy, Next-generation topology of d-wave quantum processors, arXiv preprint arXiv:2003.00133 (2020)
arXiv 2020
-
[5]
L. P. Yulianti, K. Surendro, Implementation of quantum annealing: A systematic review, IEEE Transactions on Emerging Topics in Computing 11 (2023) 150–162
work page 2023
-
[6]
Lucas, Ising formulations of many np problems, Frontiers in Physics 2 (2014) 5
A. Lucas, Ising formulations of many np problems, Frontiers in Physics 2 (2014) 5
work page 2014
-
[7]
P. Date, D. Arthur, L. Pusey-Nazzaro, Qubo formulations for training machine learning models, Quantum Computing Applications 1 (2023) 100–112
work page 2023
-
[8]
S. Mücke, R. Heese, S. Müller, M. Wolter, N. Piatkowski, Feature selection on quantum comput- ers, Quantum Machine Intelligence 5 (2023) 11. URL: https://doi.org/10.1007/s42484-023-00099-z. doi:10.1007/s42484-023-00099-z
Show all 31 references
-
[9]
Pranjić, B
D. Pranjić, B. C. Mummaneni, C. Tutschku, Quantum annealing based feature selection in machine learning, Quantum Machine Learning 2 (2023) 11–19
2023
-
[10]
Nembrini, M
R. Nembrini, M. F. Dacrema, P. Cremonesi, Feature selection for recommender systems with quantum computing, Journal of Computing Frontiers 10 (2024) 45–57
2024
-
[11]
Borle, N
N. Borle, N. Zecevic, et al., Feature selection with quantum annealing for interpretable and robust machine learning, Quantum Machine Intelligence 5 (2023) 1–15
2023
-
[12]
Pasin, W
A. Pasin, W. Cunha, M. A. Gonçalves, N. Ferro, A quantum annealing instance selection approach for efficient and effective transformer fine-tuning, in: Proceedings of the 2024 ACM SIGIR International Conference on Theory of Information Retrieval, 2024, pp. 205–214
2024
-
[13]
Cunha, C
W. Cunha, C. França, G. Fonseca, L. Rocha, M. A. Gonçalves, An effective, efficient, and scalable confidence-based instance selection framework for transformer-based text classification, in: Proceedings of the 46th International ACM SIGIR Conference on Research and Development...
2023
-
[14]
P. W. Koh, P. Liang, Understanding black-box predictions via influence functions, in: International conference on machine learning, PMLR, 2017, pp. 1885–1894
2017
-
[15]
Molnar, Interpretable Machine Learning, 3 ed., 2025
C. Molnar, Interpretable Machine Learning, 3 ed., 2025. URL: https://christophm.github.io/ interpretable-ml-book
2025
-
[16]
A. S. Joaquin, B. Wang, Z. Liu, N. Asher, B. Lim, P. Muller, N. F. Chen, In2core: Leveraging influence functions for coreset selection in instruction finetuning of large language models, arXiv preprint arXiv:2408.03560 (2024)
2024 arXiv
-
[17]
Bauckhage, N
C. Bauckhage, N. Piatkowski, R. Sifa, D. Hecker, S. Wrobel, A qubo formulation of the k-medoids problem., in: LWDA, 2019, pp. 54–63
2019
-
[18]
Alvarez-Giron, J
W. Alvarez-Giron, J. Téllez-Torres, J. Tovar-Cortes, H. Gómez-Adorno, Team qiimas on task 2 - clustering: Quantum annealing for k-medoids optimization, in: Working Notes of CLEF 2024 - Conference and Labs of the Evaluation Forum, Grenoble, France, 2024. URL: https://bitbucket....
2024
-
[19]
Kurihara, S
K. Kurihara, S. Tanaka, S. Miyashita, Quantum annealing for clustering, in: Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence (UAI), AUAI Press, 2009, pp. 317–324
2009
-
[20]
Zaech, M
J.-N. Zaech, M. Danelljan, T. Birdal, L. Van Gool, Probabilistic sampling of balanced k-means using adiabatic quantum computing, arXiv preprint arXiv:2310.12153 (2023). URL: https://arxiv.org/abs/ 2310.12153
2023 arXiv
-
[21]
Matsumoto, Y
N. Matsumoto, Y. Hamakawa, K. Tatsumura, K. Kudo, Distance-based clustering using qubo formulations, Scientific Reports 12 (2022) 2669. URL: https://doi.org/10.1038/s41598-022-06559-z. doi:10.1038/s41598-022-06559-z
2022 doi
-
[22]
D.-W. S. Inc., Ocean software documentation, 2023. URL: https://docs.ocean.dwavesys.com/
2023
-
[23]
Morstyn, Annealing-based quantum computing for combinatorial optimal power flow, IEEE Transactions on Smart Grid PP (2022) 1–1
T. Morstyn, Annealing-based quantum computing for combinatorial optimal power flow, IEEE Transactions on Smart Grid PP (2022) 1–1. doi:10.1109/TSG.2022.3200590
2022
-
[24]
T. M. Cover, J. A. Thomas, Elements of Information Theory, 2nd ed., Wiley-Interscience, 2006
2006
-
[25]
Breiman, Random forests, Machine Learning 45 (2001) 5–32
L. Breiman, Random forests, Machine Learning 45 (2001) 5–32
2001
-
[26]
Debeer, C
D. Debeer, C. Strobl, Conditional permutation importance revisited, BMC Bioinformatics 21 (2020) 1–19
2020
-
[27]
W. Liu, P. P. Pokharel, J. C. Principe, Correntropy: Properties and applications in non-gaussian signal processing, IEEE Transactions on Signal Processing 55 (2007) 5286–5298. doi: 10.1109/ TSP.2007.898255
2007
-
[28]
Pasvolsky, D.-W
J. Pasvolsky, D.-W. S. Inc., dimod.generators.combinations — constraint generator for fixed- 𝑘 selection, 2019. URL: https://github.com/dwavesystems/dimod/blob/main/dimod/generators/ constraints.py, accessed: 2025-06-12
2019
-
[29]
Hutter, H
F. Hutter, H. H. Hoos, K. Leyton-Brown, Efficient functional anova: Insights into high-dimensional model performance, in: Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence (UAI), 2014
2014
-
[30]
A. Abid, A. Kamel, J. Zou, Lofo importance: Leave one feature out based feature importance score, https://github.com/aerdem4/lofo-importance, 2020
2020
-
[31]
K. Kira, L. A. Rendell, The feature selection problem: Traditional methods and a new algorithm, AAAI (1992) 129–134
1992
Reviewed August 6, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.