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

Physical Review A

Quantum algorithm for support matrix machines

Bojia Duan, Jiabin Yuan, Ying Liu, Dan Li

Published Sep 1, 2017• 65 citations
Publisher

Abstract

We propose a quantum algorithm for support matrix machines (SMMs) that efficiently addresses an image classification problem by introducing a least-squares reformulation. This algorithm consists of two core subroutines: a quantum matrix inversion (Harrow-Hassidim-Lloyd, HHL) algorithm and a quantum singular value thresholding (QSVT) algorithm. The two algorithms can be implemented on a universal quantum computer with complexity $O\left[log\left(npq\right)\right]$ and $O\left[log\left(pq\right)\right]$, respectively, where $n$ is the number of the training data and $pq$ is the size of the feature space. By iterating the algorithms, we can find the parameters for the SMM classfication model. Our analysis shows that both HHL and QSVT algorithms achieve an exponential increase of speed over their classical counterparts.

DOI
10.1103/physreva.96.032301

Related papers

Quantum algorithm for low-rank matrix regression with feature extraction

Kaitian Gao, Youlong Yang, Zhenye Du

Low-rank matrix regression is a pivotal technique in image processing and pattern recognition that can directly handle data with intrinsic matrix structures. However, classical algorithms for this task suffer from a computational bottleneck, where the complexity escalates cubically with the matrix dimension, incurring prohibitive costs for high-dimensional datasets. In this study, we propose a quantum algorithm for low-rank matrix regression with feature extraction, leveraging the Harrow–Hassidim–Lloyd algorithm for regression matrix estimation and a modified quantum singular-value thresholding algorithm for iterative variable updates. Theoretical analysis demonstrates that our algorithm reduces the time complexity dependence on the matrix dimension from cubic to logarithmic, achieving an exponential speedup over classical counterparts when the problem is well conditioned and the precision requirements are moderate. Furthermore, we introduce an algorithmic variant utilizing the quantum memory model to bypass the reliance on quantum random access memory. Additionally, we propose a hybrid strategy leveraging quantum sketching techniques to effectively eliminate the runtime dependence on the condition number. Subsequently, we performed small-scale quantum experiments to validate the feasibility of our proposed quantum algorithm.

Journal of Applied Physics•Jan 5, 2026•0 citations

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

Quantum support vector machine for big feature and 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 linear and non-linear binary classifier, can be implemented on a quantum computer, with exponential speedups in the size of the vectors and the number of training data examples. At the core of the algorithm is a non-sparse matrix simulation technique to efficiently perform a principal component analysis and matrix inversion of the training data kernel matrix. We thus provide an example of a quantum big feature and big data algorithm and pave the way for future developments at the intersection of quantum computing and machine learning.

•Jul 1, 2013•38 citations

LS-SVM generation using an optimized HHL quantum algorithm

Gabriela Pinheiro, Luis Antônio Brasil Kowada

Abstract Least Squares Support Vector Machine (LS-SVM) is a reformulation of the Support Vector Machine(SVM) algorithm that uses a hyperplane to classify elements in a dataset, with the coefficients of the hyperplane being determined by solving a linear system of equations. A quantum algorithm, the Harrow-Hassidim-Lloyd (HHL) algorithm, has the potential to offer exponential advantages over classical algorithms for solving linear systems, although an efficient implementation is yet to be developed. The current era of quantum computing presents a series of technical challenges for implementing and executing circuits, with smaller circuits being less susceptible to noise. In response to this scenario, circuit reduction optimizations have been developed to enhance execution quality. This paper presents the process of using optimized HHL quantum circuits to generate LS-SVMs applied to the classification of pulsar candidates, where the quantum generated SVMs closely matched the performance of their classical counterparts and obtained competitive results against other Quantum Machine Learning methods even when using a real quantum device, with the optimized circuits having a significant execution speedup over the original quantum circuits.

•Sep 3, 2025•1 citation

Efficient quantum circuit for singular-value thresholding

Bojia Duan, Jiabin Yuan, Ying Liu +1 more

A singular-value thresholding (SVT) operation is a fundamental core module of many mathematical models in computer vision and machine learning, particularly for many nuclear norm minimizing-based problems. A quantum SVT (QSVT) algorithm was proposed in Phys. Rev. A. 96, 032301 (2017) to solve an image-classification problem. This algorithm runs in $O\left[{log}_{2}\left(pq\right)\right]$, an exponential speed improvement over the classical algorithm, which runs in $O\left[\text{poly}\left(pq\right)\right]$. In this paper, we design a scalable quantum circuit for a QSVT. The quantum circuit is designed with $O\left[{log}_{2}\left(pq/\ensuremath{\varepsilon}\right)\right]$ qubits and $O\left[\text{poly}{log}_{2}\left(1/\ensuremath{\varepsilon}\right)\right]$ quantum gates in terms of error $O\left(\ensuremath{\varepsilon}\right)$. We also show that a high-probability and high-fidelity output can be obtained in one iteration of the quantum circuit. The quantum circuit for a QSVT implies a tempting possibility for experimental realization on a quantum computer. Finally, we propose a small-scale quantum circuit for a QSVT. We numerically simulate and demonstrate the performance of this circuit, verifying its capability to solve the intended SVT.

