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

Jiayang Niu, Qihan Zou, Jie Li, Ke Deng, Mark Sanderson, Yongli Ren

TL;DR

This paper introduces Quantum-EVT, a novel framework that uses Extreme Value Theory to predict the exact number of quantum computations (shots) needed to achieve reliable feature selection for recommender systems. This is crucial for efficiently utilizing noisy quantum hardware, ensuring performance comparable to classical methods without excessive, costly trial-and-error.

What Problem Does This Paper Address?

Quantum computing holds immense promise for tasks like feature selection in recommender systems, particularly through algorithms like the Quantum Approximate Optimization Algorithm (QAOA) applied to Quadratic Unconstrained Binary Optimization (QUBO) problems. However, current quantum hardware is inherently noisy and probabilistic. This means a single quantum computation (a "shot") doesn't guarantee an optimal result; multiple shots are required to sample the solution space and identify high-quality solutions. A critical unanswered question is: how many shots are truly necessary to achieve a desired level of performance, especially when aiming to match or surpass classical algorithms? Without this knowledge, researchers and engineers risk wasting valuable quantum computing resources on insufficient runs or, conversely, performing far more computations than needed. This paper addresses this gap by providing a principled, statistically grounded method to estimate these essential quantum execution requirements.

Methods

The core of this paper is the Quantum-EVT (Q-EVT) framework. It combines several key ideas:

  • QUBO Formulation for Feature Selection: The problem of selecting the best subset of features for a recommender system is framed as a QUBO problem. This is a standard approach in the field, often using techniques like PDQUBO to encode feature importance and interactions into the QUBO matrix.
  • Quantum Approximate Optimization Algorithm (QAOA): QAOA is employed as the quantum algorithm to solve the QUBO problem on gate-based quantum computers. QAOA is a hybrid quantum-classical algorithm designed for combinatorial optimization.
  • Extreme Value Theory (EVT): This is the novel component. EVT is a statistical framework used to model the behavior of extreme events. In this context, it's applied to the distribution of the minimum energy values obtained from repeated QAOA executions. By modeling these extreme low-energy outcomes, EVT can predict the probability of achieving a certain solution quality.
  • Estimating Required Extreme Samples: A crucial practical challenge is that EVT parameter estimation itself requires a sufficient number of extreme samples. The paper proposes a method to statistically determine the minimum number of these extreme samples needed for stable EVT parameter estimation, balancing accuracy with computational cost. This involves using statistical tests (Hotelling's T² and multivariate Shapiro-Wilk) on bootstrapped samples.
  • Handling Discrete Quantum Outputs: Quantum measurements yield discrete energy values. To align these with EVT's typical assumption of continuous distributions, the authors add uniform noise to the discrete quantum energy values. This "smoothing" helps EVT model the distribution more accurately.
  • Confidence-Based Shot Estimation: Given a target energy value (often derived from a classical baseline like Simulated Annealing), Q-EVT uses the fitted EVT model to calculate the number of quantum executions (shots) required to achieve that target with a specified confidence level (e.g., 95%).

Datasets

The paper evaluates its method using two standard click-through-rate (CTR) prediction datasets:

  • Avazu: A widely used dataset for CTR prediction.
  • Criteo: Another common dataset for CTR prediction.

These datasets are used to train a base recommendation model (DeepFM) which then informs the QUBO formulation for feature selection. No new benchmarks were introduced; the focus was on applying the EVT framework to existing problem formulations and datasets.

Key Insights and Ideas

  • EVT is a powerful tool for quantifying quantum uncertainty: The paper demonstrates that EVT, typically used for rare events in nature or finance, is surprisingly effective at modeling the probabilistic outcomes of quantum computations. This provides a principled way to move beyond brute-force or heuristic approaches to determining quantum shot counts.
  • The "sweet spot" for quantum execution is estimable: The core insight is that there's a statistically predictable number of quantum runs needed to reliably achieve performance comparable to classical methods. This moves us closer to practical quantum advantage by making resource estimation more concrete.
  • Noise and hardware limitations necessitate robust estimation: Experiments on real quantum hardware (Ankaa-3 and Forte) showed that more runs are required compared to simulators. This highlights the importance of Q-EVT's confidence-based estimation, as it accounts for these real-world imperfections.
  • Smoothed discrete outputs are key for EVT: The technique of adding uniform noise to discrete quantum outputs is a practical workaround that allows EVT to be applied effectively, bridging the gap between theoretical assumptions and experimental reality.

Key Results

  • Accurate Shot Estimation: Q-EVT successfully predicted the number of quantum executions (shots) required to match or surpass classical Simulated Annealing (SA) performance on both simulators and real quantum devices. For instance, on the Avazu dataset at scale 13 with 500 shots per run, Q-EVT estimated 16 runs for 95% confidence, and empirical evaluation showed the results crossing the SA baseline precisely at this estimated number.
  • Scalability: The required number of runs increases with feature selection scale (e.g., from 7 runs at scale 10 to 62 runs at scale 15 on the Avazu simulator with 500 shots).
  • Shot Budget Impact: Increasing the number of shots per run (e.g., from 500 to 2000) significantly reduces the total number of runs needed to achieve the target performance.
  • Hardware vs. Simulator Gap: Real quantum devices consistently required more runs than simulators to achieve the same performance level, underscoring the need for Q-EVT's robust estimation. For example, on Criteo at scale 15 with 500 shots, the simulator needed 62 runs, while the physical device needed 114 runs for 95% confidence.

Limitations and Future Work

  • Breakdown Scenarios: The authors acknowledge two scenarios where Q-EVT might struggle:
  • Low Output Variability: If a quantum algorithm consistently produces identical optimal outputs even with few shots, there isn't enough variability for EVT to reliably estimate parameters.
  • Persistent Suboptimality: If quantum outputs remain significantly suboptimal even after many executions, the estimated shot count might become unstable or overestimated.
  • Future Work: The paper suggests exploring Q-EVT for other quantum optimization problems beyond feature selection and investigating its application to different quantum algorithms and hardware architectures. Further research into mitigating the identified breakdown scenarios would also be valuable.

Summary updated

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.
BibTeX
@inproceedings{niu2026estimating,
  author = {Jiayang Niu and Qihan Zou and Jie Li and Ke Deng and Mark Sanderson and Yongli Ren},
  title = {{Estimating Quantum Execution Requirements for Feature Selection in Recommender Systems Using Extreme Value Theory}},
  booktitle = {Recsys‘25 Short Paper Track},
  year = {2026},
  url = {https://openreview.net/forum?id=LzvCa6kRAI},
}
Figure