Quantum speedup of Bayes’ classifiers

Changpeng Shao

Research output: Contribution to journalArticle (Academic Journal)peer-review

9 Citations (Scopus)
219 Downloads (Pure)


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.
Original languageEnglish
Article number045301
Number of pages26
JournalJournal of Physics A
Publication statusPublished - 3 Jan 2020


  • quantum algorithms
  • quantum computing
  • Bayes’ classifiers
  • machine learning


Dive into the research topics of 'Quantum speedup of Bayes’ classifiers'. Together they form a unique fingerprint.

Cite this