Patent Publication Number: US-11386346-B2

Title: Systems and methods for quantum bayesian networks

Description:
FIELD 
     This disclosure generally relates to analog computing, and in particular to quantum machine learning. 
     BACKGROUND 
     Machine learning models are often represented by graphical models, such as probabilistic graphical models which reflect probabilistic structures of model variables. Probabilistic graphical models typically comprise either directed or undirected graphs. 
     Directed graphs can represent causal relationships explicitly via directed edges, which allows for relatively compact representations of probability distributions. A special case of the directed graph is the Bayesian network (also known as a directed acyclic graph). Bayesian networks allow for straightforward determination of conditional probabilities based only on parent nodes. 
     Undirected graphs do not provide explicit dependencies via directed edges. Undirected graphs thus typically are relatively less compact, require more variables, are more challenging to train and infer, and are more powerful relative to directed graphs. A special case of the undirected graph is the Markov network. Both training and inference of Markov networks typically involve making determinations based on a partition function characterizing the network, which is typically NP-hard. 
     Analog processors provide a number of analog computation devices with physical characteristics (often continuously-varying) which can be exploited for computational purposes without necessarily being limited to the execution of binary logical circuits. At least some analog processors provide a plurality of analog computation devices which are controllably coupled to each other by couplers. Such analog processors may be themselves correspond in structure to certain types of graphs (e.g. where computation devices correspond to nodes and couplers correspond to edges) and may thus be naturally adapted to representing graphs of the same or similar types. 
     Analog processors may take many forms. Where analog processors exhibit computationally-relevant quantum mechanical effects (e.g. entanglement, tunneling, or the like), they may be referred to as quantum processors and their computation devices are called qubits. Quantum processors may have a number of qubits, couplers, and associated local bias devices, exemplary embodiments of which are described in, for example, U.S. Pat. Nos. 7,533,068, 8,008,942, 8,195,596, 8,190,548, and 8,421,053. Such quantum processors may operate, for example, via quantum annealing and/or may operate adiabatically. For the sake of convenience, the following disclosure refers generally to “qubits” and “quantum processors”, although those skilled in the art will appreciate that this disclosure may be implemented in systems comprising other analog processors. 
     Some quantum processors, such as exemplary quantum annealing processors described above, provide mutual, symmetric coupling between qubits. Such quantum processors have, for example, been modelled as undirected graphs and used to represent undirected graphs (see, for example, US Patent Publication 2017/0300817). Such techniques have been used to represent, for example, Markov networks (e.g. restricted Boltzmann machines). 
     There has been some exploration of processing Bayesian networks by certain types of quantum computers, such as gate model quantum computers, where gate operations allow asymmetry in couplings (see, e.g., Tucci,  Use of a Quantum Computer to do Importance and Metropolis - Hastings Sampling of a Classical Bayesian Network , arXiv:0811.1792 [quant-ph] and Sakkaris,  QuDot Nets: Quantum Computers and Bayesian Networks , arXiv:1607.07887 [quant-ph]). Such techniques are not directly applicable to certain quantum computers, such as quantum computers with topologies which correspond to undirected graphs. 
     There is thus a general desire for systems and methods for providing directed graphical models in quantum computers with topologies corresponding to undirected graphs. 
     The foregoing examples of the related art and limitations related thereto are intended to be illustrative and not exclusive. Other limitations of the related art will become apparent to those of skill in the art upon a reading of the specification and a study of the drawings. 
     BRIEF SUMMARY 
     Computational systems and methods are described which, at least in some implementations, allow for the computation of at least some problems by certain quantum processors where the problems are represented as directed graphical models and the quantum processor provides a hardware topology and coupling physics which correspond to an undirected graphical representation. 
     Aspects of the present disclosure provide systems and methods for quantum computing given a problem represented by a Bayesian network. The system comprises circuitry including at least one processor. The at least one processor is in communication with a quantum processor comprising a plurality of qubits and couplers. The couplers are operable to symmetrically couple qubits. The system executes the method. 
     The method comprises 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; 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 prediction for the problem based on the parametrized Markov network. 
     In some implementations, transforming the Bayesian network to the Markov network comprises moralization of the Bayesian network. Moralization comprises marrying parent nodes of the first plurality of nodes and removing directionality from the first plurality of edges. 
     In some implementations, 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&#39;s qubits and couplers. In some implementations, forming the Markov network comprises forming a Boltzmann machine. In some implementations, forming a Boltzmann machine comprises forming a Chimera-structured restricted Boltzmann machine corresponding to a Chimera-structured topology of the quantum processor. 
     In some implementations, 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. In some implementations, 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. In some implementations, 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. In some implementations, the Markov network comprises a Boltzmann machine. 
     In some implementations, 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. 
    
    
     
       BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWING(S) 
       In the drawings, identical reference numbers identify similar elements or acts. The sizes and relative positions of elements in the drawings are not necessarily drawn to scale. For example, the shapes of various elements and angles are not necessarily drawn to scale, and some of these elements may be arbitrarily enlarged and positioned to improve drawing legibility. Further, the particular shapes of the elements as drawn, are not necessarily intended to convey any information regarding the actual shape of the particular elements, and may have been solely selected for ease of recognition in the drawings. 
         FIG. 1  is a schematic diagram of an exemplary hybrid computer including a digital computer and an analog computer in accordance with the present systems, devices, methods, and articles. 
         FIG. 2  is a flowchart of an exemplary method for computing problems represented by Bayesian networks by a quantum computer. 
         FIG. 3  is a schematic diagram of an example Bayesian network and a transformation of the Bayesian network into an approximately-corresponding Markov network. 
     
    
    
     DETAILED DESCRIPTION 
     The present disclosure provides systems and methods for computing problems represented as directed graphical models with quantum processors with topologies and coupling physics which correspond to undirected graphs. In particular, at least some implementations of the presently-disclosed systems and methods provide techniques for generating approximations of Bayesian networks via a quantum processor capable of computing problems based on a Markov network-representation of such problems. 
     Introductory Generalities 
     In the following description, certain specific details are set forth in order to provide a thorough understanding of various disclosed implementations. However, one skilled in the relevant art will recognize that implementations may be practiced without one or more of these specific details, or with other methods, components, materials, etc. In other instances, well-known structures associated with computer systems, server computers, and/or communications networks have not been shown or described in detail to avoid unnecessarily obscuring descriptions of the implementations. 
     Unless the context requires otherwise, throughout the specification and claims that follow, the word “comprising” is synonymous with “including,” and is inclusive or open-ended (i.e., does not exclude additional, unrecited elements or method acts). 
     Reference throughout this specification to “one implementation” or “an implementation” means that a particular feature, structure or characteristic described in connection with the implementation is included in at least one implementation. Thus, the appearances of the phrases “in one implementation” or “in an implementation” in various places throughout this specification are not necessarily all referring to the same implementation. Furthermore, the particular features, structures, or characteristics may be combined in any suitable manner in one or more implementations. 
     As used in this specification and the appended claims, the singular forms “a,” “an,” and “the” include plural referents unless the context clearly dictates otherwise. It should also be noted that the term “or” is generally employed in its sense including “and/or” unless the context clearly dictates otherwise. 
     The headings and Abstract of the Disclosure provided herein are for convenience only and do not interpret the scope or meaning of the implementations. 
     Computing Systems 
       FIG. 1  illustrates a computing system  100  comprising a digital computer  102 . The example digital computer  102  includes one or more digital processors  106  that may be used to perform classical digital processing tasks. Digital computer  102  may further include at least one system memory  108 , and at least one system bus  110  that couples various system components, including system memory  108  to digital processor(s)  106 . System memory  108  may store a VAE instructions module  112 . 
     The digital processor(s)  106  may be any logic processing unit or circuitry (e.g., integrated circuits), such as one or more central processing units (“CPUs”), graphics processing units (“GPUs”), digital signal processors (“DSPs”), application-specific integrated circuits (“ASICs”), programmable gate arrays (“FPGAs”), programmable logic controllers (“PLCs”), etc., and/or combinations of the same. 
     In some implementations, computing system  100  comprises an analog computer  104 , which may include one or more quantum processors  114 . Digital computer  102  may communicate with analog computer  104  via, for instance, a controller  126 . Certain computations may be performed by analog computer  104  at the instruction of digital computer  102 , as described in greater detail herein. 
     Digital computer  102  may include a user input/output subsystem  116 . In some implementations, the user input/output subsystem includes one or more user input/output components such as a display  118 , mouse  120 , and/or keyboard  122 . 
     System bus  110  can employ any known bus structures or architectures, including a memory bus with a memory controller, a peripheral bus, and a local bus. System memory  108  may include non-volatile memory, such as read-only memory (“ROM”), static random access memory (“SRAM”), Flash NAND; and volatile memory such as random access memory (“RAM”) (not shown). 
     Digital computer  102  may also include other non-transitory computer- or processor-readable storage media or non-volatile memory  124 . Non-volatile memory  124  may take a variety of forms, including: a hard disk drive for reading from and writing to a hard disk (e.g., magnetic disk), an optical disk drive for reading from and writing to removable optical disks, and/or a solid state drive (SSD) for reading from and writing to solid state media (e.g., NAND-based Flash memory). The optical disk can be a CD-ROM or DVD, while the magnetic disk can be a rigid spinning magnetic disk or a magnetic floppy disk or diskette. Non-volatile memory  124  may communicate with digital processor(s) via system bus  110  and may include appropriate interfaces or controllers  126  coupled to system bus  110 . Non-volatile memory  124  may serve as long-term storage for processor- or computer-readable instructions, data structures, or other data (sometimes called program modules) for digital computer  102 . 
     Although digital computer  102  has been described as employing hard disks, optical disks and/or solid state storage media, those skilled in the relevant art will appreciate that other types of nontransitory and non-volatile computer-readable media may be employed, such magnetic cassettes, flash memory cards, Flash, ROMs, smart cards, etc. Those skilled in the relevant art will appreciate that some computer architectures employ nontransitory volatile memory and nontransitory non-volatile memory. For example, data in volatile memory can be cached to non-volatile memory. Or a solid-state disk that employs integrated circuits to provide non-volatile memory. 
     Various processor- or computer-readable instructions, data structures, or other data can be stored in system memory  108 . For example, system memory  108  may store instruction for communicating with remote clients and scheduling use of resources including resources on the digital computer  102  and analog computer  104 . Also for example, system memory  108  may store at least one of processor executable instructions or data that, when executed by at least one processor, causes the at least one processor to execute the various algorithms described elsewhere herein, including machine learning related algorithms. For instance, system memory  108  may store a machine learning instructions module  112  that includes processor- or computer-readable instructions to provide a machine learning model, such as a variational autoencoder. Such provision may comprise training and/or performing inference with the machine learning model, e.g., as described in greater detail herein. 
     In some implementations system memory  108  may store processor- or computer-readable calculation instructions and/or data to perform pre-processing, co-processing, and post-processing to analog computer  104 . System memory  108  may store a set of analog computer interface instructions to interact with analog computer  104 . When executed, the stored instructions and/or data cause the system to operate as a special purpose machine. 
     Analog computer  104  may include at least one analog processor such as quantum processor  114 . Analog computer  104  can be provided in an isolated environment, for example, in an isolated environment that shields the internal elements of the quantum computer from heat, magnetic field, and other external noise (not shown). The isolated environment may include a refrigerator, for instance a dilution refrigerator, operable to cryogenically cool the analog processor, for example to temperature below approximately 1° Kelvin. 
     Bayesian Networks for Markovian Topologies 
     It may not be practicable to represent a Bayesian network   defined on some space x in the physical topology of a particular quantum processor. If the quantum processor is capable of representing and computing Markov networks, we can approximate the probability distribution   (x) corresponding to   by another distribution   (x) corresponding to a Markov network   also defined on x. The quantum processor may then draw samples from (or otherwise compute) the approximating Markov network, the results of which may be reconstituted into an approximate solution to the Bayesian network  . 
     The Bayesian network   can be factorized as the following joint probability distribution: 
               p   ⁡     (       x   1     ,     x   2     ,   …   ⁢           ,     x   N       )       =       ∏   i   N     ⁢     p   ⁡     (       x   i     ❘       p   a     ⁡     (     x   i     )         )               
