QUBO Formulations for Training Machine Learning Models
  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.
