Quantum inference on Bayesian networks
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 o...
| Main Authors: | , , |
|---|---|
| 其他作者: | |
| 格式: | 文件 |
| 语言: | English |
| 出版: |
American Physical Society
2014
|
| 在线阅读: | http://hdl.handle.net/1721.1/88648 https://orcid.org/0000-0001-7296-523X https://orcid.org/0000-0002-6211-982X https://orcid.org/0000-0001-9614-2836 |
| _version_ | 1826189626177486848 |
|---|---|
| author | Low, Guang Hao Yoder, Theodore James Chuang, Isaac L. |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Low, Guang Hao Yoder, Theodore James Chuang, Isaac L. |
| author_sort | Low, Guang Hao |
| collection | MIT |
| 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. |
| first_indexed | 2024-09-23T08:18:53Z |
| format | Article |
| id | mit-1721.1/88648 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T08:18:53Z |
| publishDate | 2014 |
| publisher | American Physical Society |
| record_format | dspace |
| spelling | mit-1721.1/886482022-09-23T12:12:21Z Quantum inference on Bayesian networks Low, Guang Hao Yoder, Theodore James Chuang, Isaac L. 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. 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 2014-08-11T13:14:33Z 2014-08-11T13:14:33Z 2014-06 2014-02 2014-07-23T20:47:47Z Article http://purl.org/eprint/type/JournalArticle 1050-2947 1094-1622 http://hdl.handle.net/1721.1/88648 Low, Guang Hao, Theodore J. Yoder, and Isaac L. Chuang. “Quantum Inference on Bayesian Networks.” Phys. Rev. A 89, no. 6 (June 2014). © 2014 American Physical Society https://orcid.org/0000-0001-7296-523X https://orcid.org/0000-0002-6211-982X https://orcid.org/0000-0001-9614-2836 en http://dx.doi.org/10.1103/PhysRevA.89.062315 Physical Review A Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. American Physical Society application/pdf American Physical Society American Physical Society |
| spellingShingle | Low, Guang Hao Yoder, Theodore James Chuang, Isaac L. Quantum inference on Bayesian networks |
| title | Quantum inference on Bayesian networks |
| title_full | Quantum inference on Bayesian networks |
| title_fullStr | Quantum inference on Bayesian networks |
| title_full_unstemmed | Quantum inference on Bayesian networks |
| title_short | Quantum inference on Bayesian networks |
| title_sort | quantum inference on bayesian networks |
| url | http://hdl.handle.net/1721.1/88648 https://orcid.org/0000-0001-7296-523X https://orcid.org/0000-0002-6211-982X https://orcid.org/0000-0001-9614-2836 |
| work_keys_str_mv | AT lowguanghao quantuminferenceonbayesiannetworks AT yodertheodorejames quantuminferenceonbayesiannetworks AT chuangisaacl quantuminferenceonbayesiannetworks |