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

Journal of Physics A Mathematical and Theoretical

Quantum speedup of Bayes’ classifiers

Changpeng Shao

Published Nov 29, 2019• 9 citations
Publisher

Abstract

Abstract Data classification is a fundamental problem in machine learning. We study quantum speedup of the supervised data classification algorithms (quadratic, linear and naïve Bayes classifiers) based on Bayes’ theory. The main technique we use to achieve quantum speedup is block-encoding. However, to apply this technique effectively, we propose a general method to construct the block-encoding. As an application, we show that all the three classifiers achieve exponential speedup at the number of samples over their classical counterparts. As for the dimension of the space, quantum quadratic and linear classifiers achieve varying degrees of polynomial speedup, while quantum naïve Bayes’ classifier achieves an exponential speedup. The only assumption we make is the qRAM to prepare quantum states of the input data.

DOI
10.1088/1751-8121/ab5d77

Related papers

Quadratic Speed‐ups in Quantum Kernelized Binary Classification

Jungyun Lee, Daniel K. Park

Abstract Classification is at the core of data‐driven prediction and decision‐making, representing a fundamental task in supervised machine learning. Recently, several quantum machine learning algorithms that use quantum kernels as a measure of similarities between data have emerged to perform binary classification on datasets encoded as quantum states. The potential advantages of quantum kernels arise from the ability of quantum computers to construct kernels that are more effective than their classical counterparts in capturing patterns in data or computing kernels more efficiently. However, existing quantum kernel‐based classification algorithms do not harness the capability of having data samples in quantum superposition for additional enhancements. This work demonstrates how such capability can be leveraged in quantum kernelized binary classifiers (QKCs) through Quantum Amplitude Estimation (QAE) for quadratic speed‐up. Additionally, new quantum circuits are proposed for the QKCs in which the number of qubits is reduced by one, and the circuit depth is reduced linearly with respect to the number of sample data. The quadratic speed‐up over previous methods is verified through numerical simulations on the Iris dataset.

arXiv:2403.17453•Advanced Quantum Technologies•Jul 8, 2024•3 citations

Quantum Bayes classifiers and their application in image classification

Ming‐Ming Wang, Xiao-Ying Zhang

Bayesian networks are powerful tools for probabilistic analysis and have been widely used in machine learning and data science. Unlike the time-consuming parameter training process of neural networks, Bayes classifiers constructed on Bayesian networks can make decisions based solely on statistical data from samples. In this paper we focus on constructing quantum Bayes classifiers (QBCs). We design both a na\"{\i}ve QBC and three semina\"{\i}ve QBCs (SN-QBCs). These QBCs are then applied to image classification tasks. To reduce computational complexity, we design a local feature sampling method to extract a limited number of feature attributes from an image. These attributes serve as nodes of the Bayesian networks to generate the QBCs. We simulate these QBCs on the MindQuantum platform and evaluate their performance on the MNIST and Fashion-MNIST data sets. Our results demonstrate that these QBCs achieve good classification accuracies even with a limited number of attributes. The classification accuracies of QBCs on the MNIST data set surpass those of classical Bayesian networks and quantum neural networks that utilize all available feature attributes. Additionally, we simulate these QBCs in a quantum noise environment.

arXiv:2401.01588•Physical Review A•Jul 12, 2024•6 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•2,147 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

Quantum ensembles of quantum classifiers

Maria Schuld, Francesco Petruccione

Quantum machine learning witnesses an increasing amount of quantum algorithms for data-driven decision making, a problem with potential applications ranging from automated image recognition to medical diagnosis. Many of those algorithms are implementations of quantum classifiers, or models for the classification of data inputs with a quantum computer. Following the success of collective decision making with ensembles in classical machine learning, this paper introduces the concept of quantum ensembles of quantum classifiers. Creating the ensemble corresponds to a state preparation routine, after which the quantum classifiers are evaluated in parallel and their combined decision is accessed by a single-qubit measurement. This framework naturally allows for exponentially large ensembles in which - similar to Bayesian learning - the individual classifiers do not have to be trained. As an example, we analyse an exponentially large quantum ensemble in which each classifier is weighed according to its performance in classifying the training data, leading to new results for quantum as well as classical machine learning.

arXiv:1704.02146•Scientific Reports•Feb 5, 2018•93 citations

Toward speedup without quantum coherent access

Nhat A. Nghiem

Along with the development of quantum technology, finding useful applications of quantum computers has been a central pursuit. Despite various quantum algorithms have been developed, many of them often require strong input assumptions, which is hardware demanding. In particular, recent advances on dequantization have revealed that the quantum advantage is more of a mere artifact of strong input assumptions. In this work, we propose a variant of these algorithms, leveraging both classical and quantum resources. Provided the classical knowledge (the entries) of the matrix/vector of interest, a classical procedure is used to pre-process this information. Then they are fed into a quantum circuit which is shown to be a block encoding of the matrix of interest. From this block-encoding, we show how to use it to tackle a wide range of problems, including principal component analysis, linear equation solving, Hamiltonian simulation, preparing ground state, and data fitting. We also analyze our protocol, showing that both the classical and quantum procedure can achieve logarithmic complexity in the input dimension, thus implying its potential for near term realization. We then discuss several implications and corollaries of our result. First,, our results suggest there are certain matrices/Hamiltonians where our method can provide exponential improvement compared to the existing ones with respect to the sparsity. Regarding dense linear systems, our method achieves exponential speed-up with respect to the inverse of error tolerance, compared to the best previously known quantum algorithm for dense systems. Last, and most importantly, regarding quantum data fitting, we show how the output of our quantum algorithms can be leveraged to predict unseen data. Thus, it provides an end-to-end application, which has been an open aspect of the previous quantum data fitting algorithm.

quant-pharXiv:2602.20781•Feb 25, 2026•0 citations
Abstract Data classification is a fundamental problem in machine learning. We study quantum speedup of the supervised data classification algorithms (quadratic, linear and naïve Bayes classifiers) based on Bayes’ theory. The main technique we use to achieve quantum speedup is block-encoding. However, to apply this technique effectively, we propose a general method to construct the block-encoding. As an application, we show that all the three classifiers achieve exponential speedup at the number of samples over their classical counterparts. As for the dimension of the space, quantum quadratic and linear classifiers achieve varying degrees of polynomial speedup, while quantum naïve Bayes’ classifier achieves an exponential speedup. The only assumption we make is the qRAM to prepare quantum states of the input data.
Abstract Classification is at the core of data‐driven prediction and decision‐making, representing a fundamental task in supervised machine learning. Recently, several quantum machine learning algorithms that use quantum kernels as a measure of similarities between data have emerged to perform binary classification on datasets encoded as quantum states. The potential advantages of quantum kernels arise from the ability of quantum computers to construct kernels that are more effective than their classical counterparts in capturing patterns in data or computing kernels more efficiently. However, existing quantum kernel‐based classification algorithms do not harness the capability of having data samples in quantum superposition for additional enhancements. This work demonstrates how such capability can be leveraged in quantum kernelized binary classifiers (QKCs) through Quantum Amplitude Estimation (QAE) for quadratic speed‐up. Additionally, new quantum circuits are proposed for the QKCs in which the number of qubits is reduced by one, and the circuit depth is reduced linearly with respect to the number of sample data. The quadratic speed‐up over previous methods is verified through numerical simulations on the Iris dataset.
Bayesian networks are powerful tools for probabilistic analysis and have been widely used in machine learning and data science. Unlike the time-consuming parameter training process of neural networks, Bayes classifiers constructed on Bayesian networks can make decisions based solely on statistical data from samples. In this paper we focus on constructing quantum Bayes classifiers (QBCs). We design both a na\"{\i}ve QBC and three semina\"{\i}ve QBCs (SN-QBCs). These QBCs are then applied to image classification tasks. To reduce computational complexity, we design a local feature sampling method to extract a limited number of feature attributes from an image. These attributes serve as nodes of the Bayesian networks to generate the QBCs. We simulate these QBCs on the MindQuantum platform and evaluate their performance on the MNIST and Fashion-MNIST data sets. Our results demonstrate that these QBCs achieve good classification accuracies even with a limited number of attributes. The classification accuracies of QBCs on the MNIST data set surpass those of classical Bayesian networks and quantum neural networks that utilize all available feature attributes. Additionally, we simulate these QBCs in a quantum noise environment.
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.
Quantum machine learning witnesses an increasing amount of quantum algorithms for data-driven decision making, a problem with potential applications ranging from automated image recognition to medical diagnosis. Many of those algorithms are implementations of quantum classifiers, or models for the classification of data inputs with a quantum computer. Following the success of collective decision making with ensembles in classical machine learning, this paper introduces the concept of quantum ensembles of quantum classifiers. Creating the ensemble corresponds to a state preparation routine, after which the quantum classifiers are evaluated in parallel and their combined decision is accessed by a single-qubit measurement. This framework naturally allows for exponentially large ensembles in which - similar to Bayesian learning - the individual classifiers do not have to be trained. As an example, we analyse an exponentially large quantum ensemble in which each classifier is weighed according to its performance in classifying the training data, leading to new results for quantum as well as classical machine learning.
Along with the development of quantum technology, finding useful applications of quantum computers has been a central pursuit. Despite various quantum algorithms have been developed, many of them often require strong input assumptions, which is hardware demanding. In particular, recent advances on dequantization have revealed that the quantum advantage is more of a mere artifact of strong input assumptions. In this work, we propose a variant of these algorithms, leveraging both classical and quantum resources. Provided the classical knowledge (the entries) of the matrix/vector of interest, a classical procedure is used to pre-process this information. Then they are fed into a quantum circuit which is shown to be a block encoding of the matrix of interest. From this block-encoding, we show how to use it to tackle a wide range of problems, including principal component analysis, linear equation solving, Hamiltonian simulation, preparing ground state, and data fitting. We also analyze our protocol, showing that both the classical and quantum procedure can achieve logarithmic complexity in the input dimension, thus implying its potential for near term realization. We then discuss several implications and corollaries of our result. First,, our results suggest there are certain matrices/Hamiltonians where our method can provide exponential improvement compared to the existing ones with respect to the sparsity. Regarding dense linear systems, our method achieves exponential speed-up with respect to the inverse of error tolerance, compared to the best previously known quantum algorithm for dense systems. Last, and most importantly, regarding quantum data fitting, we show how the output of our quantum algorithms can be leveraged to predict unseen data. Thus, it provides an end-to-end application, which has been an open aspect of the previous quantum data fitting algorithm.