Quantum inference on Bayesian networks

Guang Hao Low, Theodore J. Yoder, and Isaac L. Chuang
Phys. Rev. A 89, 062315 – Published 13 June 2014

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 O(nmP(e)1), depending critically on P(e), the probability that 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)12) 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.

  • Figure
  • Figure
  • Figure
  • Received 28 February 2014

DOI:https://doi.org/10.1103/PhysRevA.89.062315

©2014 American Physical Society

Authors & Affiliations

Guang Hao Low, Theodore J. Yoder, and Isaac L. Chuang

  • Massachusetts Institute of Technology, 77 Massachusetts Avenue, Cambridge, Massachusetts 02139, USA

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 89, Iss. 6 — June 2014

Reuse & Permissions
Access Options
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review A

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×