# Quantum speedup in Bayesian machine learning on NISQ computers

It is well known that in Bayesian learning, applying Bayes' theorem requires knowledge on how the data is distributed, and this usually requires either expensive integrals or some sampling mechanism, and, using Bayesian machine learning, (instead of Frequentist) has a significant computation cost that is required to perform the Bayesian inferences, and it could be solved with quantum computers, do you think there is a speedup using Bayesian machine learning algorithms in NISQ machines like IBM Q?

There are libraries available for QML using Qiskit and PennyLane with TensorFlow.

Also, Pycm4, Zhusuan, and Edward 2.0 will have TensorFlow backend So, I am actually interested in "Quantum Bayesian machine learning" I am about to start a master program in CS.

Is it a good idea to work/research in Bayesian QML using TensorFlow with Qiskit, PennyLane, and PyMC4 in order to run bayesian machine learning algorithms in IBM Q?

Does it have any useful approach to data science?

As far as I know, there are four possibilities for having a quantum advantage in Bayesian machine learning:

1. Gaussian processes: there is a known quantum speed-up for Gaussian processes that you can easily test on IBM Q [1,2]. The idea is to use HHL (quantum algorithm for matrix inversion) in order to compute the inverse of the kernel matrix, which is used to estimate the mean and variance estimators of your Gaussian process. It provides a exponential speed-up in the best case (sparse kernel matrix), and polynomial (quadratic) in the worst. The experiments in [2] show limited advantage for NISQ, but it is worth considering when we will have bigger devices.

2. MAP inference for mixture models of distributions in the exponential family: there is another speed-up for the Expectation-Maximization (EM) algorithm used for MAP inference (maximum likelihood with a prior) [6]. More precisely, the quantum algorithm is exponentially faster in the number of training point than classical EM. The caveat is that it requires to encode the data in a QRAM, which is not really NISQy (requires a lot of qubits and a fast algorithm to perform this encoding)

3. Energy-based model: there is also a lot of work on quantum energy-based model [3-5], which you could argue are Bayesian in spirit. The general idea of energy-based models is to find the parameters $$\theta$$ of the probability distribution $$p(x |\theta)=\frac{1}{Z_{\theta}}e^{-\beta E(x, \theta)}$$ that fits your data the best. In classical energy-based model, $$E(x, \theta)$$ is a number, usually given by the classical Ising model $$E(x, \theta)=\sum_{ij} \theta_{ij} x_i x_j$$ and $$Z_{\theta}$$ is a normalization factor that is in general very hard to compute. In the quantum case, we replace the probability distribution by a density matrix $$\rho(\theta)=\frac{1}{Z_{\theta}} e^{-\beta H(\theta)}$$ and the energy function by a Hermitian matrix: $$H(\theta)=\sum_{ij} \theta_{ij} \hat{\sigma}^z_i \hat{\sigma}^z_j + \sum_i \hat{\sigma}^x_i,$$ taking advantage of both thermal and quantum fluctuations in the generative process. [3] introduced the idea and showed examples of speed-ups on toy models, while [4] and [5] are example on how you can train such a generative model on NISQ devices.

4. Bayesian inference: the previous examples are not exactly quantum Bayesian inference as you probably imagined it in your question (computing the explicit posterior distribution by approximating the partition function---i.e. the expansive integral---on a quantum computer). The thing is that for energy-based model, computing the partition function exactly is #P-Hard in general and NP-Hard for local Hamiltonians (a simpler class of energy-based models), so non-tractable even for a quantum computer. However, a quantum speed-up is possible for additive approximations of the partition function, as explained in those slides. But I don't know any paper that explicitly does that in the context of Bayesian machine learning.

I am about to start a master program in CS Is it a good idea to work/research in Bayesian QML using TensorFlow with Qiskit, PennyLane, and PyMC4 in order to run Bayesian machine learning algorithms in IBM Q?

I think so. Reproducing [2] or [4] using Pennylane (with a Qiskit backend) can be a very good exercise to learn quantum computing. If you want to do research on the subject, it would be better to do your master's thesis in a group with people who work in that area (look at the authors of the papers I've cited). Doing it alone (or with a pure-CS Professor) would be very challenging.

[1] Zhao et al., Quantum algorithms for training Gaussian Processes, Phys. Rev. A, 2018

[2] Zhao et al., Bayesian Deep Learning on a Quantum Computer, Quantum Machine Intelligence, 2018

[3] Amin et al., Quantum Boltzmann Machines, Phys. Rev. X, 2016

[4] Verdon et al., A quantum algorithm to train neural networks using low-depth circuits, arXiv, 2017

[5] Verdon et al., Quantum Hamiltonian-Based Models & the Variational Quantum Thermalizer Algorithm, arXiv, 2019

[6] Kerenidis et al., Quantum Expectation-Maximization for Gaussian Mixture Models, arXiv, 2019