Byskit plants an initial step towards taking full advantage of the amplitude amplification when running discrete Bayesian networks on a quantum computer. It provides the ability to easily translate a simple classical discrete Bayesian network to its corresponding quantum circuit.
A Bayesian network is a probabilistic model that graphically represents random variables and the conditional dependencies between them. The model is based on a directed acyclic graph with nodes representing random variables and the directed edges between them representing their conditional dependencies. These dependencies are modelled with conditional probability distributions or tables.
These probability distributions can either be specified manually or learned using data. Once they are populated, we can use the network to make inferences of different types. For instance, we can make predictions about outcomes based on a set of inputs, or we can make diagnoses where we infer what inputs may have led to an observed outcome. These inferences can be exact or approximate.
The main graph in this slide is simple, with a child and two roots. However, Bayesian networks can be arbitrarily complex - see the example to the right. Performing exact inference on bayesian networks is sharp-P hard, meaning they become classically intractable as they grow very large. We can use approximate inference to avoid this, but this is still NP hard generally. Approximate inference uses other techniques such as Markov Chain Monte Carlo sampling or rejection sampling methods to speed up inference.
By implementing a bayesian network on quantum hardware, it is possible to obtain a square root speedup of rejection sampling of a Bayesian network. This is based on the principle of amplitude amplification, which is the generalisation of Grover’s algorithm, to facilitate a quantum version of rejection sampling. Quantum rejection sampling has been implemented and demonstrated on toy problems such as stock price prediction and bankruptcy protection.
The probability of each node’s outcome is mapped to a probability amplitude in a qubit by preparing each one in a specified state. Where in the graph representation we would propagate the probabilities through each layer, in the quantum hardware implementation we use qubit gates to change the states of control qubits and subsequently read out the measurement qubit to take a sample.
We begin by defining the connectivity and probabilities of the Bayesian network. Then to generate the quantum implementation of the network Byskit:
