We examine the feasibility of Deutsch-Jozsa Algorithm, a basic quantum algorithm, on a machine learning-based logistic regression problem. Its major property to distinguish the function type with an exponential speedup can help identify the feature unsuitability much more quickly. Although strict conditions and restrictions to abide exist, we reconfirm the quantum superiority in many aspects of modern computing.
We examine the feasibility of Deutsch-Jozsa Algorithm, a basic quantum algorithm, on a machine learning-based logistic regression problem. Its major property to distinguish the function type with an exponential speedup can help identify the feature unsuitability much more quickly. Although strict conditions and restrictions to abide exist, we reconfirm the quantum superiority in many aspects of modern computing.
We present a generalized Deutsch-Jozsa (DJ) quantum algorithm that not only determines both the global type of an unknown Boolean function (constant or balanced) but also determines explicit output values of the function in a single oracle query. Unlike the original DJ algorithm, which identifies only whether a function is constant or balanced, our generalization retrieves actual function output values at the same time with using a Bell state as ancilla. This makes a richer function characterization with minimal queries to have practical quantum advantages, e.g. data classification, logistic regression, and quantum cryptography.
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 (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.
Feature selection is a pivotal step in machine learning, aimed at reducing feature dimensionality and improving model performance. Conventional feature selection methods, typically framed as NP-hard problems, focus primarily on selecting non-redundant and discriminative features but neglect how these selected features influence downstream machine learning tasks. To bridge this gap, we propose a mixed-integer non-linear programming-based integrated feature selection and logistic regression (IFSLR) model that jointly optimizes feature selection and classifier parameters. To solve the proposed IFSLR model efficiently, we reformulate it into two quantum-computing-compatible quadratic unconstrained binary optimization (QUBO) models via discretization of continuous variables and Taylor expansions, and provide a theoretical approximation guarantee for the proposed QUBO models. To adaptively optimize both the discretization step length optimization sub-problems and the parameterized QUBO sub-problems, we develop a dual-level Q-learning-guided hybrid quantum-classical algorithm that dynamically selects which sub-problem to solve. At the upper level, an adaptive Q learning agent is employed to select appropriate sub-problems during the search process. At the lower level, each iteration addresses either discretization step length optimization sub-problems or parameterized QUBO sub-problems. Experiments on the German credit dataset demonstrate that our method achieves a 10.83% improvement in accuracy and a 4.54-fold enhancement in computational efficiency on average compared with state-of-the-art methods. It also achievesF1 score improvements of 2.86% on the Wisconsin diagnostic breast cancer dataset and 7.65% on the Portuguese bank marketing dataset. The improvements further validate the effectiveness and generalizability of the proposed model and algorithm.
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), where T is the number of iterations.
By fusing the revolutionary machine learning technique with the special features of quantum computing, the quickly emerging subject of quantum machine learning aims to increase computation efficiency and smoothness in terms of both space and temporal complexities. A specific dataset pertaining to quantum computing has been evaluated and trained using a variety of machine learning techniques, such as logistic regression, random forests, and XGBoost. Recall, accuracy, and precision have all been computed and compared. Furthermore, various classifications of quantum machine learning algorithms and their challenges have been extensively discussed, exploring various opportunities and research areas in this field. The chapter’s conclusion highlights the significance of integrating the two cutting-edge, interdisciplinary fields of machine learning and quantum computing to further this research. This discovery adds to the literature on the intricacy and challenges of data processing in the potentially exploding field of quantum machine learning.