| Title: |
Quantum inference on Bayesian networks |
| Authors: |
Low, Guang Hao; Yoder, Theodore James; Chuang, Isaac L. |
| Contributors: |
Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science; Massachusetts Institute of Technology. Department of Physics; Low, Guang Hao; Yoder, Theodore James; Chuang, Isaac L. |
| Source: |
American Physical Society |
| Publisher Information: |
American Physical Society |
| Publication Year: |
2014 |
| Subject Terms: |
stat; phil |
| Description: |
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)[superscript −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(n2[superscript m]P(e)[superscript −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. ; United States. Army Research Office (Project W911NF1210486) ; National Science Foundation (U.S.). Integrative Graduate Education and Research Traineeship ; National Science Foundation (U.S.). Center for Ultracold Atoms |
| Document Type: |
article in journal/newspaper |
| Language: |
English |
| Relation: |
http://hdl.handle.net/1721.1/88648 |
| Availability: |
http://hdl.handle.net/1721.1/88648 |
| Rights: |
undefined |
| Accession Number: |
edsbas.BC476CCD |
| Database: |
BASE |