Deep Learning approaches have become pervasive in recent years due to their ability to solve complex tasks. However, these models need huge datasets for proper training and good generalization. This translates into high training and fine-tuning time, even several days for the most complex models and large datasets. In this work, we present a novel quantum Instance Selection (IS) approach that allows to significantly reduce the size of the training datasets (by up to 28%) while maintaining the model's effectiveness, thus promoting (training) speedups and scalability. Our solution is innovative in the sense that it exploits a different computing paradigm - Quantum Annealing (QA) - a specific Quantum Computing paradigm that can be used to tackle optimization problems. To the best of our knowledge, there have been no prior attempts to tackle the IS problem using QA. Furthermore, we propose a new Quadratic Unconstrained Binary Optimization formulation specific for the IS problem, which is a contribution in itself. Through an extensive set of experiments with several Text Classification benchmarks, we empirically demonstrate our quantum solution's feasibility and competitiveness with the current state-of-the-art IS solutions.
Deep Learning approaches have become pervasive in recent years due to their ability to solve complex tasks. However, these models need huge datasets for proper training and good generalization. This translates into high training and fine-tuning time, even several days for the most complex models and large datasets. In this work, we present a novel quantum Instance Selection (IS) approach that allows to significantly reduce the size of the training datasets (by up to 28%) while maintaining the model's effectiveness, thus promoting (training) speedups and scalability. Our solution is innovative in the sense that it exploits a different computing paradigm - Quantum Annealing (QA) - a specific Quantum Computing paradigm that can be used to tackle optimization problems. To the best of our knowledge, there have been no prior attempts to tackle the IS problem using QA. Furthermore, we propose a new Quadratic Unconstrained Binary Optimization formulation specific for the IS problem, which is a contribution in itself. Through an extensive set of experiments with several Text Classification benchmarks, we empirically demonstrate our quantum solution's feasibility and competitiveness with the current state-of-the-art IS solutions.
Abstract Instance selection algorithms for supervised classification and regression tasks in machine learning aim to reduce the size of training datasets whilst maintaining the performance of models by selecting the most important, high-fidelity training labels from a large pool of instances in the original datasets. Traditional instance selection methods such as cluster-based techniques demonstrate enhanced generalization capabilities on fewer data points compared with random sampling approaches, but often suffer from high computational costs, sensitivity to hyperparameters and non-deterministic time complexities. This paper proposes QReduce which is a novel instance selection algorithm which models datasets as N-dimensional graphs with each data point corresponding to a vertex and edges constructed between points in a k-nearest neighbour manner. This graph is subjected to quantum annealing to solve the minimum vertex cover or maximum cut graph combinatorial optimization problems and yield a subgraph representing the reduced subset of instances selected for the reduced dataset. Solving such NP-hard problems are intractable for exact classical solvers on account of combinatorial explosion of the problem’s search space, and quantum annealing was shown to outperform other approximate metaheuristic techniques such as simulated annealing, justifying it as a strong metaheuristic optimization model. QReduce enables recursive reduction of the dataset and has the benefits of less sensitivity to hyperparameters as well as a deterministic time complexity, enabling efficient and effective reduction in storage and compute requirements for training complex machine learning models in the age of green and sustainable AI. Experimental results demonstrate the efficacy of QReduce, outperforming existing instance selection techniques and having the highest average percentage data reduction to percentage accuracy reduction ratios on datasets for both classification and regression tasks, thereby making it a best-in-class instance selection algorithm for selecting high-fidelity training labels in supervised machine learning tasks.
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.
This paper proposes an integrated QUBO-based quantum-annealing optimization framework for next-generation cloud computing. First, for resource-demand forecasting, we blend Autoregressive (AR) models with Quadratic Unconstrained Binary Optimization (QUBO) and solve the resulting problem via Simulated Annealing; monthly-scale tests reveal superior trend-capture accuracy compared with classical predictors. Second, we embed quantum optimization into Support Vector Machines by casting kernel selection and penalty-parameter tuning as QUBO instances; evaluations on the Iris benchmark—and on synthetically enlarged variants—show marked gains in both classification accuracy and training speed, especially under large-data regimes. Third, we extend the same paradigm to deep learning: a QUBO-formulated quantum-annealing routine optimizes weight initialization and layer-wise learning rates in convolutional networks for image classification, yielding higher top-1 accuracy and reduced wall-clock training time. Across all tasks the hybrid quantum-classical solver consistently outperforms its classical counterparts while maintaining linear scalability in cloud environments. These results show the practical potential of quantum - enhanced algorithms for resource prediction, classification, and deep learning, and pave the way for wider use of quantum technologies in cloud - based AI services.
Abstract The field of Quantum Computing has gathered significant popularity in recent years and a large number of papers have studied its effectiveness in tackling many tasks. We focus in particular on Quantum Annealing (QA), a meta-heuristic solver for Quadratic Unconstrained Binary Optimization (QUBO) problems. It is known that the effectiveness of QA is dependent on the task itself, as is the case for classical solvers, but there is not yet a clear understanding of which are the characteristics of a problem that make it difficult to solve with QA. In this work, we propose a new methodology to study the effectiveness of QA based on meta-learning models. To do so, we first build a dataset composed of more than five thousand instances of ten different optimization problems. We define a set of more than a hundred features to describe their characteristics and solve them with both QA and three classical solvers. We publish this dataset online for future research. Then, we train multiple meta-models to predict whether QA would solve that instance effectively and use them to probe which features with the strongest impact on the effectiveness of QA. Our results indicate that it is possible to accurately predict the effectiveness of QA, validating our methodology. Furthermore, we observe that the distribution of the problem coefficients representing the bias and coupling terms is very informative in identifying the probability of finding good solutions, while the density of these coefficients alone is not enough. The methodology we propose allows to open new research directions to further our understanding of the effectiveness of QA, by probing specific dimensions or by developing new QUBO formulations that are better suited for the particular nature of QA. Furthermore, the proposed methodology is flexible and can be extended or used to study other quantum or classical solvers.
The recent availability of quantum annealers as cloud-based services has enabled new ways to handle machine learning problems, and several relevant algorithms have been adapted to run on these devices. In a recent work, linear regression was formulated as a quadratic binary optimization problem that can be solved via quantum annealing. Although this approach promises a computational time advantage for large datasets, the quality of the solution is limited by the necessary use of a precision vector, used to approximate the real-numbered regression coefficients in the quantum formulation. In this work, we focus on the practical challenge of improving the precision vector encoding: instead of setting an array of generic values equal for all coefficients, we allow each one to be expressed by its specific precision, which is tuned with a simple adaptive algorithm. This approach is evaluated on synthetic datasets of increasing size, and linear regression is solved using the D-Wave Advantage quantum annealer, as well as classical solvers. To the best of our knowledge, this is the largest dataset ever evaluated for linear regression on a quantum annealer. The results show that our formulation is able to deliver improved solution quality in all instances, and could better exploit the potential of current quantum devices.
Quantum computing offers new paradigms in machine learning, notably through Quantum Annealing (QA), which offers promising approaches to optimization problems. This study introduces an application of Multi-tasking Quantum Annealing (MTQA) to enhance multi-class Support Vector Machines (SVMs). Traditional QA methods require multiple cycles to classify multi-class datasets, significantly increasing computational demands. In contrast, MTQA embeds multiple SVM classifiers in parallel on a quantum annealer, thereby reducing the number of required annealing cycles to a single cycle. Utilizing the D-Wave Advantage 6.4 system, we evaluated our method across three benchmark datasets: a synthetic dataset (Blob), subsets of handwritten digits, and the Iris dataset with different feature focuses. Our findings demonstrate that MTQA achieves accuracy equivalent to that of classical Sequential Minimal Optimization (SMO), Simulated Annealing (SA), and standard QA methods while significantly improving computational efficiency. Despite the current limitations in quantum technology and the empirical selection of model parameters, these results highlight the emergent potential of quantum computing in machine learning. Further advancements in quantum algorithm optimization and parameter tuning are anticipated to enhance the efficacy of QA and MTQA, solidifying their practical application roles.