Machine learning is considered to be one of the most promising applications of quantum computing. Therefore, the search for quantum advantage of the quantum analogues of machine learning models is a key research goal. Here, we show that variational quantum classifiers and support vector machines with quantum kernels can solve a classification problem based on the k-FORRELATION problem, which is known to be PROMISEBQP-complete. Because the PROMISEBQP complexity class includes all Bounded-Error Quantum Polynomial-Time (BQP) decision problems, our results imply that there exists a feature map and a quantum kernel that make variational quantum classifiers and quantum kernel support vector machines efficient solvers for any BQP problem. Hence, this work implies that their feature map and quantum kernel, respectively, can be designed to have a quantum advantage for any classification problem that cannot be classically solved in polynomial time but contrariwise by a quantum computer.
Machine learning is considered to be one of the most promising applications of quantum computing. Therefore, the search for quantum advantage of the quantum analogues of machine learning models is a key research goal. Here, we show that variational quantum classifiers and support vector machines with quantum kernels can solve a classification problem based on the k-FORRELATION problem, which is known to be PROMISEBQP-complete. Because the PROMISEBQP complexity class includes all Bounded-Error Quantum Polynomial-Time (BQP) decision problems, our results imply that there exists a feature map and a quantum kernel that make variational quantum classifiers and quantum kernel support vector machines efficient solvers for any BQP problem. Hence, this work implies that their feature map and quantum kernel, respectively, can be designed to have a quantum advantage for any classification problem that cannot be classically solved in polynomial time but contrariwise by a quantum computer.
Abstract A kernel-based quantum classifier is the most interesting and powerful quantum machine learning technique for hyperlinear classification of complex data, which can be easily realized in shallow-depth quantum circuits such as a SWAP test classifier. A variational quantum approximate support vector machine (VQASVM) can be realized inherently and explicitly on these circuits by introduction of a variational scheme to map the quadratic optimization problem of the support vector machine theory to a quantum-classical variational optimization problem. Probability weight modulation in index qubits of a classifier can designate support vectors among training vectors, which can be achieved with a parameterized quantum circuit (PQC). The classical parameters of PQC is then transferred to many copies of other decision inference circuits. Our VQASVM algorithm is experimented with toy example data sets on cloud-based quantum machines for feasibility evaluation, and numerically investigated to evaluate its performance on a standard iris flower and MNIST data set. The empirical run-time complexity of VQASVM is estimated to be sub-quadratic on the training data set size, while that of the classical solver is quadratic.
Background Quantum support vector machines and quantum kernel methods have emerged as promising approaches within quantum machine learning, with the goal of leveraging quantum computing to enhance classification performance and computational efficiency. This review systematically surveys recent advances in QSVM and kernel‐based quantum classifiers, and analyzes their algorithmic frameworks, experimental implementations, and practical challenges. Methods We systematically examine QSVM approaches, including three schemes based on HHL algorithm, Hadamard test, and variational optimization, alongside multi‐class extension and quantum feature mapping. Result Findings indicate that QSVM can offer theoretical speed‐ups in specific settings, particularly when combined with quantum feature mappings that encode data into high‐dimensional Hilbert spaces. However, current implementations remain constrained by hardware limitations, and a lack of large‐scale general validation. Most studies focus on proof‐of‐principle experiments with limited real‐world applicability. Conclusion While promising, QSVM requires further work on scalability, noise resilience, and real‐world integration. Future research should focus on robust algorithms and empirical studies.
Quantum algorithms have become a popular research domain in recent times for discovering quantum-enhanced solutions in machine learning applications. Quantum kernels are one of the directions that establish such quantum-enhanced solutions to some extent. This work presents a detailed analysis of the quantum kernel approach leveraging feature maps and relevant hyperparameters to develop enhanced quantum kernels. The study includes a new high-order feature map and assesses five existing state-of-the-art feature maps for enhanced quantum kernel classifiers. Additionally, the significance of the rotational factor as a hyperparameter is highlighted for improving kernel performance. Also, it is analyzed whether different hyperparameter-tuned feature maps can lead to enhanced decision boundaries, demonstrating kernel expressivity. The analysis is undertaken on classification tasks using four different nonlinear datasets of distinct complexity. Comparative evaluations are also made with traditional machine learning models-Support Vector Machines (Linear and RBF), Naïve Bayes, Linear Discriminant Analysis, Decision Tree, Random Forest, Adaptive Boosting, and MLP. Overall, the study demonstrates that a well-tuned quantum feature map can enhance the generalization ability of quantum kernels, making them more effective for broader quantum-enhanced machine learning applications.
The quantum support vector machines (QSVMs) offer a paradigm change that may leverage quantum mechanical processes to outperform traditional support vector machines (SVMs) in high-dimensional and nonlinear classification tasks. These machines are located at the crossroads of supervised machine learning and quantum computing. The purpose of this chapter is to provide a comprehensive technical analysis of QSVMs, with a particular emphasis on the use of variation quantum circuits for implicit feature space transformations and the development of these circuits within the context of quantum kernel estimation. Through the use of quantum state preparation and interference, we provide a comprehensive explanation of the possible fabrication of quantum kernels that are based on inner product evaluations in exponentially huge Hilbert spaces. When it comes to boosting model expressivity beyond classical limits, the importance that entanglement and quantum feature mapping play is specifically stressed. In addition to this, we investigate algorithmic implementations on noisy intermediate-scale quantum (NISQ) hardware, focusing on problems associated with quantum decoherence, gate fidelity, and loop depth optimization. Several fields, including quantum-enhanced drug discovery, anomaly detection in quantum sensor networks, fault classification in quantum error correction, and portfolio optimization, are now the focus of research that is being conducted in order to develop real-world applications. This chapter comes to a close with an analysis of the existing theoretical limits, resource needs, and future perspectives for the use of QSVMs in machine learning applications in order to achieve a quantum advantage. In order to facilitate the development of scalable quantum machine learning models that are founded on strong mathematical and computational notions, this synthesis is geared at academics and practitioners.
A basic idea of quantum computing is surprisingly similar to that of kernel methods in machine learning, namely, to efficiently perform computations in an intractably large Hilbert space. In this Letter we explore some theoretical foundations of this link and show how it opens up a new avenue for the design of quantum machine learning algorithms. We interpret the process of encoding inputs in a quantum state as a nonlinear feature map that maps data to quantum Hilbert space. A quantum computer can now analyze the input data in this feature space. Based on this link, we discuss two approaches for building a quantum model for classification. In the first approach, the quantum device estimates inner products of quantum states to compute a classically intractable kernel. The kernel can be fed into any classical kernel method such as a support vector machine. In the second approach, we use a variational quantum circuit as a linear model that classifies data explicitly in Hilbert space. We illustrate these ideas with a feature map based on squeezing in a continuous-variable system, and visualize the working principle with two-dimensional minibenchmark datasets.
A potential path forward is Quantum Machine Learning (QML), which aims to leverage quantum computing in conjunction with classical machine learning to enhance computing efficiency and the expressiveness of models. In this paper, two different quantum classifiers - Variational Quantum Classifier (VQC) and Quantum Kernel Support Vector Machine (QSVM) - are compared with three classical classifiers as baseline classifiers - Logistic Regression, Support Vector Machine (SVM), and a Multi-Layer Perceptron (MLP) - on the Breast Cancer Wisconsin dataset. The quantum circuits were created in the PennyLane framework and simulated on a classical backend. However, in terms of accuracy, classical Logistic Regression performed better with an accuracy of 97.8%, classical SVM and QSVM with an accuracy of 95.6% each, although the Quantum VQC achieved a lower accuracy of 88.9% and had a recall of 100% for the benign class, though it correctly identified only 12 of the 17 malignant cases (a malignant-class recall of approximately 70.6%). The drawback of quantum models is the higher training time; however, since the quantum circuit needs to be classically simulated, the quantum SVM took 23.29 seconds compared to less than 0.01 seconds for the classical linear models. These results indicate that for small structured datasets, classifiers based on quantum computing have not yet surpassed well-tuned classical counterparts. In some respects (e.g., benign-class recall), they perform competitively, though not on malignant-class recall, where the VQC in particular performed worse than the classical baselines, which is worth further investigation on real quantum computers.