Quantum Feature Selection with Higher-Order Binary Optimization on Trapped-Ion Hardware

This paper presents a quantum feature-selection framework using a higher-order unconstrained binary optimization (HUBO) formulation with multivariate dependencies, which was successfully implemented on IonQ Forte trapped-ion hardware to demonstrate competitive classification performance and the feasibility of higher-order quantum optimization for machine learning preprocessing.

The Gist

Imagine you are trying to solve a massive puzzle, but you have 32 different pieces (features) to choose from, and you only need a few of them to see the whole picture clearly. The problem is, some pieces look important on their own, some look important only when paired with others, and some are just duplicates of each other.

This paper describes a new way to use a quantum computer to find the perfect set of puzzle pieces. Instead of just looking at pieces one by one or in pairs (like traditional methods), this new method looks at how groups of three pieces work together.

Here is the breakdown of their approach using simple analogies:

1. The Problem: Too Many Choices

In data science, "Feature Selection" is the process of picking the most useful information from a huge list.

• The Old Way (QUBO): Imagine trying to pick the best team members by only asking, "How good is Person A?" and "How well do Person A and Person B get along?" This misses the fact that sometimes, a specific group of three people creates a magic chemistry that you can't see by looking at them individually or in pairs.
• The New Way (HUBO): The authors created a method that asks, "How good is this specific trio of people working together?" They call this Higher-Order Unconstrained Binary Optimization (HUBO). It's like having a super-intelligent manager who can instantly understand complex group dynamics, not just individual skills.

2. The Recipe: The "Energy" Model

To find the best team, the researchers built a mathematical "recipe" called a Hamiltonian (think of it as a scorecard).

• Relevance (One-body): If a piece of information is very useful on its own, the scorecard gives it a "bonus" (lowers the energy).
• Redundancy (Two-body): If two pieces of information say the exact same thing, the scorecard penalizes picking both of them (raises the energy).
• Complex Groups (Three-body): This is the secret sauce. If three pieces of information create a powerful insight only when combined, the scorecard rewards that specific trio.
• The "No Free Lunch" Rule: To stop the computer from just picking every single piece (which is the lazy, easy solution), they added a penalty. It's like a strict coach who says, "You can't pick the whole team; you must pick the best small squad."

3. The Machine: The Quantum Gym

They tested this recipe on a real quantum computer made by IonQ, which uses trapped ions (charged atoms) as its "bits."

• The Workout: They used a technique called Digitized Counterdiabatic Quantum Optimization (DCQO). Imagine trying to find the lowest point in a foggy valley. A normal walk might get you stuck in a small dip. This technique is like a guided tour that helps the computer "slide" quickly and smoothly to the absolute lowest point (the best solution) without getting stuck in the fog.
• The Result: The computer ran this "workout" and spit out a list of probabilities for each feature, telling them how often that feature appeared in the best solutions.

4. The Test Drive: Two Real-World Scenarios

They tested their method on two different datasets to see if it actually worked:

• Scenario A: The Gallstone Dataset (Medical)

  • The Task: Predict if a patient has gallstones based on 32 health metrics (like cholesterol, age, weight).
  • The Outcome: The quantum method picked 19 key metrics. It performed better than standard computer methods (like PCA or picking the top 19 by simple ranking). It found a smaller, cleaner list of symptoms that predicted the disease just as well, or even better, than using all the data.
  • The Check: They compared the real quantum computer results with a perfect, noise-free simulation. They matched very closely, proving the real hardware works as expected.

• Scenario B: The Spambase Dataset (Email)

  • The Task: Tell if an email is spam or not, based on 32 word/character frequencies.
  • The Outcome: The quantum method reduced the list to 23 key indicators. Again, it outperformed the standard methods. It managed to cut out the "noise" (redundant words) while keeping the "signal" (words that actually indicate spam).

5. The Bottom Line

The paper claims that:

1. It works: The quantum computer successfully found high-quality subsets of data.
2. It's better than the old way: By looking at "three-way" relationships (higher-order), it found better combinations than methods that only look at individuals or pairs.
3. It's efficient: It reduced the amount of data needed to make accurate predictions without losing accuracy.
4. Hardware is ready: The results from the real IonQ machine were very similar to the perfect simulations, suggesting that today's quantum computers are already capable of handling these complex "group dynamics" problems.

In short, the authors built a quantum "scout" that is better at spotting the most valuable team members in a group because it understands how people interact in threes, not just in pairs. They proved it works on real hardware with real data.

Technical Summary

1. Problem Statement

Feature selection (FS) is critical for improving model interpretability, reducing overfitting, and enhancing computational efficiency in high-dimensional datasets. However, classical FS methods face significant limitations:

• Wrapper methods are computationally expensive and scale poorly.
• Filter methods (e.g., mutual information) often ignore feature interactions.
• Embedded methods are sensitive to hyperparameters and often bias toward linear or hierarchical dependencies.
• Quantum Limitations: Existing quantum approaches typically formulate FS as a Quadratic Unconstrained Binary Optimization (QUBO) problem. QUBO is restricted to one- and two-body interactions, forcing higher-order dependencies (multivariate relationships) to be neglected, approximated, or introduced via costly quadratization overheads.

