Performance-Driven QUBO for Recommender Systems on Quantum Annealers

1. Problem Statement

Recommender systems often suffer from the "curse of dimensionality" due to the vast number of item features, leading to redundancy, increased storage costs, and reduced retrieval efficiency. While feature selection is critical, traditional methods often fail to explicitly optimize for the final recommendation performance (e.g., ranking metrics like nDCG).

Existing Quantum Annealing (QA) approaches for feature selection, which formulate the problem as Quadratic Unconstrained Binary Optimization (QUBO), face two main limitations:

1. Misaligned Objectives: Current QUBO-based methods (e.g., MIQUBO, CoQUBO) construct the coefficient matrix $Q$ based on statistical dependencies (mutual information, correlation) or model outputs, rather than the direct impact on the recommendation performance metric.
2. Instability: The performance of quantum annealers on real hardware (NISQ era) is sensitive to problem size, sample counts, and problem difficulty, leading to inconsistent results.

The authors pose three key research questions:

• How does the instability of quantum annealers affect recommender system performance?
• How effective are quantum annealers for feature selection in this domain?
• Can QUBO-based methods on quantum hardware match or surpass classical feature selection baselines?

2. Methodology: PDQUBO

The authors propose PDQUBO (Performance-Driven Quadratic Unconstrained Binary Optimization), a novel framework that aligns the QUBO optimization objective directly with the downstream recommendation performance using counterfactual analysis.

Core Workflow

1. Base Model Training: A recommendation model ($G_\Theta$) is trained on the full feature set $F$.
2. Counterfactual Analysis: The method evaluates the impact of features by creating "counterfactual instances." It systematically masks (removes) individual features ($f_i$) and pairs of features ($f_i, f_j$) from the input and measures the change in the evaluation metric (e.g., nDCG).
   • $E_i$: Performance drop when $f_i$ is removed.
   • $E_{ij}$: Performance drop when both $f_i$ and $f_j$ are removed.
   • Note: A positive $E$ indicates the feature is important (performance drops when removed); a negative $E$ suggests the feature is redundant or harmful.
3. QUBO Formulation: The counterfactual values are used to construct the QUBO coefficient matrix $Q$:
   • Diagonal elements ($Q_{ii}$): Set to $-E_i$ (representing individual feature importance).
   • Off-diagonal elements ($Q_{ij}$): Set to $-E_{ij}$ (representing pairwise feature interactions).
   • The objective function minimizes energy $Y = x^T Q x$, where $x$ is a binary vector indicating feature selection. Minimizing $Y$ corresponds to selecting features that maximize the recommendation performance.
4. Optimization: The constructed QUBO problem is solved using either classical solvers (Simulated Annealing, Tabu Search) or Quantum Annealers (D-Wave).
5. Retraining: The selected feature subset is used to retrain the base model for final evaluation.

Key Distinctions

• Model-Agnostic: PDQUBO works with any base model (KNN, MLP, NCF) and any metric.
• Interaction-Aware: Unlike "filter" methods that treat features independently, PDQUBO explicitly models pairwise interactions via the quadratic terms in $Q$.

3. Key Contributions

1. PDQUBO Framework: A new QUBO formulation that explicitly links feature selection to recommendation performance via counterfactual analysis, ensuring the optimization direction is performance-driven rather than statistically driven.
2. Comprehensive Stability Analysis: A detailed investigation into the instability of real-world quantum annealers, analyzing how solution quality varies with:
   • Problem size (number of features).
   • Sample size (number of annealing runs).
   • Problem difficulty (data sparsity).
3. Empirical Validation: Extensive experiments on real-world datasets (CLEF 2024 QuantumCLEF datasets, KuaiRec, KuaiRand, Avazu, Criteo) demonstrating that PDQUBO outperforms existing QUBO baselines and competes with state-of-the-art classical feature selection methods.
4. Scalability Insights: Analysis of the computational cost and a proposed two-stage pruning strategy to mitigate the $O(|F|^2)$ complexity of constructing the full QUBO matrix, though the paper concludes the full quadratic formulation is necessary for optimal performance.

4. Experimental Results

The authors evaluated PDQUBO against baselines (CQFS, MIQUBO, CoQUBO, QUBO-Boosting) and classical methods (Lasso, GBDT, Permutation Importance) across various datasets and models.

• Performance vs. Baselines:

  • PDQUBO consistently achieved the best or second-best nDCG@10 scores across most configurations on the 150_ICM and 500_ICM datasets.
  • In CTR prediction tasks (Avazu, Criteo), PDQUBO-Hybrid (using a hybrid quantum-classical solver) achieved the highest AUC scores, outperforming both classical baselines and other QUBO variants.
  • PDQUBO significantly outperformed other QUBO methods (like MIQUBO), proving that performance-driven construction is superior to statistical dependency construction.

• Stability Findings:

  • Problem Size: Quantum Annealing (QA) results become unstable as the number of features increases beyond the hardware's logical qubit capacity, whereas classical solvers (SA, TS) remain stable.
  • Sample Size: Increasing the number of QA samples significantly reduces energy variance and improves downstream performance, highlighting the need for sufficient sampling in NISQ devices.
  • Difficulty: QA tends to show larger but more volatile performance gains on sparse (difficult) datasets.

• Necessity of Quadratic Terms:

  • Experiments comparing "Indiv" (diagonal only) vs. "All" (full matrix) showed that including pairwise interactions ($Q_{ij}$) is crucial. The "All" approach yielded significantly better results, confirming that feature interactions are vital for effective selection in this context.

• Efficiency:

  • While classical solvers' time complexity grows exponentially with problem size, the quantum annealing time remains relatively constant (limited by hardware access and sampling time), offering a potential speed advantage for large-scale problems once hardware constraints are overcome.

5. Significance and Future Directions

• Bridging the Gap: This work successfully bridges the gap between theoretical quantum optimization and practical recommender system deployment by ensuring the optimization objective directly targets the business metric (recommendation quality).
• Practical Viability: The results suggest that even with current NISQ hardware limitations, hybrid quantum-classical approaches can provide competitive or superior feature selection compared to mature classical methods.
• Future Work: The authors suggest extending PDQUBO to model higher-order feature interactions (beyond pairs) and exploring variational quantum algorithms on gate-based quantum computers to handle larger-scale, more complex feature structures.

In conclusion, PDQUBO represents a significant step forward in applying quantum computing to real-world recommendation challenges, demonstrating that performance-driven, counterfactual-based QUBO formulations can effectively leverage quantum annealers for high-quality feature selection.