Estimating Quantum Execution Requirements for Feature Selection in Recommender Systems Using Extreme Value Theory Conference: Proceedings of the Nineteenth ACM Conference on Recommender Systems; September 22–26, 2025; Prague, Czech Republic Proceedings of the Nineteenth ACM Conference on Recommender
Jiayang Niu, Qihan Zou, Jie Li, Ke Deng, Mark Sanderson, Yongli Ren · 2025
Read Estimating Quantum Execution Requirements for Feature Selection in Recommender Systems Using Extreme Value Theory Conference: Proceedings of the Nineteenth ACM Conference on Recommender Systems; September 22–26, 2025; Prague, Czech Republic Proceedings of the Nineteenth ACM Conference on Recommender by Jiayang Niu, Qihan Zou, Jie Li, Ke Deng, Mark Sanderson, Yongli Ren (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-03229.txt.
Introduction
Jiayang Niu and co-authors estimate how many runs a quantum computer needs to give a trustworthy answer for feature selection in recommender systems, in a 2025 paper. Feature selection can be framed as a binary optimization problem for quantum hardware. Prior work stresses speed and quality but overlooks the noisy, chance-driven nature of real machines.
Their method uses extreme value theory to assess the usability of quantum solutions. For a fixed problem size, it estimates the executions needed to reliably match or beat classical baselines. Experiments span several quantum platforms. The work adds a practical yardstick for when quantum help is worth its cost.
Catalog record
| CREATOR | Jiayang Niu, Qihan Zou, Jie Li, Ke Deng, Mark Sanderson, Yongli Ren |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 27 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-03229
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Estimating Quantum Execution Requirements for Feature Selection in Recommender Systems Using Extreme Value Theory Conference: Proceedings of the Nineteenth ACM Conference on Recommender Systems; September 22–26, 2025; Prague, Czech Republic Proceedings of the Nineteenth ACM Conference on Recommender Systems (RecSys ’25), September 22–26, 2025, Prague, Czech Republic DOI: 10.1145/3705328.3748029 ISBN: 979-8-4007-1364-4/2025/09 CCS: Mathematics of computing Probability and statistics CCS: Information systems Recommender systems CCS: Computer systems organization Quantum computing Jiayang Niu, Qihan Zou, Jie Li, Ke Deng, Mark Sanderson, Yongli Ren Abstract . Recent progress in quantum computing has advanced research in quantum-assisted information retrieval and recommender systems, especially for feature selection via Quadratic Unconstrained Binary Optimization (QUBO). However, while existing work primarily focuses on effectiveness and efficiency, However, it often neglects the inherent noise and probabilistic nature of quantum hardware. In this paper, we propose a method based on Extreme Value Theory (EVT) to estimate the number of quantum executions (shots) needed to reliably obtain high-quality solutions—comparable to or better than classical baselines. Experiments on both simulators and two physical quantum devices demonstrate that our method effectively estimates the number of required runs to obtain satisfactory solutions on two widely used benchmark datasets. † † cc-license: by 1. Introduction Recent advancements in quantum technology, along with growing media attention toward commercial quantum computers, suggest that qubit-based hardware may not only complement but in certain domains may outperform traditional transistor-based computing systems that have dominated for decades ( King et al. 2025 ; AI et al. 2024 ) . Researchers have begun to explore how these quantum techniques can benefit Information Retrieval and Recommender Systems (RecSys). For instance, Nembrini et al. ( Ferrari Dacrema et al. 2022 ) embedded several classical feature selection strategies into Quadratic Unconstrained Binary Optimization (QUBO) formulations, while Niu et al. ( Niu et al. 2025 ) applied counterfactual analysis to assess individual feature contributions to model performance and integrated these insights into their QUBO model. However, these studies primarily focus on the effectiveness and the efficiency when using quantum annealers (e.g., D-Wave), leaving two key research gaps : (1) Because quantum measurements are inherently probabilistic, it is necessary to run many shots 1 1 1 A shot refers to a single execution of a quantum program, including measurement. Multiple shots are used to sample from the output distribution. , so as to determine the most likely or optimal results. For a fixed problem (e.g., feature selection in RecSys), it remains unclear how many shots are required to obtain high-quality results. (2) Compared to quantum annealers, gate-based quantum computers are more powerful and versatile, as they support a broader class of quantum algorithms beyond optimisation. Thus, exploring their use in this domain holds significant potential. In this paper, we aim to answer the research question: How to estimate the number of required shots for gate-based quantum computers to achieve good results in feature selection for recommendation tasks? Specifically, we propose Quantum-EVT, a practical and theoretically grounded framework based on Extreme Value Theory (EVT) ( Kotz and Nadarajah 2000 ) for estimating the required number of quantum executions (shots), which provides confidence-based estimates that predict when quantum solvers are likely to outperform classical baseline model in terms of energy optimisation. Following existing work ( Nembrini et al. 2021 ; Ferrari Dacrema et al. 2022 ; Niu et al. 2025 ) , we frame the feature selection problem in recommendation as a QUBO formulation for a click-through-rate prediction task and solve it using the Quantum Approximate Optimisation Algorithm (QAOA) ( Farhi et al. 2014 ) , which is designed to solve combinatorial problems on a gate-based quantum device. However, there are two main challenges: (1) Deploying EVT requires several key statistical parameters, which must be estimated from many quantum executions to obtain some extreme value samples. While more samples generally lead to better results, there is a trade-off with computational cost. Thus, determining the minimum sufficient number of extreme samples becomes essential. (2) The quantum energy values derived from QUBO problems are inherently discrete, while EVT assumes a continuous distribution. Therefore, we must adapt the discrete quantum outputs to be compatible with EVT. To overcome these challenges, (1) we propose an algorithm that statistically determines the minimal number of extreme samples needed for stable EVT parameter estimation; (2) we introduce a technique to approximate a continuous distribution by adding uniform noise to the discrete quantum energy values. The main contributions of this work are: (i) An EVT-based framework for estimating the required number of quantum executions, providing confidence-based shot estimates that predict when quantum solvers outperform classical simulated annealing (SA). (ii) The first application of gate-based quantum computers to solve the feature selection problem in recommender systems. (iii) A comprehensive evaluation of EVT-based predictions, demonstrating that the estimated number of runs is both accurate and robust under realistic settings, which also validates EVT as a robust tool for modelling quantum optimisation behaviour. 2. RELATED WORKS Recent studies have explored the use of quantum optimization, particularly Quadratic Unconstrained Binary Optimization (QUBO), for feature and instance selection in information retrieval ( Pasin et al. 2024 ) (IR) and recommender systems (RecSys). CQFS ( Nembrini et al. 2021 ) , MIQUBO, CoQUBO, QUBO-Boosting ( Ferrari Dacrema et al. 2022 ) , and PDQUBO ( Niu et al. 2025 ) all formulate the feature selection task as a QUBO problem by designing different strategies for constructing the coefficient matrix Q . These strategies range from leveraging collaborative signals ( Nembrini et al. 2021 ) , to statistical measures such as mutual information and correlation ( Ferrari Dacrema et al. 2022 ) , to performance-oriented counterfactual analysis ( Niu et al. 2025 ) . These works also emphasize that quantum annealers, particularly D-Wave systems, are well-suited to solving QUBO problems due to their hardware design. However, PDQUBO additionally notes that annealer performance deteriorates as problem size increases, revealing stability concerns. Zaborniak et al. ( Zaborniak and de Sousa 2021 ) also quantitatively benchmark the Hamiltonian noise on different generations of D-Wave hardware, showing significantly higher noise levels in newer systems (e.g., Advantage_system1.1) compared to earlier models. Unlike quantum annealers, gate-based quantum computers are universal devices capable of running a broader class of quantum algorithms. The Quantum Approximate Optimization Algorithm (QAOA) ( Farhi et al. 2014 ) is a prominent candidate for solving QUBO problems on such devices. QAOA leverages parameterized variational circuits to approximate optimal solutions, enabling hybrid quantum-classical optimization pipelines. To complement the empirical use of QAOA, we adopt Extreme Value Theory (EVT) ( Coles et al. 2001 ; Gomes and Guillou 2015 ) as a principled statistical framework to model the distribution of low-energy outcomes obtained from repeated quantum executions. EVT naturally fits the structure of quantum optimization, allowing us to estimate how many repetitions are required to reach a target solution quality (e.g., matching classical baselines) under a specified confidence level. 3. PRELIMINARIES Quadratic Unconstrained Binary Optimization (QUBO) is a mathematical framework for representing binary optimization problems. It optimizes a binary vector \mathbf{x}\in\{0,1\}^{n} (with the i -th entry x_{i} denoting the i -th feature) over a symmetric matrix Q\in\mathbb{R}^{n\times n} : (1) \min_{\mathbf{x}}Y=\mathbf{x}^{\top}Q\mathbf{x}+\left(\sum_{i=1}^{n}x_{i}-k\right)^{2},\quad\mathbf{x}\in\{0,1\}^{n} where Y is the ground state energy in quantum solutions, and the penalty term \left(\sum_{i}x_{i}-k\right)^{2} enforces a