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:2203.00031 · Quantum

The complexity of quantum support vector machines

Gian Gentinetta, Arne Thomsen, David Sutter, Stefan Woerner

Published Jan 11, 2024• 65 citations
arXivHTMLPDF

Abstract

Quantum support vector machines employ quantum circuits to define the kernel function. It has been shown that this approach offers a provable exponential speedup compared to any known classical algorithm for certain data sets. The training of such models corresponds to solving a convex optimization problem either via its primal or dual formulation. Due to the probabilistic nature of quantum mechanics, the training algorithms are affected by statistical uncertainty, which has a major impact on their complexity. We show that the dual problem can be solved in O ( M 4.67 / ε 2 ) quantum circuit evaluations, where M denotes the size of the data set and ε the solution accuracy compared to the ideal result from exact expectation values, which is only obtainable in theory. We prove under an empirically motivated assumption that the kernelized primal problem can alternatively be solved in O ( min { M 2 / ε 6 , 1 / ε 10 } ) evaluations by employing a generalization of a known classical algorithm called Pegasos. Accompanying empirical results demonstrate these analytical complexities to be essentially tight. In addition, we investigate a variational approximation to quantum support vector machines and show that their heuristic training achieves considerably better scaling in our experiments.

DOI
10.22331/q-2024-01-11-1225

Related papers

Variational quantum approximate support vector machine with inference transfer

Siheon Park, Daniel K. Park, June‐Koo Kevin Rhee

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.

arXiv:2206.14507•Scientific Reports•Feb 25, 2023•36 citations

Gaussian Kernel in Quantum Paradigm.

Arit Kumar Bishwas, Ashish Mani, Vasile Palade

The Gaussian kernel is a very popular kernel function used in many machine-learning algorithms, especially in support vector machines (SVM). For nonlinear training instances in machine learning, it often outperforms polynomial kernels in model accuracy. We use Gaussian kernel profoundly in formulating nonlinear classical SVM. In the recent research, P. Rebentrost et.al. discuss a very elegant quantum version of least square support vector machine using the quantum version of polynomial kernel, which is exponentially faster than the classical counterparts. In this paper, we have demonstrated a quantum version of the Gaussian kernel and analyzed its complexity in the context of quantum SVM. Our analysis shows that the computational complexity of the quantum Gaussian kernel is O(\epsilon^(-1)logN) with N-dimensional instances and \epsilon with a Taylor remainder error term |R_m (\epsilon^(-1) logN)|.

•Nov 4, 2017•0 citations

A Triple-Hybrid Quantum Support Vector Machine Using Classical, Quantum Gate-based and Quantum Annealing-based Computing

Juan C. Boschero, Ward van der Schoot, Niels M. P. Neumann

Quantum machine learning is one of the fields where quantum computers are expected to bring advantages over classical methods. However, the limited size of current computers restricts the exploitation of the full potential of quantum machine learning methods. Additionally, different computing paradigms, both quantum and classical, each have their own strengths and weaknesses. Obtaining optimal results with algorithms thus requires algorithms to be tweaked to the underlying computational paradigm, and the tasks to be optimally distributed over the available computational resources. In this work, we explore the potential gains from combining different computing paradigms to solve the complex task of data classification for three different datasets. We use a gate-based quantum model to implement a quantum kernel and implement a complex feature map. Next, we formulate a quadratic unconstrained optimisation problem to be solved on quantum annealing hardware. We then evaluate the losses on classical hardware and reconfigure the model parameters accordingly. We tested this so-called triple-hybrid quantum support vector machine on various data sets, and find that it achieves higher precision than other support vector machines (both quantum and classical) on complex quantum data, whereas it achieves varying performance on simple classical data using limited training. For the complex data sets, the triple-hybrid version converges faster, requiring fewer circuit evaluations.

quant-pharXiv:2511.05237•Nov 10, 2025•0 citations

Quantum Kernel Alignment with Stochastic Gradient Descent

Gian Gentinetta, David Sutter, Christa Zoufal +2 more

