Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1906.03834

Quantum algorithm for logistic regression

Hailing Liu, Chao‐Hua Yu, Yusen Wu, Shi‐Jie Pan, Su‐Juan Qin, Fei Gao, Qiaoyan Wen

Published Jun 10, 2019• 7 citations
arXivHTMLPDF

Abstract

Logistic regression (LR) is an important machine learning model for classification, with wide applications in text classification, image analysis and medicine diagnosis, etc. However, training LR generally entails an iterative gradient descent method, and is quite time consuming when processing big data sets. To solve this problem, we present a quantum algorithm for LR to implement the key task of the gradient descent method, obtaining the classical gradients in each iteration. It is shown that our algorithm achieves exponential speedup over its classical counterpart in each iteration when the dimension of each data point M grows polylogarithmically with the number of data points N, i.e.,M=O(polylog N). It is worth noting that the optimal model parameters are finally derived by performing simple calculations on the obtained gradients. So once the optimal model parameters are determined, one can use them to classify new data at little cost.

DOI
10.48550/arxiv.1906.03834

Related papers

Hybrid Quantum Logistic Regression Model with Amplitude Data Encoding

Petro A. Kravets

This paper presents a hybrid quantum logistic regression model for binary data classification that combines classical logistic regression methods with quantum computing to improve efficiency and speed up the learning process. Quantum computing is used to represent and process feature and weight vectors as quantum states and to efficiently compute the dot product underlying the logistic function. The use of normalized amplitude coding allows for compact representation of feature vectors and weights, reducing the number of qubits required and potentially speeding up computations for high-dimensional classification problems where classical methods may encounter scalability limitations. The quantum dot product computation is performed using the Hadamard test, which provides a statistical estimate of the probability of measuring an auxiliary qubit. The auxiliary qubit is first put into a superposition state, and after performing controlled unitary operations, amplitude interference is formed, which depends on the scalar product of the feature vector and weight coefficients. The obtained measurement probability is used to estimate the scalar product of the feature vectors and weights. The classical part of the model provides for the execution of operations that are difficult to implement on modern quantum devices, in particular, vector normalization, application of the sigmoid function to estimate the probability of an object belonging to a certain class, calculation of the loss function and iterative update of weight coefficients by the gradient descent method. The purpose of classification is to predict the binary class for an unknown sample based on the training sample. To demonstrate the model, a numerical example is given with a step-by-step calculation of one iteration of logistic regression training. In addition, computer modeling of the hybrid algorithm training process was performed, taking into account the influence of noise on the results of quantum state measurements. A quantum noise model was developed based on the probability of confidence in the measurement result, which is interpreted as an assessment of its reliability in a Bernoulli experiment. Comparison of the obtained results with the classical approach confirms the practical suitability of the hybrid algorithm for binary classification problems. The hybrid model preserves the key properties of classical logistic regression – parameter interpretability and optimization stability, while allowing for the use of quantum advantages for compact data encoding and scalar product computation. This makes the study of hybrid logistic regression relevant for the development of machine learning algorithms on modern quantum platforms.

Vìsnik Nacìonalʹnogo unìversitetu Lʹvìvsʹka polìtehnìka Serìâ Ìnformacìjnì sistemi ta merežì•May 17, 2026•0 citations

Quantum Algorithm for Sparse Online Learning with Truncated Gradient Descent

Debbie Lim, Yixian Qiu, Patrick Rebentrost +1 more

Logistic regression, the Support Vector Machine (SVM), and least squares are well-studied methods in the statistical and computer science community, with various practical applications. High-dimensional data arriving on a real-time basis makes the design of online learning algorithms that produce sparse solutions essential. The seminal work of \hyperlink{cite.langford2009sparse}{Langford, Li, and Zhang (2009)} developed a method to obtain sparsity via truncated gradient descent, showing a near-optimal online regret bound. Based on this method, we develop a quantum sparse online learning algorithm for logistic regression, the SVM, and least squares. Given efficient quantum access to the inputs, we show that a quadratic speedup in the time complexity with respect to the dimension of the problem is achievable, while maintaining a regret of $O(1/\sqrt{T})$, where $T$ is the number of iterations.

arXiv:2411.03925•Nov 6, 2024•0 citations

A quantum gradient descent algorithm for optimizing Gaussian process models

Junpeng Hu, Jinglai Li, Lei Zhang +1 more

Gaussian process regression (GPR) is a nonparametric supervised learning method, widely valued for its ability to quantify uncertainty. Despite its advantages and broad applications, classical GPR implementations face significant scalability challenges, as they involve matrix operations with a cubic complexity in relation to the dataset size. This computational challenge is further compounded by the demand of optimizing the Gaussian Process (GP) model over its hyperparameters, rendering the total computational cost prohibitive for data intensive problems. To address this issue, we propose a quantum gradient descent algorithm to optimize the GP model. Taking advantage of recent advances in quantum algorithms for linear algebra, our algorithm achieves exponential speedup in computing the gradients of the log marginal likelihood. The entire gradient descent process is integrated into the quantum circuit. Through runtime analysis and error bounds, we demonstrate that our approach significantly improves the scalability of GPR model optimization, making it computationally feasible for large-scale applications.

