Pith. sign in

REVIEW 3 major objections 5 minor 27 references

Estimating Quantum Execution Requirements for Feature Selection in Recommender Systems Using Extreme Value Theory

T0 review · 3 major / 5 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 By fitting a Generalized Extreme Value distribution to the lowest energies sampled from QAOA, the paper estimates the number of quantum runs needed until one solution matches or beats simulated annealing in recommender feature selection.

desk verdict Useful new resource-estimation method for QAOA shot counts, but the main validation plot appears to measure the wrong statistic. read the letter →

arxiv 2507.03229 v2 pith:ZMX5VLIN submitted 2025-07-04 quant-ph

Jiayang Niu , Qihan Zou , Jie Li , Ke Deng , Mark Sanderson , Yongli Ren This is my paper
classification quant-ph MSC 62G3268Q12
keywords extremevaluetheorygeneralizeddistributionQAOAQUBOfeatureselectionrecommendersystemsshotestimationquantumexecution
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Quantum computers return probabilistic samples, so a recommender-system feature selection solved as a QUBO needs many repeated executions before a good solution is likely. The paper proposes Q-EVT, a method that treats the minimum energy found in each block of executions as an extreme-value observation and fits a generalized extreme value distribution to those minima. From that fit it derives a confidence-based number of runs required to match or beat a classical simulated annealing baseline. If the method is correct, practitioners can decide in advance how many quantum shots to pay for, instead of tuning execution counts empirically. Experiments on two CTR datasets across simulators and two gate-based quantum processors support the estimates.

What carries the argument

The central object is the Generalized Extreme Value (GEV) distribution fitted to block minima of QAOA energy samples. Because quantum outputs are discrete, the samples are first smoothed by adding independent uniform noise, and the fitting itself uses a bootstrap-based rule that selects how many extreme samples are needed for stable GEV parameter estimation, checked with Hotelling's $T^{2}$ test and a multivariate Shapiro-Wilk normality test. The fitted GEV gives the tail probability p that a single block beats the classical baseline, and the formula n_EVT >= log(1 - $\alpha$) / log(1 - p) converts that probability into an execution count for a chosen confidence level.

What would settle it

Run a controlled replication on the Criteo 13-feature, 1000-shot configuration: execute many more blocks than the estimated n_EVT, measure the empirical fraction of block minima whose energy is at or below the simulated annealing baseline, and check whether the curve crosses the 95% confidence line at delta equal to zero. A systematic deviation of the crossing point from zero would directly quantify the GEV tail bias.

Watch

Extended reading notes

Core claim

The paper's central claim is that extreme value theory gives accurate, confidence-based shot counts for QAOA-based feature selection. Concretely, after adding uniform noise to convert discrete QAOA energies into a continuous sample, the authors fit a GEV distribution to block minima and compute p, the probability that a single execution block reaches an energy no higher than the classical simulated annealing reference. The required number of blocks is then n_EVT >= log(1 - alpha) / log(1 - p), and the total shot count is n_EVT times the per-block shot budget. The paper reports that the predicted counts align with empirical outcomes: plots of empirical success ratios against n_EVT plus a shift delta cross the 95% confidence line at delta close to zero, and on a real superconducting processor the average best energy approaches the SA baseline as shots increase.

Load-bearing premise

The entire estimate rests on the smoothed discrete energy minima being well approximated by a GEV distribution, so that the probability p of reaching the classical baseline is accurate; if real hardware noise or discreteness breaks that tail fit, the computed shot count will be biased.

Editorial extensions

If this is right

  • The framework produces a concrete number of QAOA repetitions for a given per-run shot budget and confidence level, removing the need for exhaustive empirical tuning.
  • It supplies a statistically grounded way to compare gate-based quantum hardware against classical simulated annealing for QUBO feature selection under real device noise.
  • The method captures the observed trend that larger feature scales require more runs and that increasing shots per run reduces the number of runs needed, which the paper reports as evidence of consistency.
  • On physical quantum processors, allocating more shots per run is predicted to drive the average minimum energy toward the classical baseline, giving a practical hardware usage guideline.
  • The same estimate pipeline can be applied to other QUBO-based selection tasks, since the core machinery depends on the energy distribution rather than on the specific recommender model.

