The problem of selecting an appropriate number of features in supervised learning problems is investigated in this paper. Starting with common methods in machine learning, we treat the feature selection task as a quadratic unconstrained optimization problem (QUBO), which can be tackled with classical numerical methods as well as within a quantum computing framework. We compare the different results in small-sized problem setups. According to the results of our study, whether the QUBO method outperforms other feature selection methods depends on the data set. In an extension to a larger data set with 27 features, we compare the convergence behavior of the QUBO methods via quantum computing with classical stochastic optimization methods. Due to persisting error rates, the classical stochastic optimization methods are still superior.
The problem of selecting an appropriate number of features in supervised learning problems is investigated in this paper. Starting with common methods in machine learning, we treat the feature selection task as a quadratic unconstrained optimization problem (QUBO), which can be tackled with classical numerical methods as well as within a quantum computing framework. We compare the different results in small-sized problem setups. According to the results of our study, whether the QUBO method outperforms other feature selection methods depends on the data set. In an extension to a larger data set with 27 features, we compare the convergence behavior of the QUBO methods via quantum computing with classical stochastic optimization methods. Due to persisting error rates, the classical stochastic optimization methods are still superior.
Abstract The problem of selecting an appropriate number of features in supervised learning problems is investigated. Starting with common methods in machine learning, the feature selection task is treated as a quadratic unconstrained optimisation problem (QUBO), which can be tackled with classical numerical methods as well as within a quantum computing framework. The different results in small problem instances are compared. According to the results of the authors’ study, whether the QUBO method outperforms other feature selection methods depends on the data set. In an extension to a larger data set with 27 features, the authors compare the convergence behaviour of the QUBO methods via quantum computing with classical stochastic optimisation methods. Due to persisting error rates, the classical stochastic optimisation methods are still superior.
Abstract In machine learning, fewer features reduce model complexity. Carefully assessing the influence of each input feature on the model quality is therefore a crucial preprocessing step. We propose a novel feature selection algorithm based on a quadratic unconstrained binary optimization (QUBO) problem, which allows to select a specified number of features based on their importance and redundancy. In contrast to iterative or greedy methods, our direct approach yields higher-quality solutions. QUBO problems are particularly interesting because they can be solved on quantum hardware. To evaluate our proposed algorithm, we conduct a series of numerical experiments using a classical computer, a quantum gate computer, and a quantum annealer. Our evaluation compares our method to a range of standard methods on various benchmark data sets. We observe competitive performance.
Feature selection plays an important role in improving the efficiency of machine learning models for credit card fraud and default detection. We formulate the feature selection problem as a Quadratic Unconstrained Binary Optimization (QUBO) problem, which we solve using quantum annealers. We propose three new formulations based on this framework that improve the efficiency and flexibility of machine learning models. We benchmark the proposed methods, existing approaches from the literature, and also compare with classical feature-selection methods such as Random Forest feature importance and a combination of mutual information and Spearman correlation. Extensive experiments show that feature selection using quantum computers consistently performs better than the classical methods. Our experiments show the promise of using quantum computers in machine learning tasks in financial risk assessment applications.
This paper explores the applications of quantum annealing (QA) and classical simulated annealing (SA) to a suite of combinatorial optimization problems in machine learning, namely feature selection, instance selection, and clustering. We formulate each task as a Quadratic Unconstrained Binary Optimization (QUBO) problem and implement both quantum and classical solvers to compare their effectiveness. For feature selection, we propose several QUBO configurations that balance feature importance and redundancy, showing that quantum annealing (QA) produces solutions that are computationally more efficient. In instance selection, we propose a few novel heuristics for instance-level importance measures that extend existing methods. For clustering, we embed a classical-to-quantum pipeline, using classical clustering followed by QUBO-based medoid refinement, and demonstrate consistent improvements in cluster compactness and retrieval metrics. Our results suggest that QA can be a competitive and efficient tool for discrete machine learning optimization, even within the constraints of current quantum hardware.
Leveraging quantum computers for optimization problems holds promise across various application domains. Nevertheless, utilizing respective quantum computing solvers requires describing the optimization problem according to the Quadratic Unconstrained Binary Optimization (QUBO) formalism and selecting a proper solver for the application of interest with a reasonable setting. Both demand significant proficiency in quantum computing, QUBO formulation, and quantum solvers, a background that usually cannot be assumed by end users who are domain experts rather than quantum computing specialists. While tools aid in QUBO formulations, support for selecting the best-solving approach remains absent. This becomes even more challenging because selecting the best solver for a problem heavily depends on the problem itself. In this work, we are accepting this challenge and propose a predictive selection approach, which aids end users in this task. To this end, the solver selection task is first formulated as a classification task that is suitable to be solved by supervised machine learning. Based on that, we then propose strategies for adjusting solver parameters based on problem size and characteristics. Experimental evaluations, considering more than 500 different QUBO problems, confirm the benefits of the proposed solution. In fact, we show that in more than 70% of the cases, the best solver is selected, and in about 90% of the problems, a solver in the top two, i.e., the best or its closest suboptimum, is selected. This exploration proves the potential of machine learning in quantum solver selection and lays the foundations for its automation, broadening access to quantum optimization for a wider range of users. The pre-trained classifier is integrated into the MQT Quantum Auto Optimizer (MQT QAO) framework, publicly available on GitHub (https://github.com/cda-tum/mqt-qao) as part of the Munich Quantum Toolkit (MQT).
Feature selection is an essential step for reducing complexity of high dimensional data, usually in preparation for developing machine learning models such as computational biomarkers. However, there are limitations associated with feature selection such as for metabolomic data where there are hundreds or even thousands of features per study participant, while the available number of participants in a clinical trials is limited. Classical methods such as exhaustive search require evaluation of all possible feature combinations, making them costly in terms of computation and runtime, or even infeasible, as feature dimensionality increases. In this study, we propose a novel Quadratic Unconstrained Binary Optimization (QUBO) coefficient formulation and pose metabolomic feature selection as a QUBO problem that selects a specified number of features by balancing their relevance against redundancy among the selected variables. To evaluate our proposed QUBO objective function, we conducted a series of experiments using Bias-Field Digitized Counterdiabatic Quantum Optimization (BF-DCQO) and Quantum Approximate Optimization Algorithm (QAOA) on a quantum gate based computer. We also compared the method to several classical methods on three metabolomic datasets associated with Autism Spectrum Disorder (ASD) on a classical computer. Our method reduces runtime compared with exhaustive search and Iterative Tabu Search (ITS) and achieves competitive performance across classifiers compared to classical filter, wrapper, and embedded methods. These results do not claim quantum advantage; rather, they establish hardware feasibility and demonstrate the current capabilities of Noisy Intermediate-Scale Quantum (NISQ) devices.