QUBO formulations for training machine learning models

Abstract Training machine learning models on classical computers is usually a time and compute intensive process. With Moore’s law nearing its inevitable end and an ever-increasing demand for large-scale data analysis using machine learning, we must leverage non-conventional computing paradigms like...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Prasanna Date, Davis Arthur, Lauren Pusey-Nazzaro
Formato:	article
Lenguaje:	EN
Publicado:	Nature Portfolio 2021
Materias:	Medicine R Science Q
Acceso en línea:	https://doaj.org/article/0f4a394dc22c4a0abd0c90c1171774d0
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:0f4a394dc22c4a0abd0c90c1171774d0
record_format	dspace
spelling	oai:doaj.org-article:0f4a394dc22c4a0abd0c90c1171774d02021-12-02T17:01:57ZQUBO formulations for training machine learning models10.1038/s41598-021-89461-42045-2322https://doaj.org/article/0f4a394dc22c4a0abd0c90c1171774d02021-05-01T00:00:00Zhttps://doi.org/10.1038/s41598-021-89461-4https://doaj.org/toc/2045-2322Abstract Training machine learning models on classical computers is usually a time and compute intensive process. With Moore’s law nearing its inevitable end and an 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 can approximately solve NP-hard 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 problems on adiabatic quantum computers, they must be formulated as QUBO problems, which is very challenging. In this paper, we formulate the training problems of three machine learning models—linear regression, support vector machine (SVM) and balanced k-means clustering—as QUBO problems, making them conducive to be trained on adiabatic quantum computers. We also analyze the computational complexities of our formulations and compare them to corresponding state-of-the-art classical approaches. We show that the time and space complexities of our formulations are better (in case of SVM and balanced k-means clustering) or equivalent (in case of linear regression) to their classical counterparts.Prasanna DateDavis ArthurLauren Pusey-NazzaroNature PortfolioarticleMedicineRScienceQENScientific Reports, Vol 11, Iss 1, Pp 1-10 (2021)
institution	DOAJ
collection	DOAJ
language	EN
topic	Medicine R Science Q
spellingShingle	Medicine R Science Q Prasanna Date Davis Arthur Lauren Pusey-Nazzaro QUBO formulations for training machine learning models
description	Abstract Training machine learning models on classical computers is usually a time and compute intensive process. With Moore’s law nearing its inevitable end and an 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 can approximately solve NP-hard 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 problems on adiabatic quantum computers, they must be formulated as QUBO problems, which is very challenging. In this paper, we formulate the training problems of three machine learning models—linear regression, support vector machine (SVM) and balanced k-means clustering—as QUBO problems, making them conducive to be trained on adiabatic quantum computers. We also analyze the computational complexities of our formulations and compare them to corresponding state-of-the-art classical approaches. We show that the time and space complexities of our formulations are better (in case of SVM and balanced k-means clustering) or equivalent (in case of linear regression) to their classical counterparts.
format	article
author	Prasanna Date Davis Arthur Lauren Pusey-Nazzaro
author_facet	Prasanna Date Davis Arthur Lauren Pusey-Nazzaro
author_sort	Prasanna Date
title	QUBO formulations for training machine learning models
title_short	QUBO formulations for training machine learning models
title_full	QUBO formulations for training machine learning models
title_fullStr	QUBO formulations for training machine learning models
title_full_unstemmed	QUBO formulations for training machine learning models
title_sort	qubo formulations for training machine learning models
publisher	Nature Portfolio
publishDate	2021
url	https://doaj.org/article/0f4a394dc22c4a0abd0c90c1171774d0
work_keys_str_mv	AT prasannadate quboformulationsfortrainingmachinelearningmodels AT davisarthur quboformulationsfortrainingmachinelearningmodels AT laurenpuseynazzaro quboformulationsfortrainingmachinelearningmodels
_version_	1718381950529437696

QUBO formulations for training machine learning models

Ejemplares similares