Reading between the lines

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

  • Beyond feature selection for recommender systems, the same GEV-based shot estimator could be applied to other QAOA-solved combinatorial problems, provided their energy landscapes produce block minima that converge to a GEV tail.
  • The uniform-noise smoothing step treats all equal energies as interchangeable; in regimes where QAOA returns a highly degenerate set of identical minima, the fitted tail may understate the true success probability and overestimate the shots needed, which matches the paper's own note about low-variability breakdown.
  • A systematic stress test across many feature scales, shot budgets, and confidence levels would reveal where GEV tail bias begins, since the paper's empirical crossing checks cover only a few configurations.
  • If hardware noise becomes correlated or non-stationary, the i.i.d. assumption underpinning EVT is violated and the estimated shot counts will drift; monitoring the fitted GEV parameters over time could serve as a detector for such drift.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper proposes Q-EVT, an Extreme Value Theory (EVT) based method for estimating how many QAOA executions (runs, each with a fixed number of shots) are needed, at a specified confidence level, to obtain a solution whose QUBO energy is at least as good as a classical simulated-annealing baseline. The method adds uniform noise to discrete energy samples to make them amenable to GEV fitting, estimates the probability that a single run reaches the classical baseline, and computes the required number of runs as n_EVT = log(1-alpha)/log(1-p). Experiments are reported on Avazu and Criteo using QAOA on two simulators and two gate-based quantum processors. The central claim is that the estimated run counts are accurate, with simulator validation intended to show an empirical crossing at delta=0 and hardware experiments showing improved energies as shot budgets increase.

Significance. If the central validation were correct, the paper would provide a useful, falsifiable resource-estimation tool for quantum optimization in recommender-system feature selection. The strengths are real: the n_EVT formula is explicit and depends on only a small number of estimated quantities; Algorithm 1 gives a reproducible bootstrap-style rule for choosing the number of extreme samples; validation uses 1,000 independent runs; code is provided; and experiments span two simulators and two physical QPUs on two standard datasets. The overall approach is not circular, because the SA baseline and the validation draws are external to the GEV fit. However, the quantitative support for the headline 'high precision' claim currently rests on a misdescribed or missing validation statistic, so the significance cannot yet be fully assessed from the manuscript as written.

major comments (3)
  1. [Section 5.2.2 and Figures 2a/2b] The central validation statistic is either misdescribed or computed incorrectly. The text says that for each total-shot count (n_EVT+delta)*s the authors measured 'the fraction of runs whose minimal energy fell at or below the SA baseline' and plotted this fraction against delta, expecting the curve to cross the 95% line at delta=0. If 'fraction of runs' literally means the fraction of the 1,000 independent QAOA runs, each with s shots, then this fraction estimates p_s = P(min over s shots <= y_ideal), which is a constant that does not depend on the total-run count T = n_EVT+delta. A plot of that fraction against delta would be flat and cannot cross at delta=0. The quantity that should cross at delta=0 is the block success probability 1-(1-p_s)^T, i.e., the fraction of randomly formed blocks of T runs whose block minimum is at or below the SA baseline. The manuscript does not state that such blocks were formed, nor how they were formed from the 1,000 runs. If the authors actually computed the block statistic, the text misdescribes it; if the text is literal, the reported crossing does not follow from the stated procedure. In either case, the strongest quantitative support for the claim that Q-EVT predictions 'pinpoint the required number of repetitions with high precision' is missing or misreported.
  2. [Section 4.3 and Section 5.2.3] The uniform-noise smoothing is a heuristic whose error is not quantified. The fitted GEV distribution for the smoothed block minima is used to compute p and hence n_EVT, but the manuscript provides no goodness-of-fit check, no bound on the approximation error, and no analysis of how discreteness or hardware noise correlations affect the tail. On real QPUs, noise is typically non-stationary and correlated across shots, which can violate the i.i.d. block-minimum assumption underlying Eq. (4). The QPU evaluation in Section 5.2.3 shows only that the average minimum energy decreases as the shot budget increases; it does not directly test whether the predicted n_EVT values are accurate on hardware. Thus the conclusion in Section 6 that 'the predictions of Q-EVT align with empirical outcomes' is currently stronger than what the experiments demonstrate. I recommend either adding a direct QPU validation of predicted run counts or tempering the claim.
  3. [Table 1 and Section 5.2.1] The estimated run counts in Table 1 are reported as point estimates without any measure of uncertainty. The pipeline includes GEV parameter estimation, the n_estimate selection procedure in Algorithm 1, and the p-value threshold, all of which contribute variability to the final n_EVT. Without standard errors, confidence intervals, or a repeated-seed analysis, the reader cannot judge whether differences across simulators, QPUs, or datasets (e.g., 62 vs. 103 runs for Avazu scale 15 at 500 shots) are meaningful. Adding bootstrap intervals over the 200 collected extreme samples, or over repeated GEV fits, would substantially strengthen the robustness claim.
