QUBO formulations for training machine learning models.

Area of Science:

• Quantum Computing
• Machine Learning
• Computational Complexity

Background:

• Classical machine learning training is computationally intensive.
• Moore's Law limitations necessitate novel computing approaches.
• Quantum computing, particularly adiabatic quantum computing, shows promise for complex problem-solving.

Purpose of the Study:

• To reformulate machine learning training problems for adiabatic quantum computers.
• To explore the potential of quantum computing in addressing the computational demands of machine learning.
• To analyze and compare the computational complexity of quantum-enhanced machine learning algorithms with classical methods.

Main Methods:

• Formulation of linear regression, support vector machine (SVM), and balanced k-means clustering training as Quadratic Unconstrained Binary Optimization (QUBO) problems.
• Analysis of the computational time and space complexities of the proposed QUBO formulations.
• Comparison of the quantum formulations' complexities against state-of-the-art classical algorithms.

Main Results:

• Successfully formulated training for linear regression, SVM, and balanced k-means as QUBO problems.
• Demonstrated that the proposed quantum formulations offer better or equivalent time and space complexities compared to classical approaches for SVM, balanced k-means, and linear regression, respectively.
• Established the feasibility of using adiabatic quantum computers for efficient machine learning model training.

Conclusions:

• Adiabatic quantum computers can efficiently train machine learning models by leveraging QUBO formulations.
• Quantum computing presents a viable path for machine learning in the post-Moore's Law era.
• The proposed QUBO formulations pave the way for practical quantum machine learning applications.