Systems and methods for quantum bayesian networks
Techniques are provided for computing problems represented as directed graphical models via quantum processors with topologies and coupling physics which correspond to undirected graphs. These include techniques for generating approximations of Bayesian networks via a quantum processor capable of computing problems based on a Markov network-based representation of such problems. Approximations may be generated by moralization of Bayesian networks to Markov networks, learning of Bayesian networks' probability distributions by Markov networks' probability distributions, or otherwise, and are trained by executing the resulting Markov network on the quantum processor.
1. A method for quantum computing given a problem represented by a Bayesian network, the method executed by circuitry including at least one processor, the at least one processor in communication with a quantum processor comprising a plurality of qubits and couplers, the couplers operable to symmetrically couple qubits, the method comprising:
obtaining a representation of the problem, the representation of the problem comprising a Bayesian network having a first plurality of nodes and a first plurality of directed edges;
transforming the Bayesian network to a Markov network having a second plurality of nodes and a second plurality of undirected edges;
transmitting the Markov network to the quantum processor and, by said transmitting, causing the quantum processor to execute based on the Markov network;
obtaining one or more samples from the quantum processor; and
determining one or more parameters of the Markov network based on the one or more samples to generate a parametrized Markov network; and
determining an approximation of a predicted solution for the problem based on the parametrized Markov network.
2. The method according to claim 1 wherein transforming the Bayesian network to the Markov network comprises performing moralization of the Bayesian network, moralization comprising marrying parent nodes of the first plurality of nodes and removing directionality from the first plurality of edges.
3. The method according to claim 1 wherein transforming the Bayesian network to the Markov network comprises forming the Markov network based on a subgraph of a graph induced by the quantum processor's qubits and couplers.
4. The method according to claim 3 wherein forming the Markov network comprises forming a Boltzmann machine.
5. The method according to claim 4 wherein forming a Boltzmann machine comprises forming a Chimera-structured restricted Boltzmann machine corresponding to a Chimera-structured topology of the quantum processor.
6. The method according to claim 1 wherein transforming the Bayesian network to the Markov network comprises generating the Markov network based on a topology of the quantum processor and based on a size of the Bayesian network.
7. The method according to claim 6 wherein determining one or more parameters of the Markov network comprises optimizing an objective function of the Bayesian network based on a joint probability distribution corresponding to the Bayesian network.
8. The method according to claim 7 wherein determining one or more parameters of the Markov network comprises performing a positive phase of training based on a classically-tractable feature vector of the Bayesian network and performing a negative phase of training based on the one or more samples from the quantum processor.
9. The method according to claim 8 wherein the Markov network comprises a Boltzmann machine.
10. The method according to claim 1 wherein causing the quantum processor to execute comprises causing the quantum processor to physically bias the plurality of qubits and plurality of couplers to correspond to the nodes and edges of the Markov network, and evolve a state of the quantum processor to generate the one or more samples.
11. A hybrid computational system, comprising:
a quantum processor comprising a plurality of qubits and couplers, the couplers operable to symmetrically couple qubits;
at least one processor in communication with the quantum processor; and
at least one nontransitory processor-readable storage medium that stores at least one of processor-executable instructions or data which, when executed by the at least one processor cause the at least one processor to execute a method having the following acts:
obtaining a representation of the problem, the representation of the problem comprising a Bayesian network having a first plurality of nodes and a first plurality of directed edges;
transforming the Bayesian network to a Markov network having a second plurality of nodes and a second plurality of undirected edges;
transmitting the Markov network to the quantum processor and, by said transmitting, causing the quantum processor to execute based on the Markov network;
obtaining one or more samples from the quantum processor; and
determining one or more parameters of the Markov network based on the one or more samples to generate a parametrized Markov network; and
determining an approximation of a predicted solution for the problem based on the parametrized Markov network.
12. The hybrid computing system according to claim 11 wherein transforming the Bayesian network to the Markov network comprises performing moralization of the Bayesian network, moralization comprising marrying parent nodes of the first plurality of nodes and removing directionality from the first plurality of edges.
13. The hybrid computing system according to claim 11 wherein transforming the Bayesian network to the Markov network comprises forming the Markov network based on a subgraph of a graph induced by the quantum processor's qubits and couplers.
14. The hybrid computing system according to claim 13 wherein forming the Markov network comprises forming a Boltzmann machine.
15. The hybrid computing system according to claim 14 wherein forming a Boltzmann machine comprises forming a Chimera-structured restricted Boltzmann machine corresponding to a Chimera-structured topology of the quantum processor.
16. The hybrid computing system according to claim 11 wherein transforming the Bayesian network to the Markov network comprises generating the Markov network based on a topology of the quantum processor and based on a size of the Bayesian network.
17. The hybrid computing system according to claim 16 wherein determining one or more parameters of the Markov network comprises optimizing an objective function of the Bayesian network based on a joint probability distribution corresponding to the Bayesian network.
18. The hybrid computing system according to claim 17 wherein determining one or more parameters of the Markov network comprises performing a positive phase of training based on a classically-tractable feature vector of the Bayesian network and performing a negative phase of training based on the one or more samples from the quantum processor.
19. The hybrid computing system according to claim 18 wherein the Markov network comprises a Boltzmann machine.
20. The hybrid computing system according to claim 11 wherein causing the quantum processor to execute comprises causing the quantum processor to physically bias the plurality of qubits and plurality of couplers to correspond to the nodes and edges of the Markov network, and evolve a state of the quantum processor to generate the one or more samples.
21. A computational system, comprising:
at least one processor in communication with a quantum processor; and
at least one nontransitory processor-readable storage medium that stores at least one of processor-executable instructions or data which, when executed by the at least one processor cause the at least one processor to execute a method having the following acts:
obtaining a representation of the problem, the representation of the problem comprising a Bayesian network having a first plurality of nodes and a first plurality of directed edges;
transforming the Bayesian network to a Markov network having a second plurality of nodes and a second plurality of undirected edges;
transmitting the Markov network to the quantum processor and, by said transmitting, causing the quantum processor to execute based on the Markov network;
obtaining one or more samples from the quantum processor; and
determining one or more parameters of the Markov network based on the one or more samples to generate a parametrized Markov network; and
determining an approximation of a predicted solution for the problem based on the parametrized Markov network.