minor comments (5)
  1. [Abstract] The abstract contains a duplicated 'However' and an incomplete sentence transition: 'However, while existing work primarily focuses on effectiveness and efficiency, However, it often neglects...' This should be cleaned up.
  2. [Section 5.1.2] The phrase 'base recommendation mode (DeepFM)' should be 'base recommendation model (DeepFM)'.
  3. [Section 4.2 and Algorithm 1] Algorithm 1 says to 'Fit regression lines to the pairs (n, pbar)' and then determine the smallest n 'based on the intersection of regression lines and p=0.05', but the exact regression model (linear in n? in log n?) and the selection rule are not specified. Please make the procedure fully reproducible.
  4. [Section 5.2.3] The hardware evaluation reports the average of 20 independent QAOA executions at each shot budget, but no error bars or variance information are shown in Figure 2c. Since the average of 20 minima can be sensitive to outliers, error bars or a confidence band would help interpret the convergence to the SA baseline.
  5. [Section 5.1.1] Please clarify whether the 200 extreme samples collected per configuration are block minima over s shots (as implied by Section 4.3) or per-shot minima, since the distinction directly affects the interpretation of p in Eq. (5).

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity: n_EVT is a genuine extrapolation from GEV fits validated on new runs; the self-cited PDQUBO construction is an input, not the EVT prediction. The Section 5.2.2 ratio ambiguity is a reporting/validation-metric concern, not a circular reduction.

full rationale

The paper's derivation chain is not circular. The QUBO matrix Q is taken from the authors' prior PDQUBO work [20], but that prior work is an input problem formulation, not the EVT prediction target. The classical baseline y_ideal is obtained from simulated annealing, which is external to the fitted quantum data. The GEV parameters are fitted to 200 collected extreme samples, and the required execution count n_EVT is obtained by inverting the standard EVT formula 1-(1-p)^n >= alpha in Section 4.3. This is a genuine extrapolation, not a fitted parameter restated as a prediction. The simulator validation in Section 5.2.2 uses 1,000 independent QAOA runs, so the reported crossing near delta = 0 is not in-sample by construction. There is a minor self-citation of the authors' own PDQUBO framework, but it is not load-bearing for the EVT claim: even if the Q matrix construction were replaced by another QUBO formulation, the EVT shot-estimation procedure would still be well-defined. The limitation passage in Section 5.2.4 explicitly identifies breakdown scenarios where the method loses statistical basis or overestimates shot counts, which further indicates the approach is not designed to force agreement with its own outputs. One non-circular verification gap should be noted: Section 5.2.2 defines the empirical ratio as 'the fraction of runs whose minimal energy fell at or below the SA baseline,' which, if read literally as a per-run fraction, is a fixed probability p and cannot cross the 95% line as the run count n_EVT+delta varies. If the intended quantity is the block success probability 1-(1-p)^(n_EVT+delta), the crossing at delta = 0 is anchored to the defining equation for n_EVT and the paper does not state how blocks were formed from the 1,000 runs. This is a correctness and reporting issue about what the validation curve actually measures, not a circularity in the derivation, because the fitted GEV is still being compared against independent empirical draws rather than being reused as the validation statistic. Overall, the central EVT estimate is not equivalent to its inputs by construction, and no circular step rises beyond a minor self-citation.

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

The method relies on standard EVT convergence plus a heuristic smoothing step. The main fitted quantities are the GEV parameters, without reported values or error bars. No new physical entities are introduced.

free parameters (5)
  • GEV parameters (mu, sigma, xi) per configuration = estimated from 200 extreme samples
    The central estimate n_EVT is a direct function of these fitted parameters; the paper reports no numerical values.
  • Extreme sample count = 200 chosen, with n_estimate 70-80 from algorithm
    Chosen conservatively by hand; larger counts cost more quantum time.
  • QAOA circuit depth p = 3
    Chosen by hand; the paper does not justify this depth.
  • Uniform noise smoothing scale delta = smallest nonzero difference between sorted unique energies
    Determined from data, but the smoothing itself is a modeling choice that affects the GEV fit.
  • p-value threshold in Algorithm 1 = 0.05
    Conventional threshold, but the selection of n_estimate depends on it.
