Bayesian Network Structure Learning Using Quantum Annealing

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 $\mathcal{O}(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.

References in corpus (21)

• Quantum Annealing in the Transverse Ising Model
• Quantum Annealing and Analog Quantum Computation
• Defining and detecting quantum speedup
• Data Analysis with Bayesian Networks: A Bootstrap Approach
• Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design
• A practical heuristic for finding graph minors
• A case study in programming a quantum annealer for hard operational planning problems
• Quantum Optimization of Fully-Connected Spin Glasses
• Quantum Speedup by Quantum Annealing
• Optimized simulated annealing for Ising spin glasses
• On the construction of model Hamiltonians for adiabatic quantum computation and its application to finding low energy conformations of lattice protein models
• Experimental determination of Ramsey numbers
• A Quantum Annealing Approach for Fault Detection and Diagnosis of Graph-Based Systems
• Graph isomorphism and adiabatic quantum computing
• Bayesian network learning by compiling to weighted MAX-SAT
• Construction of Energy Functions for Lattice Heteropolymer Models: A Case Study in Constraint Satisfaction Programming and Adiabatic Quantum Optimization
• On Quadratization of Pseudo-Boolean Functions
• Resource Efficient Gadgets for Compiling Adiabatic Quantum Optimization Problems
• An Introduction to Quantum Bayesian Networks for Mixed States
• Construction of non-convex polynomial loss functions for training a binary classifier with quantum annealing
• Quantum Circuit For Discovering from Data the Structure of Classical Bayesian Networks

Cited by in corpus (32)

• Quantum Machine Learning
• Noisy intermediate-scale quantum (NISQ) algorithms
• Quantum machine learning in feature Hilbert spaces
• Adiabatic Quantum Computing
• Prediction by linear regression on a quantum computer
• A case study in programming a quantum annealer for hard operational planning problems
• Estimation of effective temperatures in quantum annealers for sampling applications: A case study with possible applications in deep learning
• Quantum Optimization of Fully-Connected Spin Glasses
• Quantum Algorithm for Linear Regression
• Quantum-Assisted Learning of Hardware-Embedded Probabilistic Graphical Models
• Quantum Machine Learning: from physics to software engineering
• A Quantum Annealing Approach for Fault Detection and Diagnosis of Graph-Based Systems
• Circuit design for multi-body interactions in superconducting quantum annealing system with applications to a scalable architecture
• Basic Elements for Simulations of Standard Model Physics with Quantum Annealers: Multigrid and Clock States
• Variational inference with a quantum computer
• Maximum-Entropy Inference with a Programmable Annealer
• Readiness of Quantum Optimization Machines for Industrial Applications
• Machine learning \& artificial intelligence in the quantum domain
• Model Predictive Control for Finite Input Systems using the D-Wave Quantum Annealer
• Completely Quantum Neural Networks
• Quantum Enhanced Inference in Markov Logic Networks
• A Performance Estimator for Quantum Annealers: Gauge selection and Parameter Setting
• Quantum adiabatic machine learning with zooming
• Adiabatic Quantum Optimization for Associative Memory Recall
• Quantum-assisted finite-element design optimization
• QUBO Decision Tree: Annealing Machine Extends Decision Tree Splitting
• Bayesian Networks based Hybrid Quantum-Classical Machine Learning Approach to Elucidate Gene Regulatory Pathways
• Reconstructing Bayesian Networks on a Quantum Annealer
• Classical Simulated Annealing Using Quantum Analogues
• A QUBO Model for Gaussian Process Variance Reduction
• QUBO-inspired Molecular Fingerprint for Chemical Property Prediction
• Statistical Analysis of Quantum Annealing