Core Challenge: How to explicitly capture complex, higher-order statistical dependencies among features in a quantum optimization framework without reducing the problem to a quadratic form, and how to execute this on current noisy intermediate-scale quantum (NISQ) hardware.

2. Methodology

The authors propose a novel framework based on Higher-Order Unconstrained Binary Optimization (HUBO) executed on IonQ Forte trapped-ion hardware.

A. HUBO Formulation

Instead of a quadratic Hamiltonian, the problem is encoded in a Hamiltonian containing one-, two-, and three-body interaction terms:
$$H(Z) = \sum_i h_i Z_i + \sum_{i<j} J_{ij} Z_i Z_j + \sum_{i<j<k} K_{ijk} Z_i Z_j Z_k + C$$

• Variables: $Z_i \in \{-1, +1\}$ (Ising convention), where $-1$ indicates feature selection.
• Coefficients: Derived from Mutual Information (MI):
  • $h_i$: Encodes individual feature relevance to the target.
  • $J_{ij}$: Encodes pairwise redundancy (penalizing correlated features).
  • $K_{ijk}$: Encodes higher-order dependencies (capturing information present only in groups of three features).
• Structured Penalties: To prevent trivial solutions (e.g., selecting all features), a linear penalty term $H_\lambda$ is added, suppressing features with negligible relevance below a threshold $\tau$.

B. Optimization Algorithm: Digitized Counterdiabatic Quantum Optimization (DCQO)

The authors utilize DCQO to find the ground state of the HUBO Hamiltonian:

• Mechanism: A gate-based approach inspired by "shortcuts to adiabaticity." It interpolates between a driver Hamiltonian and the target HUBO Hamiltonian while adding approximate counterdiabatic terms to suppress diabatic transitions during finite-time evolution.
• Execution: Implemented on IonQ Forte (Yb+ ions) with all-to-all connectivity, which naturally supports the long-range interactions required by HUBO without complex embedding.

C. Post-Processing and Selection

1. Sampling: The system is measured to generate bitstring samples.
2. Filtering: Samples are ranked by energy; only the lowest-energy fraction ($\rho$, e.g., top 25%) is retained to filter out noise.
3. Scoring: Feature importance ($I_i$) is calculated as the empirical frequency of a feature being selected ($x_i=1$) within the low-energy subset.
4. Thresholding: Features are selected if $I_i \geq \delta$.

3. Key Contributions

1. HUBO for Feature Selection: The first explicit formulation of feature selection as a HUBO problem that captures three-body interactions directly, avoiding the information loss inherent in QUBO reductions.
2. Hardware Implementation: Successful execution of a higher-order optimization problem on IonQ Forte trapped-ion hardware, demonstrating the feasibility of running deep quantum circuits for machine learning preprocessing.
3. Model Independence: The method relies purely on statistical dependencies (Mutual Information) derived from data, requiring no model training during the selection phase.
4. Benchmarking: Comprehensive comparison against noiseless quantum simulations and classical baselines (SelectKBest and PCA) on real-world datasets.

4. Experimental Results

The framework was tested on two datasets: Gallstone (biomedical, 38 features) and Spambase (textual, 57 features). Both were pre-selected to 32 features for hardware constraints.

A. Gallstone Dataset

• Hardware vs. Simulation: Strong qualitative agreement between IonQ Forte and noiseless simulation regarding feature inclusion probabilities.
• Performance: The quantum-selected subset (19 features) achieved 0.88 ROC-AUC, outperforming:
  • All features (0.86)
  • PCA (0.79)
  • SelectKBest (0.84)
• Insight: The inclusion of higher-order terms allowed the model to identify a more compact and informative subset than univariate methods.

B. Spambase Dataset

• Performance: The quantum-selected subset (23 features) achieved 0.9836 ROC-AUC, surpassing:
  • All features (0.9817)
  • PCA (0.9615)
  • SelectKBest (0.9805)
• Efficiency: The method reduced dimensionality by ~28% while slightly improving classification accuracy compared to using all features.

5. Significance and Conclusion

• Beyond Quadratic: The study proves that explicitly modeling higher-order statistical structures (via 3-body terms) yields better feature subsets than standard quadratic (QUBO) approaches, particularly in datasets with complex multivariate dependencies.
• Hardware Suitability: Trapped-ion processors are uniquely suited for HUBO problems due to their all-to-all connectivity, which eliminates the need for qubit mapping/embedding overheads common in superconducting architectures.
• Scalability: The results suggest that as quantum hardware scales (more qubits, higher fidelity), this approach can tackle high-dimensional feature selection problems that are computationally intractable for classical combinatorial methods.
• Future Work: The authors propose integrating Bias-Field DCQO (BF-DCQO) to iteratively update bias fields, further enhancing the optimization landscape for larger datasets.

In summary, this paper demonstrates a practical, model-agnostic quantum workflow that leverages higher-order optimization on trapped-ion hardware to outperform classical dimensionality reduction techniques in both feature compactness and predictive performance.