assumptions (5)
  • standard math Block minima of i.i.d. samples converge to a GEV distribution.
    EVT theorem used in Section 4.1.
  • domain assumption Adding uniform noise makes the discrete energy distribution continuous enough for GEV to apply.
    Heuristic introduced in Section 4.3; no formal domain-of-attraction argument.
  • domain assumption Quantum energy samples are i.i.d. across runs.
    Assumed in Section 4.1; not tested for time-dependent hardware noise.
  • domain assumption Lower QUBO energy implies better recommendation performance.
    Inherited from prior QUBO feature selection work, used in Section 3.
  • domain assumption QAOA parameters tuned on simulators transfer to real hardware.
    Used in Section 5.1.1; real-device noise may shift the optimal parameters.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Estimating Quantum Execution Requirements for Feature Selection in Recommender Systems Using Extreme Value Theory." pith.science (2026). https://pith.science/paper/ZMX5VLIN

@misc{pith2026250703229,
  author       = {Pith},
  title        = {Pith review of: Estimating Quantum Execution Requirements for Feature Selection in Recommender Systems Using Extreme Value Theory},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZMX5VLIN}},
  note         = {Machine review of arXiv:2507.03229}
}
read the original abstract

Recent advances in quantum computing have significantly accelerated research into quantum-assisted information retrieval and recommender systems, particularly in solving feature selection problems by formulating them as Quadratic Unconstrained Binary Optimization (QUBO) problems executable on quantum hardware. However, while existing work primarily focuses on effectiveness and efficiency, it often overlooks the probabilistic and noisy nature of real-world quantum hardware. In this paper, we propose a solution based on Extreme Value Theory (EVT) to quantitatively assess the usability of quantum solutions. Specifically, given a fixed problem size, the proposed method estimates the number of executions (shots) required on a quantum computer to reliably obtain a high-quality solution, which is comparable to or better than that of classical baselines on conventional computers. Experiments conducted across multiple quantum platforms (including two simulators and two physical quantum processors) demonstrate that our method effectively estimates the number of required runs to obtain satisfactory solutions on two widely used benchmark datasets.

Figures

Figures reproduced from arXiv: 2507.03229 by the authors.

