Abstract
We introduce a method for the problem of learning the structure of a Bayesian network using the quantum adiabatic algorithm. We do so by introducing an efficient reformulation of a standard posterior-probability scoring function on graphs as a pseudo-Boolean function, which is equivalent to a system of 2-body Ising spins, as well as suitable penalty terms for enforcing the constraints necessary for the reformulation; our proposed method requires 𝓞(n 2) qubits for n Bayesian network variables. Furthermore, we prove lower bounds on the necessary weighting of these penalty terms. The logical structure resulting from the mapping has the appealing property that it is instance-independent for a given number of Bayesian network variables, as well as being independent of the number of data cases.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
D. Koller, N. Friedman, Probabilistic Graphical Models: Principles and Techniques - Adaptive Computation and Machine Learning (The MIT Press, 2009)
D. Yu, X. Huang, H. Wang, Y. Cui, Q. Hu, R. Zhou, ApJ 710, 869 2010
A. Djebbari, J. Quackenbush, BMC Syst. Biol. 2, 57 2008
N. Friedman, M. Linial, I. Nachman, D. Pe’er, Using Bayesian networks to analyze expression data. In Proceedings of the Fourth Annual International Conference on Computational Molecular Biology, RECOMB ’00 (New York, NY, USA, 2000. ACM), p. 121
D. Maxwell Chickering, Learning Bayesian networks is np-complete (1996), p. 121
S. Aaronson, BQP and the polynomial hierarchy. In Proceedings of the Forty-second ACM Symposium on Theory of Computing, STOC ’10 (New York, NY, USA, 2010, ACM), p. 141
L.K. Grover, A fast quantum mechanical algorithm for database search. In Proceedings of the Twenty-eighth Annual ACM Symposium on Theory of Computing, STOC ’96 (New York, NY, USA, 1996, ACM), p. 212
R.D. Somma, D. Nagaj, M. Kieferová, Phys. Rev. Lett. 109, 050501 (2012)
T.F. Rønnow, Z. Wang, J. Job, S. Boixo, S.V. Isakov, D. Wecker, J.M. Martinis, D.A. Lidar, M. Troyer, Science (2014)
D. Venturelli, S. Mandrà, S. Knysh, B. O’Gorman, R. Biswas, V. Smelyanskiy, Quantum optimization of fully-connected spin glasses (2014)
R.R. Tucci, An introduction to quantum Bayesian networks for mixed states (2012)
R.R. Tucci, Quantum circuit for discovering from data the structure of classical Bayesian networks (2014)
R. Babbush, A. Perdomo-Ortiz, B. O’Gorman, W. Macready, A. Aspuru-Guzik, Construction of Energy Functions for Lattice Heteropolymer Models: Efficient Encodings for Constraint Satisfaction Programming and Quantum Annealing (John Wiley & Sons, Inc., 2014), p. 201
A. Perdomo-Ortiz, N. Dickson, M. Drew-Brook, G. Rose, A. Aspuru-Guzik, Scientific Reports 2 (2012)
E.G. Rieffel, D. Venturelli, B. O’Gorman, M. Do, E. Prystay, V. Smelyanskiy, A case study in programming a quantum annealer for hard operational planning problems (submitted) (2014)
A. Perdomo-Ortiz, J. Fluegemann, S. Narasimhan, V. Smelyanskiy, R. Biswas, A quantum annealing approach for fault detection and diagnosis of graph-based systems (submitted) (2014)
F. Gaitan, L. Clark, Phys. Rev. A 89, 022342 (2014)
R. Babbush, V. Denchev, N. Ding, S. Isakov, H. Neven, Construction of non-convex polynomial loss functions for training a binary classifier with quantum annealing (2014)
V.S. Denchev, Binary Classification with Adiabatic Quantum Optimization, Ph.D. thesis, Purdue University, 2013
Z. Bian, F. Chudak, W.G. Macready, L. Clark, F. Gaitan, Phys. Rev. Lett. 111, 130505 (2013)
J. Cussens, Bayesian network learning by compiling to weighted MAX-SAT. In UAI (2008), p. 105
S.V. Isakov, I.N. Zintchenko, T.F. Rønnow, M. Troyer, Optimized simulated annealing code for Ising spin glasses (2014)
D. Heckerman, D. Geiger, D. Maxwell Chickering, Mach. Learning 20, 197 (1995)
T. Kadowaki, H. Nishimori, Phys. Rev. E 58, 5355 (1998)
P. Ray, B.K. Chakrabarti, A. Chakrabarti, Phys. Rev. B 39, 11828 (1989)
A. Das, B.K. Chakrabarti, Rev. Mod. Phys. 80, 1061 (2008)
E. Farhi, J. Goldstone, S. Gutmann, M. Sipser, Quantum computation by adiabatic evolution (2000)
R. Oliveira, B.M. Terhal. Quantum Info. Comput. 8, 900 (2008)
W.M. Kaminsky, S. Lloyd. Scalable architecture for adiabatic quantum computing of np-hard problems, edited by A.J. Leggett, B. Ruggiero, P. Silvestrini, Quantum Computing and Quantum Bits in Mesoscopic Systems (Springer US, 2004), p. 229
A. Perdomo, C. Truncik, I. Tubert-Brohman, G. Rose, A. Aspuru-Guzik. Phys. Rev. A 78, 012320 (2008)
V. Choi, Quant. Inf. Proc. 7, 193 (2008)
V. Choi, Quant. Inf. Proc. 10, 343 (2011)
J. Cai, W.G. Macready, A. Roy, A practical heuristic for finding graph minors (2014)
R. Babbush, B. O’Gorman, A. Aspuru-Guzik, Annal. Phys. 525, 877 (2013)
N. Friedman, M. Goldszmidt, A. Wyner, Data analysis with Bayesian networks: A bootstrap approach. In Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence, UAI’99 (San Francisco, CA, USA, Morgan Kaufmann Publishers Inc, 1999), p. 196
E. Boros, A. Gruber, On quadratization of pseudo-Boolean functions, CoRR, abs/1404.6538 (2014)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
O’Gorman, B., Babbush, R., Perdomo-Ortiz, A. et al. Bayesian network structure learning using quantum annealing. Eur. Phys. J. Spec. Top. 224, 163–188 (2015). https://doi.org/10.1140/epjst/e2015-02349-9
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1140/epjst/e2015-02349-9