Quantum Inference on Bayesian Networks

Abstract

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 $\mathcal{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 $\mathcal{O}(n{2}^{m}P(e{)}^{-\frac{1}{2}})$ 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.

8 pages, 3 figures. Submitted to PRX

References in corpus (4)

• Quantum reinforcement learning
• Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence (1999)
• Data Analysis with Bayesian Networks: A Bootstrap Approach
• Linear-Depth Quantum Circuits for n-qubit Toffoli gates with no Ancilla

Cited by in corpus (29)

• Quantum Machine Learning
• Quantum machine learning in feature Hilbert spaces
• Parameterized quantum circuits as machine learning models
• Quantum computing for finance: overview and prospects
• Continuous-variable quantum neural networks
• Quantum computing for finance
• Differentiable Learning of Quantum Circuit Born Machine
• Is quantum advantage the right goal for quantum machine learning?
• The prospects of quantum computing in computational molecular biology
• Quantum Machine Learning for Chemistry and Physics
• Quantum Machine Learning: from physics to software engineering
• Learning and Inference on Generative Adversarial Quantum Circuits
• Enhancing Generative Models via Quantum Correlations
• Quantum Algorithms for Compositional Natural Language Processing
• Variational inference with a quantum computer
• Variational quantum amplitude estimation
• Quantum Machine Learning in Drug Discovery: Applications in Academia and Pharmaceutical Industries
• Machine learning \& artificial intelligence in the quantum domain
• Representation of binary classification trees with binary features by quantum circuits
• Mutual Information Scaling for Tensor Network Machine Learning
• Discriminating Quantum States with Quantum Machine Learning
• Communication-efficient Quantum Algorithm for Distributed Machine Learning
• Bayesian Learning of Parameterised Quantum Circuits
• On Quantum Circuits for Discrete Graphical Models
• Experimentally detecting a quantum change point via Bayesian inference
• Preparing Many Copies of a Quantum State in the Black-Box Model
• Scalable Quantum Computational Science: A Perspective from Block-Encodings and Polynomial Transformations
• EQNN: Enhanced Quantum Neural Network
• k-Contextuality as a Heuristic for Memory Separations in Learning