where x=(x 1 , x 2 , . . . , x N ) are the N nodes of the Bayesian network and pa(x i ) is the set of all parental nodes of x i . Further, a Markov network   may be described by the following joint distribution:
 
               q   ⁡     (       x   1     ,     x   2     ,   …   ⁢           ,     x   N       )       =       ∏     C   ∈     Cli   ⁡     (   G   )           ⁢       ϕ   C     ⁡     (     x   C     )               
where Cli(G) is the set of cliques in an undirected graph G of the Markov network and ϕ C  is the potential function defined on clique C. The challenge is to migrate the probability distribution p of the Bayesian network   to a probability function q of a Markov network, at least approximately, computing q by the quantum processor, and translating the result of the computation back to Bayesian network  .
 
       FIG. 2  shows an example method  200  for computing problems represented by Bayesian networks via a quantum processor. The method is performed by a classical computer (e.g. one or more processors) which may be in communication with a quantum processor. 
     At  202  a classical processor obtains a Bayesian network representing a problem. It may be obtained from a user, from storage, generated from inputs or other data, and/or otherwise obtained. At  204  the classical processor transforms the Bayesian network to a Markov network. In some implementations, the classical processor transforms the Bayesian network to a Markov network via moralization (e.g. at  212 ), which involves marrying all of the parent nodes and then dropping all of the directionalities of the edges. For example, the processor may replace each conditional probability p(x i |pa(x i )) with a joint distribution p(x i ,pa(x i )) defined on the clique x i ∪pa(x i ). This conversion is not lossless, as it can remove the conditional independencies between nodes, so the results will be approximations. Extraneous edges will tend to introduce additional error, so it can be desirable for   to have a minimal number of edges, although this is not strictly required. 
     In some implementations, the Markov network has a structure corresponding to the topology of the quantum processor. For example, given a quantum processor with a Chimera topology and symmetric coupling, the Markov network   may comprise a Chimera-structured (restricted) Boltzmann machine. The probability function of   may be, for example: 
               q   ⁡     (   x   )       =       exp   ⁡     (       -     θ   T       ⁢     ϕ   ⁡     (   x   )         )         Z   ⁡     (   θ   )               