Quantum support vector machines have the potential to achieve a quantum speedup for solving certain machine learning problems. The key challenge for doing so is finding good quantum kernels for a given data set - a task called kernel alignment. In this paper we study this problem using the Pegasos algorithm, which is an algorithm that uses stochastic gradient descent to solve the support vector machine optimization problem. We extend Pegasos to the quantum case and and demonstrate its effectiveness for kernel alignment. Unlike previous work which performs kernel alignment by training a QSVM within an outer optimization loop, we show that using Pegasos it is possible to simultaneously train the support vector machine and align the kernel. Our experiments show that this approach is capable of aligning quantum feature maps with high accuracy, and outperforms existing quantum kernel alignment techniques. Specifically, we demonstrate that Pegasos is particularly effective for non-stationary data, which is an important challenge in real-world applications.

arXiv:2304.09899•IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 17, 2023•17 citations

Support Vector Machine with a Scalable Quantum Kernel

Anant Agnihotri, Michael Krebsbach, Florentin Reiter +1 more

Quantum support vector machines are classification algorithms that rely on quantum-generated kernels. The fidelity quantum kernel commonly used in quantum support vector machines suffers from exponential concentration as system size increases, preventing an efficient scaling beyond fewqubit systems. We introduce the Hamming quantum kernel, a classical post-processing method that is based on the same measurement outcomes as the fidelity quantum kernel. However, it avoids the exponential concentration problem by using the full measurement statistics rather than a single fidelity value. We evaluate the approach on both classical data (MNIST) and synthetic data generated from quantum circuits, using systems ranging from 2 to 27 qubits. Throughout the simulations, the Hamming quantum kernel outperforms the fidelity quantum kernel whenever 15 or more qubits are used. Furthermore, for synthetic quantum data, our method consistently outperforms the classical Gaussian kernel. This demonstrates that the Hamming quantum kernel improves the expressivity and robustness at larger qubit scales without requiring any additional quantum ressources.

quant-pharXiv:2605.31449•Jun 1, 2026•0 citations

Implementation of Quantum Support Vector Machine Algorithm Using a Benchmarking Dataset

The evolution of quantum computers and quantum machine learning (QML) algorithms have started demonstrating exponential speed-ups. In machine learning problems, the efficient handling and manipulation of linear algebra subroutines defines the complexity of the task to be performed. Quantum computers handle big datasets in the form of vectors and matrix operations very efficiently. In this paper, quantum support vector machine (QSVM) algorithm is used to solve a classification problem using a benchmarking MNIST dataset of handwritten images of digits. Quantum SVM variational and kernel matrix algorithms are implemented to analyze quantum speedup on quantum simulator and physical quantum processor back-ends. The study compared classical and quantum SVM algorithms in terms of execution time and accuracy. The results explicitly prove quantum speed-up achieved by quantum classifiers on quantum back-ends for machine learning applications.