Figure 1
Figure 1. The Overview of Q-EVT 4.1 Extreme Value Theory (EVT) QAOA yields probabilistic outputs, where each execution (shot) returns only one candidate solution. Due to noise and inherent randomness, optimal solutions are obtained only with limited prob￾ability, motivating the use of repeated shots. Extreme Value Theory (EVT) [17, 18, 23, 24] offers a natural framework to analyze the min￾imum energy values obtained across th… view at source ↗
Figure 2
Figure 2. (a) and (b) Evaluation on simulators, and (c) Evaluation and trend on physical quantum processor Ankaa-3. Note the [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

27 extracted references · 20 canonical work pages

  1. [1]

    Google Quantum AI et al. 2024. Quantum error correction below the surface code threshold. Nature 638, 8052 (2024), 920

    work page 2024

  2. [2]

    Theodore Wilbur Anderson, Theodore Wilbur Anderson, Theodore Wilbur An- derson, Theodore Wilbur Anderson, and Etats-Unis Mathématicien. 1958. An introduction to multivariate statistical analysis . Vol. 2. Wiley New York

    work page 1958

  3. [3]

    Avazu Inc. 2015. Avazu CTR Prediction. https://www.kaggle.com/c/avazu-ctr- prediction Accessed: 2025-07-15

    work page 2015

  4. [4]

    Yuzhi Cai and Dominic Hames. 2010. Minimum sample size determination for generalized extreme value distribution. Communications in Statistics—Simulation and Computation® 40, 1 (2010), 87–98

    work page 2010

  5. [5]

    2001.An introduction to statistical modeling of extreme values

    Stuart Coles, Joanna Bawa, Lesley Trenner, and Pat Dorazio. 2001.An introduction to statistical modeling of extreme values . Vol. 208. Springer

    work page 2001

  6. [6]

    Criteo Labs. 2014. Criteo Labs Display Advertising Challenge. https://www. kaggle.com/c/criteo-display-ad-challenge Accessed: 2025-07-15

    work page 2014

  7. [7]

    1997.Bootstrap methods and their application

    Anthony Christopher Davison and David Victor Hinkley. 1997.Bootstrap methods and their application. Number 1. Cambridge university press

    work page 1997

  8. [8]

    Bradley Efron and Robert J Tibshirani. 1994. An introduction to the bootstrap . Chapman and Hall/CRC

    work page 1994

Show all 27 references
  1. [9]

    Davide Faranda, Jorge Milhazes Freitas, Valerio Lucarini, Giorgio Turchetti, and Sandro Vaienti. 2013. Extreme value statistics for dynamical systems with noise. Nonlinearity 26, 9 (Aug. 2013), 2597–2622. doi:10.1088/0951-7715/26/9/2597

    2013 doi

  2. [10]

    Davide Faranda and Sandro Vaienti. 2014. Extreme value laws for dynamical systems under observational noise. Physica D: Nonlinear Phenomena 280 (2014), 86–94

    2014

  3. [11]

    Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. 2014. A quantum approxi- mate optimization algorithm. arXiv preprint arXiv:1411.4028 (2014)

    2014 arXiv

  4. [12]

    Maurizio Ferrari Dacrema, Fabio Moroni, Riccardo Nembrini, Nicola Ferro, Guglielmo Faggioli, and Paolo Cremonesi. 2022. Towards feature selection for ranking and classification exploiting quantum annealers. InProceedings of the 45th International ACM SIGIR Conference on Resear...

    2022

  5. [13]

    M Ivette Gomes and Armelle Guillou. 2015. Extreme value theory and statistics of univariate extremes: a review. International statistical review 83, 2 (2015), 263–292

    2015

  6. [14]

    Huifeng Guo, Ruiming Tang, Yunming Ye, Zhenguo Li, and Xiuqiang He. 2017. DeepFM: a factorization-machine based neural network for CTR prediction.arXiv preprint arXiv:1703.04247 (2017)

    2017 arXiv

  7. [15]

    Laurens Haan and Ana Ferreira. 2006. Extreme value theory: an introduction . Vol. 3. Springer

    2006

  8. [16]

    Andrew D King, Alberto Nocera, Marek M Rams, Jacek Dziarmaga, Roeland Wiersema, William Bernoudy, Jack Raymond, Nitin Kaushal, Niclas Heinsdorf, Richard Harris, et al. 2025. Beyond-classical computation in quantum simulation. Science (2025), eado6285

    2025

  9. [17]

    Samuel Kotz and Saralees Nadarajah. 2000. Extreme value distributions: theory and applications. world scientific

    2000

  10. [18]

    Marie Kratz. 2019. Introduction to extreme value theory: Applications to risk analysis and management. 2017 MATRIX Annals (2019), 591–636

    2019

  11. [19]

    Riccardo Nembrini, Maurizio Ferrari Dacrema, and Paolo Cremonesi. 2021. Fea- ture selection for recommender systems with quantum computing. Entropy 23, 8 (2021), 970

    2021

  12. [20]

    Jiayang Niu, Jie Li, Ke Deng, Mark Sanderson, Nicola Ferro, and Yongli Ren. 2025. Performance-Driven QUBO for Recommender Systems on Quantum Annealers. arXiv:2410.15272 [cs.IR] https://arxiv.org/abs/2410.15272

    2025 arXiv

  13. [21]

    Andrea Pasin, Washington Cunha, Marcos André Gonçalves, and Nicola Ferro

  14. [22]

    Michael JD Powell. 1994. A direct search optimization method that models the objective and constraint functions by linear interpolation . Springer

    1994

  15. [23]

    Richard L Smith. 1990. Extreme value theory.Handbook of applicable mathematics 7, 437-471 (1990), 18

    1990

  16. [24]

    Richard L Smith. 1994. Extreme values. Chapman & Hall London, UK

    1994

  17. [25]

    José A Villasenor Alva and Elizabeth González Estrada. 2009. A generalization of Shapiro–Wilk’s test for multivariate normality. Communications in Statis- tics—Theory and Methods 38, 11 (2009), 1870–1883

    2009

  18. [26]

    Tristan Zaborniak and Rogério de Sousa. 2021. Benchmarking Hamiltonian noise in the D-Wave quantum annealer. IEEE Transactions on Quantum Engineering 2 (2021), 1–6

    2021

  19. [2024]

    In Proceedings of the 2024 ACM SIGIR International Conference on Theory of Information Retrieval

    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 . 205–214

    2024

Pith tools

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