where θ is a parameter vector of qubit bias values (typically denoted h) and coupler bias values (typically denoted J), ϕ(x) is the feature vector defined over cliques, and Z(θ) is the partition function (sometimes called the normalization).
 
     In some implementations, the classical processor moralizes the Bayesian network   to a Chimera-structured Markov network  , thereby represents a Bayesian network with probability distribution p as a Markov network. For example, given the example Bayesian network  302  of  FIG. 3 ,   may correspond to Markov network  304  and have a joint probability distribution described by 
               q   ⁡     (   x   )       =       1     Z   ⁡     (   x   )         ⁢       exp   ⁡     (       -       ψ   1     ⁡     (       x   1     ,     x   2     ,     x   3       )         -       ψ   2     ⁡     (       x   2     ,     x   3     ,     x   4       )         )       .             
If the normalization is Z(x)=1 (which may, in at least some circumstances, be assumed for convenience), then the two feature functions ψ i  can be described by:
 
ψ 1 ( x   1   ,x   2   ,x   3 )=ln [ p ( x   1 ) p ( x   2   |x   1 ) p ( x   3   |x   1 )]
 
« 2 ( x   2   ,x   3   ,x   4 )=ln [ p ( x   4   |x   2   ,x   3 )].
 
     These two exemplary feature functions may be described as quadratic unconstrained binary optimization (QUBO) equations, such as the following: 
                 ψ   1     ⁡     (       x   1     ,     x   2     ,       x   3     ;     θ   1         )       =         ∑     i   ∈     {     1   ,   2   ,   3     }         ⁢       h   i     ⁢     x   i         +       ∑     ij   ∈     {     12   ,   13   ,   23     }         ⁢       J   ij     ⁢     x   i     ⁢     x   j         +   a                     ψ   2     ⁡     (       x   2     ,     x   3     ,       x   4     ;     θ   2         )       =         ∑     i   ∈     {     2   ,   3   ,   4     }         ⁢       h   i     ⁢     x   i         +       ∑     ij   ∈     {     23   ,   24   ,   34     }         ⁢       J   ij     ⁢     x   i     ⁢     x   j         +   b           
