# Quantum Inference on Bayesian Networks

arXiv: https://arxiv.org/abs/1402.7359 · HTML: https://mlsanity.com/paper/1402.7359/

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Feb 2014.

## Built on by (most cited first, 19 of 19)

- [Enhancing Generative Models via Quantum Correlations](https://mlsanity.com/paper/2101.08354/) (2021)
- [Variational inference with a quantum computer](https://mlsanity.com/paper/2103.06720/) (2021)
- [Quantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constants](https://mlsanity.com/paper/2210.06539/) (2022)
- [Representation of binary classification trees with binary features by quantum circuits](https://mlsanity.com/paper/2108.13207/) (2021)
- [Qiskit Machine Learning: an open-source library for quantum machine learning tasks at scale on quantum hardware and classical simulators](https://mlsanity.com/paper/2505.17756/) (2025)
- [On Quantum Circuits for Discrete Graphical Models](https://mlsanity.com/paper/2206.00398/) (2022)
- [Bayesian Learning of Parameterised Quantum Circuits](https://mlsanity.com/paper/2206.07559/) (2022)
- [BF-QC: Belief Functions on Quantum Circuits](https://mlsanity.com/paper/2107.03930/) (2021)
- [Discriminating Quantum States with Quantum Machine Learning](https://mlsanity.com/paper/2112.00313/) (2021)
- [Quantum Speedup of Natural Gradient for Variational Bayes](https://mlsanity.com/paper/2106.05807/) (2021)
- [An Introduction to Quantum Computing for Statisticians and Data Scientists](https://mlsanity.com/paper/2112.06587/) (2021)
- [Quantum Bayesian Networks Can Speed up Reinforcement Learning in Partially Observable Environments](https://mlsanity.com/paper/2507.18606/) (2025)
- [Trustworthy Quantum Machine Learning: A Roadmap for Reliability, Robustness, and Security in the NISQ Era](https://mlsanity.com/paper/2511.02602/) (2025)
- [CQural: A Novel CNN based Hybrid Architecture for Quantum Continual Machine Learning](https://mlsanity.com/paper/2305.09738/) (2023)
- [Quantum Information Fusion and Correction under the Transferable Belief Model](https://mlsanity.com/paper/2410.08949/) (2024)
- [EQNN: Enhanced Quantum Neural Network](https://mlsanity.com/paper/2411.17726/) (2024)
- [Quantum Approximate Optimization Algorithm for Spatiotemporal Forecasting of HIV Clusters](https://mlsanity.com/paper/2507.00848/) (2025)
- [An End-to-End Hybrid Quantum-Classical Sampling Workflow for Discrete Markov Random Fields: A Reproducible Case Study](https://mlsanity.com/paper/2607.09893/) (2026)
- [Towards unsupervised representation learning for quantum data: quantum models with inference and generation](https://mlsanity.com/paper/2609.00372/) (2026)

## Abstract (arXiv)

Performing exact inference on Bayesian networks is known to be #P-hard. Typically approximate inference techniques are used instead to sample from the distribution on query variables given the values e of evidence variables. Classically, a single unbiased sample is obtained from a Bayesian network on n variables with at most m parents per node in time O(nmP(e)-1), depending critically on P(e), the probability the evidence might occur in the first place. By implementing a quantum version of rejection sampling, we obtain a square-root speedup, taking O(n2mP(e)-frac12) time per sample. We exploit the Bayesian network's graph structure to efficiently construct a quantum state, a q-sample, representing the intended classical distribution, and also to efficiently apply amplitude amplification, the source of our speedup. Thus, our speedup is notable as it is unrelativized -- we count primitive operations and require no blackbox oracle queries.