Quantum speedup of Bayes’ classifiers

Research output: Contribution to journalArticle (Academic Journal)

1 Downloads (Pure)

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

Keywords

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

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

Cite this