where θ 1 =[h 1 ,h 2 ,h 3 ,J 12 ,J 13 ,J 23 ] T , θ 2 =[h 2 ,h 3 ,h 4 ,J 23 ,J 24 ,J 34 ] T , and a and b are constants.
 
     In some implementations, the classical processor transforms the Bayesian network to a Markov network by learning the probability distribution of the Bayesian network with a Markov network (e.g. at  214 ). For example, the classical processor may learn the Bayesian network via a Boltzmann machine (a type of Markov network). Boltzmann machines include restricted Boltzmann machines, which possess a degree of correspondence to the Chimera structure mentioned above. 
     In such implementations, the classical processor generates the structure of a Boltzmann machine based on the Bayesian network. For example, the processor may generate the Boltzmann machine by defining visible units of the Boltzmann machine on all of the nodes of the Bayesian network, e.g. by defining the Markov probability function q as: 
               q   ⁡     (   x   )       =         ∑   h     ⁢     E   ⁡     (     x   ,   h     )         Z           
where Z is the partition function.
 
     The resulting Boltzmann machine is based on an undirected graph and does not necessarily require pre-training knowledge of the graphical structure of   (i.e. it does not require express deconstruction of the feature functions as described in the above example). The generalizability of this technique is potentially advantageous in suitable circumstances, but of course the resulting (restricted) Boltzmann machine will tend to be less compact and have more variables (namely hidden variables) than the original Bayesian network  , and potentially more than Markov networks trained as described above, and so it may be more computationally costly to train and infer with networks generated in this way. 
     Note that although acts  212  and  214  are depicted separately within act  204 , act  204  may comprise doing one or both of acts  212  and  214 . 
     At  206 , the classical processor determines the parameters of the Markov network generated at  204 . Where a system of equations is known (e.g. as in the above example), the parameters may be determined according to conventional linear algebraic techniques. However, note that the system may be overdetermined. This is the case with the foregoing example, which has 11 parameters and 16 equations between ψ 1  and ψ 2 . Accordingly, an exact solution may not exist. An approximating solution may instead be generated, for example by determining the least-squares solution to the system Aθ=−ln p(x) where A is the coefficients of the QUBOs. (This involves determining the pseudo-inverse of A, A +  and determining the approximate solution {tilde over (θ)}=A + [−ln p(x)]). 
     However, where the Markov network is based on the quantum processor&#39;s topological structure (by moralization and/or by learning), the quantum processor (and/or a classical proxy thereof) may be used. For example, if the quantum processor is Chimera-structured, then the Markov network may also be Chimera-structured (and/or a subgraph thereof). The Markov network may then be trained by optimizing an objective function, such as the Kullback-Liebler divergence between p(x) and q(x), i.e. KL[p(x)|q(x)]. The positive phase may be computed classically since the expected value for ϕ(x) under p(x) is tractable for a Bayesian network. The negative phase is intractable, but may be approximated by sampling from the Markov network via the quantum processor (or by suitable classical techniques such as Markov Chain Monte Carlo). 
     Sampling from the quantum processor may comprise instructing a quantum processor to represent the Markov network by physically biasing the quantum processor&#39;s qubits and couplers to correspond to the nodes and edges of the Markov network, evolving the represented system to generate one or more samples, and returning the resulting samples. The classical processor may then use the samples to optimize an objective function. 
     At  207 , the parametrized Markov network   is used to perform inference in the place of (or in addition to) the original Bayesian network  . Optionally, at  208 , a Bayesian network may be reconstituted from the output of the parametrized Markov network. This may be done by, for example, obtaining a graphical structure for the Bayesian network—either by using the original graphical structure or assembling a (potentially) new one by converting the Markov network to a junction tree by performing triangulation, finding the maximal cliques, and converting the junction tree to a Bayesian network by adding directed edges from parents of nodes to nodes based on the order of nodes and cliques. 
     Once a graphical structure is obtained, the conditional probabilities of the Markov network may be migrated to the Bayesian network by learning the parameters of the Bayesian network from the output of the Markov network. Training may proceed by, for example, maximum likelihood estimation and/or by Bayesian estimation (in both cases, based on the output data). 
     Concluding Generalities 
     The above described method(s), process(es), or technique(s) could be implemented by a series of processor readable instructions stored on one or more nontransitory processor-readable media. Some examples of the above described method(s), process(es), or technique(s) method are performed in part by a specialized device such as an adiabatic quantum computer or a quantum annealer or a system to program or otherwise control operation of an adiabatic quantum computer or a quantum annealer, for instance a computer that includes at least one digital processor. The above described method(s), process(es), or technique(s) may include various acts, though those of skill in the art will appreciate that in alternative examples certain acts may be omitted and/or additional acts may be added. Those of skill in the art will appreciate that the illustrated order of the acts is shown for exemplary purposes only and may change in alternative examples. Some of the exemplary acts or operations of the above described method(s), process(es), or technique(s) are performed iteratively. Some acts of the above described method(s), process(es), or technique(s) can be performed during each iteration, after a plurality of iterations, or at the end of all the iterations. 
     The above description of illustrated implementations, including what is described in the Abstract, is not intended to be exhaustive or to limit the implementations to the precise forms disclosed. Although specific implementations of and examples are described herein for illustrative purposes, various equivalent modifications can be made without departing from the spirit and scope of the disclosure, as will be recognized by those skilled in the relevant art. The teachings provided herein of the various implementations can be applied to other methods of quantum computation, not necessarily the exemplary methods for quantum computation generally described above. 
     The various implementations described above can be combined to provide further implementations. All of the commonly assigned US patent application publications, US patent applications, foreign patents, and foreign patent applications referred to in this specification and/or listed in the Application Data Sheet are incorporated herein by reference, in their entirety, including but not limited to: 
     U.S. Pat. No. 7,533,068 
     U.S. Pat. No. 8,008,942 
     U.S. Pat. No. 8,195,596 
     U.S. Pat. No. 8,190,548 
     U.S. Pat. No. 8,421,053 
     US Patent Publication 2017/0300817 
     These and other changes can be made to the implementations in light of the above-detailed description. In general, in the following claims, the terms used should not be construed to limit the claims to the specific implementations disclosed in the specification and the claims, but should be construed to include all possible implementations along with the full scope of equivalents to which such claims are entitled. Accordingly, the claims are not limited by the disclosure.