# QUBO Formulations for Training Machine Learning Models

arXiv: https://arxiv.org/abs/2008.02369 · HTML: https://mlsanity.com/paper/2008.02369/

## Key facts

- Cited by 33 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Aug 2020.

## Built on by (most cited first, 30 of 33)

- [Feature Selection on Quantum Computers](https://mlsanity.com/paper/2203.13261/) (2022)
- [Q-FW: A Hybrid Classical-Quantum Frank-Wolfe for Quadratic Binary Optimization](https://mlsanity.com/paper/2203.12633/) (2022)
- [Sparks of Quantum Advantage and Rapid Retraining in Machine Learning](https://mlsanity.com/paper/2407.16020/) (2024)
- [Implementation of Trained Factorization Machine Recommendation System on Quantum Annealer](https://mlsanity.com/paper/2210.12953/) (2022)
- [Quantum Sparse Coding](https://mlsanity.com/paper/2209.03788/) (2022)
- [Accelerating the training of single-layer binary neural networks using the HHL quantum algorithm](https://mlsanity.com/paper/2210.12707/) (2022)
- [Probabilistic Sampling of Balanced K-Means using Adiabatic Quantum Computing](https://mlsanity.com/paper/2310.12153/) (2023)
- [Projected Stochastic Gradient Descent with Quantum Annealed Binary Gradients](https://mlsanity.com/paper/2310.15128/) (2023)
- [Training Multi-layer Neural Networks on Ising Machine](https://mlsanity.com/paper/2311.03408/) (2023)
- [Evaluating the Potential of Quantum Machine Learning in Cybersecurity: A Case-Study on PCA-based Intrusion Detection Systems](https://mlsanity.com/paper/2502.11173/) (2025)
- [Discriminating Quantum States with Quantum Machine Learning](https://mlsanity.com/paper/2112.00313/) (2021)
- [QUBO Decision Tree: Annealing Machine Extends Decision Tree Splitting](https://mlsanity.com/paper/2303.09772/) (2023)
- [Is Quantum Optimization Ready? An Effort Towards Neural Network Compression using Adiabatic Quantum Computing](https://mlsanity.com/paper/2505.16332/) (2025)
- [Adiabatic Quantum Feature Selection for Sparse Linear Regression](https://mlsanity.com/paper/2106.02357/) (2021)
- [Hyperparameter optimization, quantum-assisted model performance prediction, and benchmarking of AI-based High Energy Physics workloads using HPC](https://mlsanity.com/paper/2303.15053/) (2023)
- [Solving the Traveling Salesman Problem via Different Quantum Computing Architectures](https://mlsanity.com/paper/2502.17725/) (2025)
- [Probabilistic Quantum SVM Training on Ising Machine](https://mlsanity.com/paper/2503.16363/) (2025)
- [Quantum Annealing for Machine Learning: Applications in Feature Selection, Instance Selection, and Clustering](https://mlsanity.com/paper/2507.15063/) (2025)
- [Subsampling Factorization Machine Annealing](https://mlsanity.com/paper/2508.08778/) (2025)
- [QUBOs for Sorting Lists and Building Trees](https://mlsanity.com/paper/2203.08815/) (2022)
- [QUBO-inspired Molecular Fingerprint for Chemical Property Prediction](https://mlsanity.com/paper/2303.10179/) (2023)
- [A general learning scheme for classical and quantum Ising machines](https://mlsanity.com/paper/2310.18411/) (2023)
- [A Simple Quantum Blockmodeling with Qubits and Permutations](https://mlsanity.com/paper/2311.07726/) (2023)
- [Adiabatic Quantum Support Vector Machines](https://mlsanity.com/paper/2401.12485/) (2024)
- [Hybrid Heuristic Algorithms for Adiabatic Quantum Machine Learning Models](https://mlsanity.com/paper/2407.21062/) (2024)
- [Performance-Driven QUBO for Recommender Systems on Quantum Annealers](https://mlsanity.com/paper/2410.15272/) (2024)
- [QUBO-based training for VQAs on Quantum Annealers](https://mlsanity.com/paper/2509.01821/) (2025)
- [On the Impact of Weight Discretization in QUBO-Based SVM Training](https://mlsanity.com/paper/2510.26323/) (2025)
- [Quadratic Unconstrained Binary Optimisation for Training and Regularisation of Binary Neural Networks](https://mlsanity.com/paper/2601.00449/) (2026)
- [Exploiting Low-Rank Objective Structure in Discrete Quadratic Optimization](https://mlsanity.com/paper/2602.20376/) (2026)

## Abstract (arXiv)

Training machine learning models on classical computers is usually a time and compute intensive process. With Moore's law coming to an end and ever increasing demand for large-scale data analysis using machine learning, we must leverage non-conventional computing paradigms like quantum computing to train machine learning models efficiently. Adiabatic quantum computers like the D-Wave 2000Q can approximately solve NP-hard optimization problems, such as the quadratic unconstrained binary optimization (QUBO), faster than classical computers. Since many machine learning problems are also NP-hard, we believe adiabatic quantum computers might be instrumental in training machine learning models efficiently in the post Moore's law era. In order to solve a problem on adiabatic quantum computers, it must be formulated as a QUBO problem, which is a challenging task in itself. In this paper, we formulate the training problems of three machine learning models---linear regression, support vector machine (SVM) and equal-sized k-means clustering---as QUBO problems so that they can be trained on adiabatic quantum computers efficiently. We also analyze the time and space complexities of our formulations and compare them to the state-of-the-art classical algorithms for training these machine learning models. We show that the time and space complexities of our formulations are better (in the case of SVM and equal-sized k-means clustering) or equivalent (in case of linear regression) to their classical counterparts.