arXiv:2503.17780•Mathematical Models and Methods in Applied Sciences•Apr 1, 2026•1 citation

Quantum Support Vector Machine for Big Data Classification

Patrick Rebentrost, Masoud Mohseni, Seth Lloyd

Supervised machine learning is the classification of new data based on already classified training examples. In this work, we show that the support vector machine, an optimized binary classifier, can be implemented on a quantum computer, with complexity logarithmic in the size of the vectors and the number of training examples. In cases where classical sampling algorithms require polynomial time, an exponential speedup is obtained. At the core of this quantum big data algorithm is a nonsparse matrix exponentiation technique for efficiently performing a matrix inversion of the training data inner-product (kernel) matrix.

arXiv:1307.0471•Physical Review Letters•Sep 25, 2014•1,951 citations

Application of Quantum Gradient Descent as a Learning Algorithm for Factorization Machines

Narges Alavi Samani, Hossein Aghababa

Gradient Descent is an optimization algorithm used for finding the minima of a function. It moves along the function with steps proportional to the negative of the gradient. Quantum version of this algorithm has the advantage of exponential speedup for problems with high dimensional inputs. On the other hand, Factorization Machines (FMs) are modeling classes with important advantages in comparison with other modeling ones such as SVMs. They, in contrast to SVMs, use factorized parameters in order to model all interactions between variables. Accordingly, unlike SVMs, they can estimate interactions in problems with large sparsity. In this work, we show that Factorization Machine can be implemented on quantum computers, using quantum gradient descent to learn the parameters of a FM. The parameters we have chosen to learn via quantum gradient descent is a bottleneck in learning parameters of a FM. Our proposed idea results in time computational complexity O(k polylog n) where k and n are the dimensions of the parameter matrix. By doing so and under some constraints on the dimensions, an exponential speedup over classical algorithms can be obtained.

Hellenic Conference on Artificial Intelligence•Jul 6, 2018•3 citations

Quantum gradient descent for linear systems and least squares

Iordanis Kerenidis, Anupam Prakash

Quantum machine learning and optimization are exciting new areas that have been brought forward by the breakthrough quantum algorithm of Harrow, Hassidim, and Lloyd for solving systems of linear equations. The utility of classical linear system solvers extends beyond linear algebra as they can be leveraged to solve optimization problems using iterative methods like gradient descent. In this work, we provide a quantum method for performing gradient descent when the gradient is an affine function. Performing $\ensuremath{\tau}$ steps of the gradient descent requires time $O(\ensuremath{\tau}{C}_{S})$ for weighted least-squares problems, where ${C}_{S}$ is the cost of performing one step of the gradient descent quantumly, which at times can be considerably smaller than the classical cost. We illustrate our method by providing two applications: first, for solving positive semidefinite linear systems, and, second, for performing stochastic gradient descent for the weighted least-squares problem with reduced quantum memory requirements. We also provide a quantum linear system solver in the QRAM data structure model that provides significant savings in cost for large families of matrices.