arXiv:1711.08896•Physical Review A•Jul 10, 2018•31 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
We propose a quantum algorithm for support matrix machines (SMMs) that efficiently addresses an image classification problem by introducing a least-squares reformulation. This algorithm consists of two core subroutines: a quantum matrix inversion (Harrow-Hassidim-Lloyd, HHL) algorithm and a quantum singular value thresholding (QSVT) algorithm. The two algorithms can be implemented on a universal quantum computer with complexity O[log(npq)]O\left[log\left(npq\right)\right]O[log(npq)] and O[log(pq)]O\left[log\left(pq\right)\right]O[log(pq)], respectively, where nnn is the number of the training data and pqpqpq is the size of the feature space. By iterating the algorithms, we can find the parameters for the SMM classfication model. Our analysis shows that both HHL and QSVT algorithms achieve an exponential increase of speed over their classical counterparts.
Low-rank matrix regression is a pivotal technique in image processing and pattern recognition that can directly handle data with intrinsic matrix structures. However, classical algorithms for this task suffer from a computational bottleneck, where the complexity escalates cubically with the matrix dimension, incurring prohibitive costs for high-dimensional datasets. In this study, we propose a quantum algorithm for low-rank matrix regression with feature extraction, leveraging the Harrow–Hassidim–Lloyd algorithm for regression matrix estimation and a modified quantum singular-value thresholding algorithm for iterative variable updates. Theoretical analysis demonstrates that our algorithm reduces the time complexity dependence on the matrix dimension from cubic to logarithmic, achieving an exponential speedup over classical counterparts when the problem is well conditioned and the precision requirements are moderate. Furthermore, we introduce an algorithmic variant utilizing the quantum memory model to bypass the reliance on quantum random access memory. Additionally, we propose a hybrid strategy leveraging quantum sketching techniques to effectively eliminate the runtime dependence on the condition number. Subsequently, we performed small-scale quantum experiments to validate the feasibility of our proposed quantum algorithm.
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.
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 linear and non-linear binary classifier, can be implemented on a quantum computer, with exponential speedups in the size of the vectors and the number of training data examples. At the core of the algorithm is a non-sparse matrix simulation technique to efficiently perform a principal component analysis and matrix inversion of the training data kernel matrix. We thus provide an example of a quantum big feature and big data algorithm and pave the way for future developments at the intersection of quantum computing and machine learning.
Abstract Least Squares Support Vector Machine (LS-SVM) is a reformulation of the Support Vector Machine(SVM) algorithm that uses a hyperplane to classify elements in a dataset, with the coefficients of the hyperplane being determined by solving a linear system of equations. A quantum algorithm, the Harrow-Hassidim-Lloyd (HHL) algorithm, has the potential to offer exponential advantages over classical algorithms for solving linear systems, although an efficient implementation is yet to be developed. The current era of quantum computing presents a series of technical challenges for implementing and executing circuits, with smaller circuits being less susceptible to noise. In response to this scenario, circuit reduction optimizations have been developed to enhance execution quality. This paper presents the process of using optimized HHL quantum circuits to generate LS-SVMs applied to the classification of pulsar candidates, where the quantum generated SVMs closely matched the performance of their classical counterparts and obtained competitive results against other Quantum Machine Learning methods even when using a real quantum device, with the optimized circuits having a significant execution speedup over the original quantum circuits.
A singular-value thresholding (SVT) operation is a fundamental core module of many mathematical models in computer vision and machine learning, particularly for many nuclear norm minimizing-based problems. A quantum SVT (QSVT) algorithm was proposed in Phys. Rev. A. 96, 032301 (2017) to solve an image-classification problem. This algorithm runs in O[log2(pq)]O\left[{log}_{2}\left(pq\right)\right]O[log2​(pq)], an exponential speed improvement over the classical algorithm, which runs in O[poly(pq)]O\left[\text{poly}\left(pq\right)\right]O[poly(pq)]. In this paper, we design a scalable quantum circuit for a QSVT. The quantum circuit is designed with $O\left[{log}_{2}\left(pq/\ensuremath{\varepsilon}\right)\right]$ qubits and $O\left[\text{poly}{log}_{2}\left(1/\ensuremath{\varepsilon}\right)\right]$ quantum gates in terms of error $O\left(\ensuremath{\varepsilon}\right)$. We also show that a high-probability and high-fidelity output can be obtained in one iteration of the quantum circuit. The quantum circuit for a QSVT implies a tempting possibility for experimental realization on a quantum computer. Finally, we propose a small-scale quantum circuit for a QSVT. We numerically simulate and demonstrate the performance of this circuit, verifying its capability to solve the intended SVT.
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.