Indian Journal of Pure & Applied Physics•Apr 28, 2022•23 citations
Quantum support vector machines employ quantum circuits to define the kernel function. It has been shown that this approach offers a provable exponential speedup compared to any known classical algorithm for certain data sets. The training of such models corresponds to solving a convex optimization problem either via its primal or dual formulation. Due to the probabilistic nature of quantum mechanics, the training algorithms are affected by statistical uncertainty, which has a major impact on their complexity. We show that the dual problem can be solved in O ( M 4.67 / ε 2 ) quantum circuit evaluations, where M denotes the size of the data set and ε the solution accuracy compared to the ideal result from exact expectation values, which is only obtainable in theory. We prove under an empirically motivated assumption that the kernelized primal problem can alternatively be solved in O ( min { M 2 / ε 6 , 1 / ε 10 } ) evaluations by employing a generalization of a known classical algorithm called Pegasos. Accompanying empirical results demonstrate these analytical complexities to be essentially tight. In addition, we investigate a variational approximation to quantum support vector machines and show that their heuristic training achieves considerably better scaling in our experiments.
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.
The Gaussian kernel is a very popular kernel function used in many machine-learning algorithms, especially in support vector machines (SVM). For nonlinear training instances in machine learning, it often outperforms polynomial kernels in model accuracy. We use Gaussian kernel profoundly in formulating nonlinear classical SVM. In the recent research, P. Rebentrost et.al. discuss a very elegant quantum version of least square support vector machine using the quantum version of polynomial kernel, which is exponentially faster than the classical counterparts. In this paper, we have demonstrated a quantum version of the Gaussian kernel and analyzed its complexity in the context of quantum SVM. Our analysis shows that the computational complexity of the quantum Gaussian kernel is O(\epsilon^(-1)logN) with N-dimensional instances and \epsilon with a Taylor remainder error term |R_m (\epsilon^(-1) logN)|.
Quantum machine learning is one of the fields where quantum computers are expected to bring advantages over classical methods. However, the limited size of current computers restricts the exploitation of the full potential of quantum machine learning methods. Additionally, different computing paradigms, both quantum and classical, each have their own strengths and weaknesses. Obtaining optimal results with algorithms thus requires algorithms to be tweaked to the underlying computational paradigm, and the tasks to be optimally distributed over the available computational resources. In this work, we explore the potential gains from combining different computing paradigms to solve the complex task of data classification for three different datasets. We use a gate-based quantum model to implement a quantum kernel and implement a complex feature map. Next, we formulate a quadratic unconstrained optimisation problem to be solved on quantum annealing hardware. We then evaluate the losses on classical hardware and reconfigure the model parameters accordingly. We tested this so-called triple-hybrid quantum support vector machine on various data sets, and find that it achieves higher precision than other support vector machines (both quantum and classical) on complex quantum data, whereas it achieves varying performance on simple classical data using limited training. For the complex data sets, the triple-hybrid version converges faster, requiring fewer circuit evaluations.
Quantum support vector machines have the potential to achieve a quantum speedup for solving certain machine learning problems. The key challenge for doing so is finding good quantum kernels for a given data set - a task called kernel alignment. In this paper we study this problem using the Pegasos algorithm, which is an algorithm that uses stochastic gradient descent to solve the support vector machine optimization problem. We extend Pegasos to the quantum case and and demonstrate its effectiveness for kernel alignment. Unlike previous work which performs kernel alignment by training a QSVM within an outer optimization loop, we show that using Pegasos it is possible to simultaneously train the support vector machine and align the kernel. Our experiments show that this approach is capable of aligning quantum feature maps with high accuracy, and outperforms existing quantum kernel alignment techniques. Specifically, we demonstrate that Pegasos is particularly effective for non-stationary data, which is an important challenge in real-world applications.
Quantum support vector machines are classification algorithms that rely on quantum-generated kernels. The fidelity quantum kernel commonly used in quantum support vector machines suffers from exponential concentration as system size increases, preventing an efficient scaling beyond fewqubit systems. We introduce the Hamming quantum kernel, a classical post-processing method that is based on the same measurement outcomes as the fidelity quantum kernel. However, it avoids the exponential concentration problem by using the full measurement statistics rather than a single fidelity value. We evaluate the approach on both classical data (MNIST) and synthetic data generated from quantum circuits, using systems ranging from 2 to 27 qubits. Throughout the simulations, the Hamming quantum kernel outperforms the fidelity quantum kernel whenever 15 or more qubits are used. Furthermore, for synthetic quantum data, our method consistently outperforms the classical Gaussian kernel. This demonstrates that the Hamming quantum kernel improves the expressivity and robustness at larger qubit scales without requiring any additional quantum ressources.
The evolution of quantum computers and quantum machine learning (QML) algorithms have started demonstrating exponential speed-ups. In machine learning problems, the efficient handling and manipulation of linear algebra subroutines defines the complexity of the task to be performed. Quantum computers handle big datasets in the form of vectors and matrix operations very efficiently. In this paper, quantum support vector machine (QSVM) algorithm is used to solve a classification problem using a benchmarking MNIST dataset of handwritten images of digits. Quantum SVM variational and kernel matrix algorithms are implemented to analyze quantum speedup on quantum simulator and physical quantum processor back-ends. The study compared classical and quantum SVM algorithms in terms of execution time and accuracy. The results explicitly prove quantum speed-up achieved by quantum classifiers on quantum back-ends for machine learning applications.