arXiv:1704.04992•Physical Review A•Feb 14, 2020•172 citations
Logistic regression (LR) is an important machine learning model for classification, with wide applications in text classification, image analysis and medicine diagnosis, etc. However, training LR generally entails an iterative gradient descent method, and is quite time consuming when processing big data sets. To solve this problem, we present a quantum algorithm for LR to implement the key task of the gradient descent method, obtaining the classical gradients in each iteration. It is shown that our algorithm achieves exponential speedup over its classical counterpart in each iteration when the dimension of each data point M grows polylogarithmically with the number of data points N, i.e.,M=O(polylog N). It is worth noting that the optimal model parameters are finally derived by performing simple calculations on the obtained gradients. So once the optimal model parameters are determined, one can use them to classify new data at little cost.
This paper presents a hybrid quantum logistic regression model for binary data classification that combines classical logistic regression methods with quantum computing to improve efficiency and speed up the learning process. Quantum computing is used to represent and process feature and weight vectors as quantum states and to efficiently compute the dot product underlying the logistic function. The use of normalized amplitude coding allows for compact representation of feature vectors and weights, reducing the number of qubits required and potentially speeding up computations for high-dimensional classification problems where classical methods may encounter scalability limitations. The quantum dot product computation is performed using the Hadamard test, which provides a statistical estimate of the probability of measuring an auxiliary qubit. The auxiliary qubit is first put into a superposition state, and after performing controlled unitary operations, amplitude interference is formed, which depends on the scalar product of the feature vector and weight coefficients. The obtained measurement probability is used to estimate the scalar product of the feature vectors and weights. The classical part of the model provides for the execution of operations that are difficult to implement on modern quantum devices, in particular, vector normalization, application of the sigmoid function to estimate the probability of an object belonging to a certain class, calculation of the loss function and iterative update of weight coefficients by the gradient descent method. The purpose of classification is to predict the binary class for an unknown sample based on the training sample. To demonstrate the model, a numerical example is given with a step-by-step calculation of one iteration of logistic regression training. In addition, computer modeling of the hybrid algorithm training process was performed, taking into account the influence of noise on the results of quantum state measurements. A quantum noise model was developed based on the probability of confidence in the measurement result, which is interpreted as an assessment of its reliability in a Bernoulli experiment. Comparison of the obtained results with the classical approach confirms the practical suitability of the hybrid algorithm for binary classification problems. The hybrid model preserves the key properties of classical logistic regression – parameter interpretability and optimization stability, while allowing for the use of quantum advantages for compact data encoding and scalar product computation. This makes the study of hybrid logistic regression relevant for the development of machine learning algorithms on modern quantum platforms.
Logistic regression, the Support Vector Machine (SVM), and least squares are well-studied methods in the statistical and computer science community, with various practical applications. High-dimensional data arriving on a real-time basis makes the design of online learning algorithms that produce sparse solutions essential. The seminal work of \hyperlink{cite.langford2009sparse}{Langford, Li, and Zhang (2009)} developed a method to obtain sparsity via truncated gradient descent, showing a near-optimal online regret bound. Based on this method, we develop a quantum sparse online learning algorithm for logistic regression, the SVM, and least squares. Given efficient quantum access to the inputs, we show that a quadratic speedup in the time complexity with respect to the dimension of the problem is achievable, while maintaining a regret of O(1/T)O(1/\sqrt{T})O(1/T​), where TTT is the number of iterations.
Gaussian process regression (GPR) is a nonparametric supervised learning method, widely valued for its ability to quantify uncertainty. Despite its advantages and broad applications, classical GPR implementations face significant scalability challenges, as they involve matrix operations with a cubic complexity in relation to the dataset size. This computational challenge is further compounded by the demand of optimizing the Gaussian Process (GP) model over its hyperparameters, rendering the total computational cost prohibitive for data intensive problems. To address this issue, we propose a quantum gradient descent algorithm to optimize the GP model. Taking advantage of recent advances in quantum algorithms for linear algebra, our algorithm achieves exponential speedup in computing the gradients of the log marginal likelihood. The entire gradient descent process is integrated into the quantum circuit. Through runtime analysis and error bounds, we demonstrate that our approach significantly improves the scalability of GPR model optimization, making it computationally feasible for large-scale applications.
Supervised machine learning is the classification of new data based on already classified training examples. In this work, we show that the support vector machine, an optimized binary classifier, can be implemented on a quantum computer, with complexity logarithmic in the size of the vectors and the number of training examples. In cases where classical sampling algorithms require polynomial time, an exponential speedup is obtained. At the core of this quantum big data algorithm is a nonsparse matrix exponentiation technique for efficiently performing a matrix inversion of the training data inner-product (kernel) matrix.
Gradient Descent is an optimization algorithm used for finding the minima of a function. It moves along the function with steps proportional to the negative of the gradient. Quantum version of this algorithm has the advantage of exponential speedup for problems with high dimensional inputs. On the other hand, Factorization Machines (FMs) are modeling classes with important advantages in comparison with other modeling ones such as SVMs. They, in contrast to SVMs, use factorized parameters in order to model all interactions between variables. Accordingly, unlike SVMs, they can estimate interactions in problems with large sparsity. In this work, we show that Factorization Machine can be implemented on quantum computers, using quantum gradient descent to learn the parameters of a FM. The parameters we have chosen to learn via quantum gradient descent is a bottleneck in learning parameters of a FM. Our proposed idea results in time computational complexity O(k polylog n) where k and n are the dimensions of the parameter matrix. By doing so and under some constraints on the dimensions, an exponential speedup over classical algorithms can be obtained.
Quantum machine learning and optimization are exciting new areas that have been brought forward by the breakthrough quantum algorithm of Harrow, Hassidim, and Lloyd for solving systems of linear equations. The utility of classical linear system solvers extends beyond linear algebra as they can be leveraged to solve optimization problems using iterative methods like gradient descent. In this work, we provide a quantum method for performing gradient descent when the gradient is an affine function. Performing $\ensuremath{\tau}$ steps of the gradient descent requires time $O(\ensuremath{\tau}{C}_{S})$ for weighted least-squares problems, where CS{C}_{S}CS​ is the cost of performing one step of the gradient descent quantumly, which at times can be considerably smaller than the classical cost. We illustrate our method by providing two applications: first, for solving positive semidefinite linear systems, and, second, for performing stochastic gradient descent for the weighted least-squares problem with reduced quantum memory requirements. We also provide a quantum linear system solver in the QRAM data structure model that provides significant savings in cost for large families of matrices.