Quantum circuit representation of Bayesian networks

address1]Sima E. Borujeni
address1]Saideep Nannapanenimycorrespondingauthor
[mycorrespondingauthor]Corresponding author. Phone: +1 316-978-6240

address2]Nam H. Nguyen
[fn1]Present address: Boeing Research & Technology, Huntington Beach, CA 92647, USA
address2]Elizabeth C. Behrman
address3]James E. Steck

[address1]Department of Industrial, Systems, and Manufacturing Engineering, Wichita State University

1845 Fairmount St, Box 35, Wichita, KS, 67260 USA

<EMAIL_ADDRESS><EMAIL_ADDRESS>
[address2]Department of Mathematics, Statistics, and Physics, Wichita State University

1845 Fairmount St, Box 33, Wichita, KS, 67260 USA

<EMAIL_ADDRESS><EMAIL_ADDRESS>
[address3]Department of Aerospace Engineering, Wichita State University

1845 Fairmount St, Box 44, Wichita, KS, 67260 USA

Probabilistic graphical models such as Bayesian networks are widely used to model stochastic systems to perform various types of analysis such as probabilistic prediction, risk analysis, and system health monitoring, which can become computationally expensive in large-scale systems. While demonstrations of true quantum supremacy remain rare, quantum computing applications managing to exploit the advantages of amplitude amplification have shown significant computational benefits when compared against their classical counterparts. We develop a systematic method for designing a quantum circuit to represent a generic discrete Bayesian network with nodes that may have two or more states, where nodes with more than two states are mapped to multiple qubits. The  marginal probabilities associated with root nodes (nodes without any parent nodes) are represented using rotation gates, and the conditional probability tables associated with non-root nodes are represented using controlled rotation gates. The controlled rotation gates with more than one control qubit are represented using ancilla qubits. The proposed approach is demonstrated for three examples: a 4-node oil company stock prediction, a 10-node network for liquidity risk assessment, and a 9-node naive Bayes classifier for bankruptcy prediction. The circuits were designed and simulated using Qiskit, a quantum computing platform that enable simulations and also has the capability to run on real quantum hardware. The results were validated against those obtained from classical Bayesian network implementations.

Bayesian network Quantum Circuit Qiskit QubitFinance

§ INTRODUCTION

Bayesian Networks, also known as Bayesian belief networks, are probabilistic graphical models used to represent knowledge about an uncertain domain. A Bayesian network is represented as a directed acyclic graph with nodes and edges, where nodes represent the random variables and edges represent the probabilistic dependence between nodes [Murphy & Russell, 2002].

Bayesian networks are used to perform two types of analysis: forward analysis, which provides a probabilistic prediction of the lower-level nodes in the Bayesian networks using probability distributions of the higher-level nodes, and inverse analysis, which infers the values of higher-level nodes using data on the lower-level nodes. The inverse analysis is commonly referred to as Bayesian inference since the inference analysis is carried out using the Bayes theorem. The forward analysis is typically performed through Monte Carlo analysis and has been used to perform uncertainty propagation [Nannapaneni et al., 2016], performance evaluation [Zhu & Deshmukh, 2003], reliability and risk analysis [Garvey et al., 2015], and prognostics [Ferreiro et al., 2012], whereas the inverse analysis has been used for system identification [Lee & Song, 2016], health monitoring [Kothamasu et al., 2006], and system diagnostics [Li et al., 2017]. Bayesian networks have been used to carry out a variety of analyses in several domains of science and engineering such as mechanical [Xu, 2012], aerospace [Li et al., 2017, Nannapaneni et al., 2018], and manufacturing systems [Büyüközkan et al., 2015, Nannapaneni et al., 2018], industrial systems [Cai et al., 2016], healthcare [Kahn Jr et al., 1997, Kalet et al., 2015], infrastructure systems [Hosseini & Barker, 2016, Nannapaneni et al., 2017], biomedical systems [Miyauchi & Nishimura, 2018], and transportation [Sun et al., 2006, Pettet et al., 2017].

Some of the issues with the current implementations of Bayesian networks is the high computational expense in the presence of large number of nodes (random variables) for both forward and inverse analyses.  One possible way to obviate this difficulty might be to use the principles of quantum computing (sometimes referred to as quantum-assisted computing). This is because quantum computers make use of “superposition" which is
the ability of quantum systems to be simultaneously in multiple different states.

Several algorithms have been developed using the principles of quantum mechanics that have demonstrated superior computational performance over the corresponding classical algorithms, and the most notable of these are Shor's algorithm [Shor, 1994] and Grover's algorithm [Grover, 1996]. Shor's algorithm is used for the factorization of integers; this algorithm has exponential speedup when compared to the best known classical algorithms. Grover's algorithm is used for search in an unstructured search space (such as an unstructured database), and has quadratic speedup.

Due to its computational benefits, the Grover's algorithm has been used as a sub-routine in the development of many quantum algorithms for classification such as quantum support vector machines [Rebentrost et al., 2014], for clustering such as quantum k-means clustering [Aïmeur et al., 2007], and for combinatorial optimization [Baritompa et al., 2005]. With regard to Bayesian networks, Ozols et al [Ozols et al., 2013] used the principles of amplitude amplification [Brassard et al., 2002]  to develop an algorithm for Bayesian inference (inverse analysis) known as quantum rejection sampling, which is a quantum version of the rejection sampling algorithm [Gilks & Wild, 1992] used for inference in classical Bayesian networks. Woerner and Egger [Woerner & Egger, 2019] used the principles of amplitude amplification and estimation [Brassard et al., 2002] to perform risk analysis (forward analysis), and demonstrated it with two toy problems from the financial industry. In this paper, we consider the representation of Bayesian networks in a quantum computing paradigm to facilitate the use of those quantum algorithms for forward and inverse analyses.

There are primarily two types of architectures that have widely been used to realize quantum computing: quantum gate models [Dallaire-Demers & Wilhelm, 2016] and quantum annealing [Bunyk et al., 2014]. The quantum gate architecture uses a series of quantum gates that act on individual qubits to achieve the desired computation.

More details regarding qubits and gates are available in Sections <ref> and <ref>. A quantum circuit is a graphical representation of the sequence of gates implemented on various qubits to do the desired computation. Quantum annealing architecture uses the principles of quantum annealing [Boixo et al., 2013], which is a quantum equivalent to classical simulated annealing algorithm, to make the desired computation. According to Ajagekar et al [Ajagekar et al., 2020], quantum annealing architecture is better suited for optimization problems whereas quantum gate architecture facilitates universal quantum computation. As the goal of this paper is the representation of Bayesian networks, we use the quantum gate architecture as opposed to the quantum annealing architecture.

Low et al [Low et al., 2014] discussed the principles of quantum circuit design to represent a Bayesian network with discrete nodes that have two states, and also discussed the circuit design for implementing quantum rejection sampling for inference. In this paper, we consider the representation of generic discrete Bayesian networks with nodes that may have two or more states, and also discuss the decomposition of complex gates using elementary gates (discussed in Section <ref>) such that they can be implemented on available quantum computing platforms.

Paper Contributions: The overall contributions made through this paper are:  (1) Decomposition of a multi-qubit gate into elementary gates to represent a discrete variable with more than two states; (2) A systematic procedure to design a quantum circuit to represent a generic discrete Bayesian network with nodes that may have two or more states; and (3) Illustration of the proposed quantum circuit representation to three Bayesian networks used for oil price stock prediction, liquidity risk assessment, and bankruptcy prediction, and validating the results against classical Bayesian network implementations.

Paper Organization: Section <ref> provides a brief background to qubits, quantum gates, and Bayesian networks. Section <ref> details the proposed methods for designing a quantum circuit to represent a Bayesian network. Section <ref> details the application of the proposed methods to three Bayesian networks from the financial industry followed by concluding remarks in Section <ref>.

§ BACKGROUND

In this section, we provide a brief background to qubits, different quantum gates that are used to perform qubit transformations, and Bayesian Networks.

§.§ Qubit

A qubit (or a quantum bit) is an elementary unit of information in quantum computing, similar to a classical bit (or simply a bit) in classical computing. A bit is always in one of the either two basis states - 0 and 1, whereas a qubit can be in both the basis states simultaneously. This property of a qubit is known as quantum superposition. In quantum computing, the Dirac notation is used to represent the two basis states as $\Ket{0}$ and $\Ket{1}$. In general, any two orthonormal states can be used as the basis states but the commonly used basis states or computational basis are $\Ket{0}$ and $\Ket{1}$. Eq. (<ref>) provides their vector representations as

\begin{equation}
\label{eqn:basis}
\Ket{0} = \begin{bmatrix}
{1} \\
{0} \\
\end{bmatrix} \hspace{2cm}
\Ket{1}= \begin{bmatrix}

{0} \\
{1} \\
\end{bmatrix}
\end{equation}

A general pure state of a qubit is a superposition, which is linear combination of the two basis states written as  $ \Ket{\Psi} = c_1 \Ket{0} + c_2 \Ket{1}$ or

\begin{equation}
\begin{bmatrix}
\end{bmatrix} = c_1\begin{bmatrix}
{1} \\
{0} \\
\end{bmatrix}
{0} \\
{1} \\
\end{bmatrix}
\end{equation}

where $c_1$ and $c_2$ are  complex numbers, which represent the probability amplitudes corresponding to $\Ket{0}$ and $\Ket{1}$ respectively. When a measurement is made, the qubit collapses to one of the two basis states. The probabilities of observing the qubit in $\Ket{0}$ and $\Ket{1}$ states are computed as the inner product of their probability amplitudes and their complex conjugates, represented as $c_1^{\dagger} c_1 = |c_1|^2$ and $c_2^{\dagger} c_2 = |c_2|^2$ respectively, where $c_1^{\dagger}$ and $c_2^{\dagger}$ are the complex conjugates of $c_1$ and $c_2$ respectively. Since a qubit can be either in $\Ket{0}$ or in $\Ket{1}$, the sum of their probabilities is equal to unity ($|c_1|^2  + |c_2|^2=1$).

When multiple qubits are used in computing, their joint state can be obtained through a tensor product of individual qubits. If $\Ket{\Psi_1}=a_1\Ket{0}+a_2\Ket{1}$ and $\ket{\Psi_2} = b_1\Ket{0}+b_2\Ket{1}$ represent two qubits with real-valued probability amplitudes, then their joint state is represented as $\Ket{\Psi_1} \otimes \Ket{\Psi_2} = a_1b_1\Ket{00}+a_1b_2\Ket{01}+a_2b_1\Ket{10}+a_2b_2\Ket{11}$. But the joint state need not always be a product state (tensor product of individual states). There are states of the joint system that can not be written as a product of individual states; these are called entangled states. Entanglement is quantum correlation stronger than any possible classical correlation.

An example of an entangled state of two qubits is the Bell state, defined as $\dfrac{1}{\sqrt{2}} \Ket{00} + \dfrac{1}{\sqrt{2}} \Ket{11}$ [Nielsen & Chuang, 2002]. Clearly, it can not be written as a tensor product of two qubits, $\Ket{\Psi_1}=a_1\Ket{0}+a_2\Ket{1}$ and $\ket{\Psi_2} = b_1\Ket{0}+b_2\Ket{1}$, because then $a_1b_1 = a_2b_2 = \dfrac{1}{\sqrt{2}}$ but also $a_1b_2 = a_2b_1 = 0$. Thus, neither qubit has an individual state, but the two are perfectly correlated. If one of the two qubits is measured to be in $\Ket{0}$ state, then the other qubit is also in $\Ket{0}$ due to the presence of entanglement between them.

[line cap=round, line join=round, >=Triangle]
(-2.5,-2.49) rectangle (2.70,2.70);
[shift=(0,0), fill, fill, fill opacity=0.1] (0,0) – (56.7:0.4) arc (56.7:90.:0.4) – cycle;
[shift=(0,0), fill, fill, fill opacity=0.1] (0,0) – (-135.7:0.4) arc (-135.7:-33.2:0.4) – cycle;
(0,0) circle (2cm);
[rotate around=0.:(0.,0.),dash pattern=on 3pt off 3pt] (0,0) ellipse (2cm and 0.9cm);
(0,0)– (0.70,1.07);
[->] (0,0) – (0,2);
[->] (0,0) – (-0.81,-0.79);
[->] (0,0) – (2,0);
[dotted] (0.7,1)– (0.7,-0.46);
(0,0)– (0.7,-0.46);
(-0.08,-0.3) node[anchor=north west] $\phi$;
(0.01,0.9) node[anchor=north west] $\theta$;
(-1.01,-0.72) node[anchor=north west] $\mathbf {X}$;
(2.07,0.3) node[anchor=north west] $\mathbf {Y}$;
(-0.5,2.6) node[anchor=north west] $\mathbf {Z=|0\rangle}$;
(-0.4,-2) node[anchor=north west] $-\mathbf {Z=|1\rangle}$;
(0.4,1.65) node[anchor=north west] $|\Psi\rangle$;
[fill] (0,0) circle (1.5pt);
[fill] (0.7,1.1) circle (0.5pt);

Bloch sphere representation of a qubit

A Bloch sphere (shown in Figure <ref>) is often used for geometrical representation of a qubit. In a Bloch sphere, the positive Z-axis corresponds to the $\Ket{0}$ state while the negative Z-axis corresponds to $\Ket{1}$ state. A pure state of a qubit is represented by a point on the Bloch sphere and can be represented as $\cos(\frac{\theta}{2}) \Ket{0} + e^{i\phi}\sin(\frac{\theta}{2}) \Ket{1}$ for given values of $(\theta,\phi)$.

§.§ Quantum gates

Quantum gates are mathematical operations performed on the qubits to change their probability amplitudes to gain the desired computations. The quantum gates are similar to classical gates (such as the AND gate) acting on classical bits. Geometrically, one-qubit gates represent unitary rotations about various axes in the Bloch sphere.

There are two elementary gates in quantum computing - $U_3$ and CNOT, which act on a single qubit and two qubits respectively. Any other multi-qubit gates can be decomposed into these elementary gates. We discuss in detail the one-qubit and two-qubit elementary gates. A more comprehensive review of gates is available in Nielsen and Chuang's textbook [Nielsen & Chuang, 2002].

§.§.§ One-qubit gates
We review the generic $U_3$ gate [McKay et al., 2018], and some of its special cases - $X$ (sometimes referred to as Pauli-$X$), $R_Y$ and $R_Z$ gates.

$U_3$ gate has three parameters $\theta$, $\phi$ and $\lambda$, and it can be used to construct any arbitrary single qubit gate. The matrix representation of this gate is given as

\begin{equation}
\label{eqn:U_3matrix}
U_3(\theta, \phi, \lambda) = \begin{bmatrix}
\cos\Big(\dfrac{\theta}{2}\Big) &  -e^{i\lambda} \sin\Big(\dfrac{\theta}{2}\Big) \\[2mm]
e^{i\phi} \sin\Big(\dfrac{\theta}{2}\Big) &  e^{i(\phi + \lambda)} \cos\Big(\dfrac{\theta}{2}\Big) \\
\end{bmatrix}
\end{equation}

where $\theta$ represents the angle of rotation about the Y-axis, and $\phi$ and $\lambda$ represent the angles of rotation around the Z-axis. The generic $U_3$ gate is often represented as the $U$ gate.

$R_Y$ gate: The $R_Y$ gate is a single-qubit gate, which corresponds to a rotation of angle $\theta$ (radians) about the y-axis on the Bloch sphere. $R_Y$ gate can be represented as a special case of $U_3$ gate as

\begin{equation}
R_Y(\theta)=U_3(\theta, 0, 0)=
\begin{bmatrix}
\cos\Big(\dfrac{\theta}{2}\Big) &  -\sin\Big(\dfrac{\theta}{2}\Big) \\[2mm]
\sin\Big(\dfrac{\theta}{2}\Big) & \cos\Big(\dfrac{\theta}{2}\Big)\\
\end{bmatrix}
\end{equation}

$R_Z$ gate or Phase-shift gate:
$R_Z(\lambda)$ is another single qubit gate, which corresponds to rotation about the Z-axis by an angle $\lambda$ on the Bloch sphere. $R_Z$ gate can be represented as a special case of $U_3$ as

\begin{equation}
\begin{bmatrix}
1 &  \hspace{2mm} 0 \\
0 & \hspace{2mm} e^{i\lambda}\\
\end{bmatrix}
\end{equation}

Using the matrix representations of $R_Y$ and $R_Z$ gates, the $U_3$ gate given in Eq. (<ref>) can be decomposed into two phase-shift rotations and one rotation about the Y-axis as

\begin{equation}
\label{eq:U_3_3matricies}
\begin{aligned}
U_3(\theta, \phi, \lambda) &= \begin{bmatrix}
1 &  0 \\[2mm]
0 &  e^{i\phi} \\
\end{bmatrix}
\begin{bmatrix}
\cos\Big(\dfrac{\theta}{2}\Big) &  -\sin\Big(\dfrac{\theta}{2}\Big) \\[2mm]
\sin\Big(\dfrac{\theta}{2}\Big) &  \cos\Big(\dfrac{\theta}{2}\Big) \\
\end{bmatrix}
\begin{bmatrix}
1 &  0 \\[2mm]
0 &  e^{i\lambda} \\
\end{bmatrix} \\
& = R_Z(\phi)R_Y(\theta)R_Z(\lambda)
\end{aligned}
\end{equation}

For more detail about the rotation gates and decomposition of an arbitrary single qubit gate, refer to [Nielsen & Chuang, 2002] and [Cross et al., 2017].

X gate: The $X$ gate is the quantum-equivalent to the classical NOT gate or sometimes referred to as flip gate, as it flips $\Ket{0}$ to $\Ket{1}$ and $\Ket{1}$ to $\Ket{0}$. The matrix notation of the $X$ gate is equal to

\begin{equation}
X = U_3\Big(\pi, -\frac{\pi}{2}, \frac{\pi}{2}\Big) = \begin{bmatrix}
0 &  \hspace{2mm} 1 \\
1 & \hspace{2mm} 0\\
\end{bmatrix}
\end{equation}

§.§.§ Two-qubit gates
An elementary two-qubit gate is the controlled-NOT (CNOT or $CX$) gate. The two qubits on which the CNOT gate is implemented are referred to as the control qubit and target qubit. When the control qubit is $\Ket{0}$, the target qubit remains unchanged whereas when the control qubit is $\Ket{1}$, the $X$ gate is implemented on the target qubit. The CNOT gate does not have any effect on the control qubit. In the usual computational basis ($\Ket{00}, \Ket{01}, \Ket{10}, and \Ket{11}$ states),the matrix representation of a CNOT gate is given as

\begin{equation}
\centering
\begin{bmatrix}
1 & 0 & 0 & 0 \\
{0} & {1} & {0} & {0} \\
{0} & {0} & {0} & {1} \\
{0} & {0} & {1} & {0} \\
\end{bmatrix}
\end{equation}

For example, consider two qubits given as $\Ket{\Psi_1}=a_1\Ket{0}+a_2\Ket{1}$ and $\ket{\Psi_2} = b_1\Ket{0}+b_2\Ket{1}$ on which a CNOT gate is implemented with $\Ket{\Psi_1}$ as the control qubit. The combined quantum state before the application of CNOT gate is given by their tensor product, $\Ket{\Psi_1} \otimes \Ket{\Psi_2} = a_1b_1 \Ket{00} + a_1b_2 \Ket{01} + a_2b_1 \Ket{10} + a_2b_2 \Ket{11}$. The quantum state after the application of the CNOT gate is equal to $a_1b_1 \Ket{00} + a_1b_2 \Ket{01} + a_2b_1 \Ket{11} + a_2b_2 \Ket{10}$. The $\Ket{00}$ and $\Ket{01}$ remain unchanged  since the control qubit is $\Ket{0}$ whereas $\Ket{10}$ and $\Ket{11}$ become $\Ket{11}$ and $\Ket{10}$ respectively as the $X$ gate is applied when the control qubit is $\Ket{1}$. Similar to the CNOT gate, we have the $CU$ gate, which implements the $U$ (or the $U_3$) gate when the control qubit is $\Ket{1}$. Given the matrix of the $U$ gate in Eq. (<ref>), the matrix representation of $CU$ can be written as

\begin{equation}
\begin{bmatrix}
{1} & \hspace{4mm}{0} & {0} & {0} \\
{0} & \hspace{4mm}{1} & {0} & {0} \\
{0} & \hspace{4mm}{0} & \cos\Big(\dfrac{\theta}{2}\Big)& -e^{i\lambda} \sin\Big(\dfrac{\theta}{2}\Big) \\[2mm]
{0} & \hspace{4mm} {0} & e^{i\phi} \sin\Big(\dfrac{\theta}{2}\Big)& e^{i(\phi + \lambda)} \cos\Big(\dfrac{\theta}{2}\Big) \\
\end{bmatrix}
\end{equation}

A variant of the $CU$ gate is the $CR_Y(\theta)$ gate, which implements the rotation gate $R_Y(\theta)$ on the target qubit when the control qubit is equal to $\Ket{1}$. The matrix representation of the $CR_Y(\theta)$ can be written as

\begin{equation}
\begin{bmatrix}
{1} & \hspace{4mm}{0} & {0} & {0} \\
{0} & \hspace{4mm}{1} & {0} & {0} \\
{0} & \hspace{4mm}{0} & \cos\Big(\dfrac{\theta}{2}\Big)& - \sin\Big(\dfrac{\theta}{2}\Big) \\[2mm]
{0} & \hspace{4mm} {0} & \sin\Big(\dfrac{\theta}{2}\Big)& \cos\Big(\dfrac{\theta}{2}\Big) \\
\end{bmatrix}
\end{equation}

§.§.§ Three-qubit gates
We will discuss two three-qubit gates that are later used in the proposed methodology: CCNOT (or $CCX$ or Toffoli) and $CCR_Y(\theta)$. Out of the three qubits on which the CCNOT and $CCR_Y(\theta)$ are implemented, two qubits act as control qubits and the other is the target qubit. In the case of CCNOT gate, when both control qubits are $\Ket{1}$, we implement the $X$ gate on the target qubit. In the case of the $CCR_Y(\theta)$ gate, we implement the $R_Y(\theta)$ gate when the two control qubits are in the $\Ket{1}$ state. The three-qubits are not elementary gates but can be decomposed into a combination of single-qubit and CNOT gates. For example, the CCNOT can be represented using a combination of nine single qubit gates and six CNOT gates [Shende & Markov, 2008]. Similar to $CCX$ and $CCR_Y(\theta)$, we can define an $C^nX$ and $C^nR_Y(\theta)$ gates with $n$ control qubits and one target qubits. Figure <ref> provides the representation of various gates discussed above in a quantum circuit. A quantum circuit represents a graphical representation of a sequence of gates that are implemented on various qubits to obtain a desired computation. Measurement gate in Figure <ref> performs the measurement operation on a qubit.

$X$      $R_Y$     $R_Z$     $U_3$     $CU$

@C=1em @R=.7em    X              @C=1em @R=.7em      R_Y          @C=1em @R=.7em     R_Z          @C=1em @R=.7em     U_3         @C=1em @R=.7em     1

CNOT      CCNOT     $CR_Y$     $CCR_Y$      Measurement

@C=1em @R=.7em     1

@C=1em @R=.7em     1

@C=1em @R=.7em     1
@C=1em @R=.7em     1

@C=1em @R=.7em

Representation of commonly used one, two, and three qubit gates

@C=1em @R=0.9em

U         =  @C=1em @R=0.9em
1         1

A         B         C

Decomposition of a CU gate into a combination of single qubit and CNOT gates

According to [Nielsen & Chuang, 2002], the $CU$ can be decomposed into a combination of single-qubit and CNOT gates as given in Figure <ref>; this decomposition can mathematically be represented as

\begin{equation}
\label{eqn:cu}
CU = (I\otimes A)CX(I\otimes B)CX(I\otimes C)
\end{equation}

where $A = R_Z(\phi)R_Y(\theta/2)$, $B = R_Y(-\theta/2)R_Z(-(\lambda+\phi)/2)$, $C = R_Z((\lambda-\phi)/2)$, and $I$ represents the identity matrix. $I\otimes A$ represents the tensor product of two matrices, $I$ and $A$, where $I$ and $A$ are single-qubit gates implemented on the first and second qubits respectively. $I\otimes A$ is the simplified representation of the two gates acting on the two qubits.

§.§ Bayesian Networks

As mentioned in Section <ref>, Bayesian networks (BNs) are probabilistic graphical models that represent a probabilistic framework to model stochastic/uncertain systems. In a probabilistic framework, a stochastic system can be represented as a joint probability distribution defined over the set of random variables. A BN consists of nodes and edges, where nodes represent the random variables, and edges represent the dependence between nodes, which is quantified using conditional probability tables (CPT, for discrete variables) and conditional probability distributions (CPD, for continuous variables). In this paper, we consider the design of quantum circuits to represent discrete Bayesian networks.

Let us consider a Bayesian network with $s$ nodes, where $\mathbb{V}=\{V_1,V_2,...,V_s\}$ represents the set of all nodes or random variables. An edge from node $V_i$ to node $V_j$ represents the dependence between the variables $V_i$ and $V_j$, and that the values of $V_j$ are dependent on the values of $V_i$. Here, $V_i$ is called the parent node and node $V_j$ is referred to as the child node. The nodes without any parent nodes are typically referred to as root nodes. Using the graphical representation of a Bayesian network, the joint probability over the nodes (random variables) can be decomposed into a product of marginal and conditional probabilities as

\begin{equation}
P(V_1,V_2,...,V_s)= \prod_{i=1}^{s} P(V_i| \Pi_{V_i})
\end{equation}

where $\Pi_{V_i}$ denotes the set of parents nodes associated with $V_i$. For root nodes, the $P(V_i| \Pi_{V_i})$ becomes equal to the marginal distribution, $P(V_i)$.

Consider a simple Bayesian network with 3 nodes as shown in Figure <ref> where A, B and C are discrete random variables with two states True (or “1") and False (or “0"). In this BN, $A$ and $B$ are root nodes whereas $C$ is a child node with $A$ and $B$ as parent nodes. We have the marginal distributions for root nodes (shown in Figure <ref> and a CPT for the child node, which represents a probability distribution of the child node conditioned on the values taken by the parent nodes. Given a CPT, we can calculate its marginal distribution by integrating over the distributions of the parent nodes, i.e., $P(C) = \sum_{A, B} P(C|A, B)\times P(A, B)$. Due to the independence between nodes A and B (from Figure <ref>), the joint probabilities of A and B can be written as the product of individual probabilities, i.e., $P(A, B) = P(A)\times P(B)$, and therefore, $P(C) = P(C|A, B)\times P(A)\times P(B)$.

We use the marginal probabilities of various nodes in a Bayesian network as a measure to check the accuracy of the proposed quantum circuit representation approach in Section <ref>. After we design the quantum circuit, we estimate the marginal probabilities by simulating the quantum circuits, and compare them against the values from classical Bayesian network implementations. After providing a brief background to quantum computing and Bayesian networks, we will now discuss the representation of a Bayesian network through a quantum circuit.

An example of a 3-node Bayesian network

§ QUANTUM CIRCUIT OF A BAYESIAN NETWORK

We use the following principles for the design of a quantum circuit to represent a Bayesian network.

* Map each node in a Bayesian network to one or more qubits (depending on the number of discrete states of the node)

* Map the marginal/conditional probabilities of each node to the probability amplitudes (or probabilities) associated with various states of the qubit(s).

* Realize the required probability amplitudes of quantum states using (controlled) rotation gates.

@C=0.5em @R=0.9em

q_0:0     R_Y(θ_A)[0em]0      X     1    X [0em]0      X    1    X [0em]0          1    [0em]0           1

q_1:0    R_Y(θ_B)[0em]0      X     1    X [0em]0           1    [0em]0      X     1    X [0em]0           1

q_2:0    [0em]0          R_Y(θ_C,00)    [0em]0           R_Y(θ_C,01)    [0em]0          R_Y(θ_C,10)    [0em]0           R_Y(θ_C,11)

Conceptual quantum circuit for the 3-node Bayesian network

Let us discuss how these ideas can be used to design a quantum circuit for the 3-node Bayesian network in Figure <ref>. All the nodes in Figure <ref> have two states (0 and 1), and since a qubit can represent two states ($\Ket{0}$ and $\Ket{1}$), we can map each node to a different qubit. Also, let us map state 0 of each node to $\Ket{0}$ and state 1 to $\Ket{1}$. Let the three nodes A, B, and C be mapped to three qubits $q_0, q_1,$ and $q_2$ respectively.  Let the initial state of the three qubits be $\Ket{0}$. In the cases of $q_0$ and $q_1$, we will need to apply rotation gates ($R_Y$) with angles ($\theta_A$ and $\theta_B$) that result in superposed quantum states whose probabilities correspond the probabilities of nodes A and B respectively. The calculation of those angles are later discussed in Section <ref>. In the case of qubit $q_2$ (that corresponds to C), we will have a different rotation angle conditioned on the states of $q_0$ and $q_1$ since we have a different set of probabilities for node C conditioned on the values of parent nodes (A, B). Since there are four combinations of parent node values, we will have four rotation angles, one for each parent node combination. These conditional rotations are implemented using controlled rotation gates, whose angles depend on the conditional probabilities of C; these rotations are represented as $\theta_{C,ij}$, where $i,j=0,1$ and represent the states of $q_0$ and $q_1$ respectively.

Figure <ref> provides a conceptual quantum circuit for the 3-node Bayesian network. First, we implement the single qubit rotations to obtain the probabilities associated with A and B. Depending on the values of A and B, we implement controlled rotations to realize the conditional probabilities associated with C. In a controlled rotation, since the rotations are applied only when the control qubit is $\Ket{1}$, we use the $X$ gate to flip the $\Ket{0}$ to $\Ket{1}$ state to obtain the conditional probabilities when the parent node value(s) are 0. As there are two parent nodes, we implement a $CCR_Y$ gate to realize the conditional probabilities of C for every combination of the parent nodes. If there are $n$ parent nodes, then we would implement a $C^nR_Y$ gate. The overall quantum circuit can be obtained by composing all the single-qubit and controlled rotations in a sequential manner (as shown in Figure <ref>). In this paper, we refer to this approach as the C-QBN approach, which stands for Compositional approach for Quantum Bayesian networks.

We discuss below the computation of rotation angles to realize nodal probabilities in Section <ref>, representation of two-state child nodes with one or more parent nodes in Section <ref>, and representation of nodes with more than two states in Section <ref>.

§.§ Rotation angle computation

As mentioned above, we can represent a two-state root node using a single qubit. By applying an $R_Y$ gate with an appropriate angle, the probabilities of the root node can be mapped to the probabilities (and thus probability amplitudes) of the basis states, $\Ket{0}$ and $\Ket{1}$. Let $\theta_{V_i}$ represent the rotation angle associated with a two-state root node, $V_i$. Given the initial state of a qubit as $\Ket{0}$, the application of $R_Y(\theta)$ will transform $\Ket{0}$ to $\cos{\bigg(\dfrac{\theta}{2}\bigg)}\Ket{0} + \sin{\bigg(\dfrac{\theta}{2}\bigg)}\Ket{1}$. Therefore, the probabilities associated with the $\Ket{0}$ and $\Ket{1}$ states are equal to $\cos^2{\bigg(\dfrac{\theta}{2}\bigg)}$ and $\sin^2{\bigg(\dfrac{\theta}{2}\bigg)}$ respectively. If $P(V_i=0)$ and $P(V_i=0)$ represent the probabilities of states 0 and 1 of $V_i$, then the rotation angle can be computed as

\begin{equation}
\label{eqn:theta}
\theta_{V_i} = 2\times\tan^{-1}\sqrt{\dfrac{P(\Ket{1})}{P(\Ket{0})}} = 2\times\tan^{-1}\sqrt{\dfrac{P(V_i=1)}{P(V_i=0)}}
\end{equation}

In Eq. (<ref>), $P(\Ket{0})$ and $P(\Ket{1})$ represent the probabilities of a qubit to be in $\Ket{0}$ and $\Ket{1}$ respectively. Since we map the nodal probabilities to the probabilities of quantum states, $P(\Ket{0})$ and $P(\Ket{1})$ are replaced with $P(V_i=0)$ and $P(V_i=1)$ respectively. Therefore, two-state root nodes can be represented using an $R_Y$ gate with a rotation angle of $2\times\tan^{-1}\sqrt{\dfrac{P(V_i=1)}{P(V_i=0)}}$. In Figure <ref>, the rotation angle to find the probabilities of A and B can be calculated as $\theta_A = 2\times\tan^{-1}\sqrt{\dfrac{0.8}{0.2}} = 2.214$ and $\theta_B = 2\times\tan^{-1}\sqrt{\dfrac{0.7}{0.3}} = 1.982$.

Eq. (<ref>) can also be used to compute the rotation angles associated with conditional probabilities of two-state child nodes. Let $V_i$ and $\Pi_{V_i}$ represent a child node and set of its parent nodes respectively. For each combination of parent node values, $\Pi_{V_i} = \Pi^*_{V_i}$, we have probabilities for $V_i=0$ and $V_i=1$ denoted as $P(V_i=0|\Pi_{V_i} = \Pi^*_{V_i})$ and $P(V_i=1|\Pi_{V_i} = \Pi^*_{V_i})$ respectively. The rotation angle associated with $V_i$ when $\Pi_{V_i} = \Pi^*_{V_i}$, which is denoted by $\theta_{V_i, \Pi^*_{V_i}}$ can be calculated as

\begin{equation}
\label{eqn:theta2}
\theta_{V_i, \Pi^*_{V_i}} = 2\times\tan^{-1}\sqrt{\dfrac{P(V_i=1|\Pi_{V_i} = \Pi^*_{V_i})}{P(V_i=0|\Pi_{V_i} = \Pi^*_{V_i})}}
\end{equation}

The rotation angles associated with node C (qubit $q_2$ in Figure <ref>) can be calculated using Eq. (<ref>) as $\theta_{C,00} = 2\times\tan^{-1}\sqrt{\dfrac{0.85}{0.15}} = 2.346$, $\theta_{C,01} = 2\times\tan^{-1}\sqrt{\dfrac{0.7}{0.3}} = 1.982 $, $\theta_{C,10} = 2\times\tan^{-1}\sqrt{\dfrac{0.6}{0.4}} = 1.772 $, and $\theta_{C,11} = 2\times\tan^{-1}\sqrt{\dfrac{0.9}{0.1}} = 2.498$. The conditional probabilities associated with child nodes are realized through controlled rotations. As controlled rotation gates are not elementary gates, they need to be decomposed into single-qubit and two-qubit elementary gates; the decomposition is discussed below in Section <ref>.

§.§ Representing two-state child nodes with two-state parent nodes

First, we consider the representation of child nodes with one parent node, and then we consider the case with multiple parent nodes. A two-state child node with one parent node can be represented using two $CR_Y$ gates (assuming the parent node has two states) with rotation angles computed using Eq. (<ref>) conditioned on the parent node value. We consider parent nodes with more than two states in Section <ref>. The $CR_Y$ gate is a special case of a $CU$ gate discussed in Section <ref>, where $U=R_Y$. In Section <ref>, we discussed the decomposition of a $CU$ gate in terms of elementary single-qubit and CNOT gates shown in Figure <ref> and given in Eq. (<ref>). Since $R_Y(\theta) = U_3\Big(\dfrac{\theta}{2},0,0\Big)$, the single qubit gates A, B, and C in  Figure <ref> can be calculated as $A = R_Z(0)R_Y\Big(\dfrac{\theta}{2}\Big) = R_Y\Big(\dfrac{\theta}{2}\Big), B = R_Y\Big(-\dfrac{\theta}{2}\Big)R_Z\Big(-\dfrac{(0+0)}{2}\Big) =  R_Y\Big(-\dfrac{\theta}{2}\Big),$ and $C = R_Z\Big(\dfrac{(0-0)}{2}\Big) = I$. Figure <ref> illustrates the decomposition of the $CR_Y$ gate into single-qubit and CNOT gates. After considering child nodes with one parent node, we now consider child nodes with more than one parent nodes.

@C=1em @R=0.9em

R_Y (θ)         =  @C=1em @R=0.9em
1         1

R_Y(θ/2)         R_Y(-θ/2)

Decomposition of a $CR_Y$ gate into single-qubit and CNOT gates

Let $n$ represent the number of parent nodes for a child node, $V_i$. The conditional probabilities of $V_i$ can be stated using $C^nR_Y$ gate where the $n$ control qubits are the $n$ qubits corresponding to the $n$ parent nodes and the target qubit represents the child node.  For the child node C in Figure <ref>, n=2, and therefore, we used a $CCR_Y$ or $C^2R_Y$ gate to show the conditional probabilities of C in Figure <ref>. $C^nR_Y$ is not an elementary gate and will need to be decomposed into elementary gates. One of the techniques to build the $C^nR_Y$ is the use of additional “dummy" qubits known as ancilla qubits [Nielsen & Chuang, 2002]. Following [Nielsen & Chuang, 2002], implementation $C^nR_Y$ requires $n-1$ ancilla qubits. Using ancilla qubits, the $C^nR_Y$ gate is decomposed into a combination of $2(n-1)$ CCNOT gates, and one $CR_Y$ gate. For illustration, Figure <ref> details the representation of $C^5R_Y$ gate using four ancilla qubits. The $CR_Y$ gate can again be decomposed into a combination of single qubit and CNOT gates as detailed in Figure <ref>.

In Figure <ref>, $q_i, i=0\dots 4$ represent the control qubits (parent nodes), and $q_5$ is the target qubit (child node). As there are five control qubits, we use four ancilla qubits ($a_j, j=0\dots 3$). In total, we have 8 CCNOT gates ($2\times (5-1)$), two CNOTs and two single-qubit rotation gates. In Figure <ref>, there are two control qubits ($n=2$) for $q_2$ (node C), we will use one ancilla qubit to make the $CCR_Y$ gates. Note that we do not need a different set of ancilla qubits for implementing various controlled rotations (conditional probabilities), and we can the same set of ancilla qubits for all the $C^nR_Y$ rotations. Moreover, we can use the same set of ancilla qubits to build the $C^nR_Y$ rotations associated with various child nodes. Consider a Bayesian network with $s$ two-state nodes given by ${V_1, V_2,\dots V_s}$ and let $|.|$ denote the cardinality operator. For a node $V_i$, $|\Pi_{V_i}|$ provides the number of parent nodes of a $V_i$. For a root node,  $|\Pi_{V_i}| = 0$ and for a child node, $|\Pi_{V_i}| > 0$. Therefore, the total number of qubits required to represent a Bayesian network with two-state nodes (denoted as $m_{BN,2}$) can be calculated as

\begin{equation}
\label{eqn:total_2qubit}
m_{BN,2} = s + \max \Big(|\Pi_{V_1}|, |\Pi_{V_2}|, \dots |\Pi_{V_s}|\Big) - 1
\end{equation}

where $s$ qubits are used to represent $s$ nodes in the Bayesian network, and an additional $\max \Big(|\Pi_{V_1}|, |\Pi_{V_2}|, \dots |\Pi_{V_s}|\Big)-1$ ancilla qubits are used to represent the multi-qubit conditional rotations.

@C=0.5em @R=0.9em
q_0:0     1

q_1:0      1

q_2:0      1

q_3:0      1      =

q_4:0      1

q_5:0      R_Y (θ)     @C=0.6em @R=0.9em
q_0:0        1                                      1

q_1:0        4                                      4

q_2:0           3                                3

q_3:0               3                          3

q_4:0                   3                  3

a_0:0         1                                1

a_1:0             1                        1

a_2:0                1                  1

a_3:0                        1       1

q_5:0                    R_Y(θ/2)      R_Y(-θ/2)

Representation of $C^5R_Y$ gate using ancilla qubits

§.§ Representing discrete variables with more than two states

When a node has more than two states, then we need to use more than one qubit to represent it, as one qubit can represent only two states. Consider a random variable $V_i$ with $n_i$ states, denoted as $V_{i,j}, j=0,1,\dots n_i-1$, and $P(V_{i,j})$ represents the probability of state $V_{i,j}$; therefore, $\sum_{j=0}^{n_i-1} P(V_{i,j})=1$.

Let $m_i$ represent the number of qubits to represent $V_i$. The number of states that are represented by $m_i$ qubits is $2^{m_i}$, which needs to be greater than or equal to $n_i$.
Thus, value of $m_i$ can be calculated as the smallest integer that is greater than or equal to ${\log_2 n_i}$, which can be represented using the ceiling function as $m_i = \ceil[\big]{\log_2 n_i}$, where $\ceil[\big]{.}$ is the ceiling function.
Let $\Ket{q_j} j=l\dots l+m_i-1$ represent $m_i$ qubits in the quantum circuit used to represent $V_i$. In addition to qubits representing node $V_i$, there could be other qubits in the quantum circuit, which are used to represent other nodes and/or ancilla qubits. Here, $l$ is used to represent the indices of the qubits used to represent node $V_i$. The superposition state, $\Ket{q_l q_{l+1} \dots q_{l+m_i-1}}$ can be written in terms of the basis states as

\begin{equation}
\label{eqn:mstate}
\Ket{q_l q_{l+1} \dots q_{l+m_i-1}} = \sum_{j=0}^{2^{m_i}-1} \alpha_t \Ket{q_l q_{l+1} \dots q_{l+m_i-1}}_j
\end{equation}

@C=1em @R=0em
0        4U_0,1 …m_i-1

0        U_0,1 …m_i-1

0        U_0,1 …m_i-1             =

⋯    U_0,1 …m_i-1     ⋯

0        U_0,1 …m_i-1           @C=1em @R=0em
0    R_Y(θ_l)     1     X     1     X

0        3U_1 …m_i-1, q_l = 1         3U_1 …m_i-1, q_l = 0

0        U_1 …m_i-1, q_l = 1         U_1 …m_i-1, q_l = 0

⋯    U_1 …m_i-1, q_l = 1     ⋯    U_1 …m_i-1, q_l = 0     ⋯

0        U_1 …m_i-1, q_l = 1         U_1 …m_i-1, q_l = 0

Decomposing a $m_i$ qubit rotation into single qubit  and Controlled $m_i$ - 1 qubit rotations

In Eq. (<ref>), $\Ket{q_l q_{l+1} \dots q_{l+k-1}}_j$ represents a basis state ($\Ket{00\dots 0}$ for instance) and $\alpha_j$ represents its probability amplitude. Let us map the $n_i$ states of the variable to $n_i$ basis states represented by these $m_i$ qubits. Hence, state $V_{i,j}$ can be mapped to the quantum state $\Ket{q_l q_{l+1} \dots q_{l+m_i-1}}_j$. The probability amplitudes of these $n_i$ quantum states can be calculated using the available state probabilities and the probability amplitudes of the remaining quantum states are set to zero. Therefore, $\alpha_j = \sqrt{P(V_{i,j})}$ when $j<n_i$ and $\alpha_j = 0$ when $n_i\leq j < 2^{m_i}$.

Our goal is to identify the gate $U$ that acts on $m_i$ qubits and produces the desired state probabilities, i.e., $U\Ket{0}^{\otimes m_i} = \Ket{q_l q_{l+1} \dots q_{l+m_i-1}}$ which is equlal to $\sum_{j=0}^{n_i-1} \sqrt{P(V_{i,j})} \Ket{q_l q_{l+1} \dots q_{l+m_i-1}}_j$. Since $U$ is a multi-qubit gate, it needs to be decomposed into a set of elementary gates discussed in Section <ref>. Our approach is to decompose the probability distribution defined over $m_i$ qubits into a combinations of marginal and conditional distributions that can be implemented using single-qubit and controlled-rotations. First, we rotate the first qubit ($q_l$) to obtain its associated probability values corresponding to its $\Ket{0}$ and $\Ket{1}$ states respectively using a single-qubit $R_Y$ rotation, and we implement a different multi-qubit rotation on the remaining $k-1$ when $q_l=\Ket{0}$ and $q_l=\Ket{1}$.

Figure <ref> details the decomposition of a $m_i$ qubit rotation into a combination of single-qubit and controlled $m_i$-1 qubit rotations, where $U_{0,1 \dots m_i-1}$ is the $m_i$ qubit rotation, and $U_{1 \dots m_i-1, q_l=\Ket{1}}$ and $U_{1 \dots m_i-1, q_1=\Ket{0}}$ are the rotations implemented on $m_i-1$ qubits ($q_{l+1},q_{l+2} \dots q_{l+m_i-1}$) when $q_l=\Ket{1}$ and $q_l=\Ket{0}$ respectively. $R_Y(\theta_l)$ represents the rotation to obtain the probabilities associated with qubit $q_l$, and can be calculated using Eq. (<ref>). The probabilities of $\Ket{0}$ and $\Ket{1}$ states of $q_l$ can be calculated using an indicator function, $\mathbb{I}_{q_l}$, defined as

\begin{equation}
\label{eqn:ql}
\mathbb{I}_{q_l}(\Ket{q_l q_{l+1} \dots q_{l+m_i-1}})=
\left\{
\begin{array}{ll}
1  & \mbox{if } \Ket{q_l}=\Ket{1} \\
0 & \mbox{if } \Ket{q_l}=\Ket{0}
\end{array}
\right.
\end{equation}

Using Eq. (<ref>), the probability that $q_l=\Ket{1}$ can be calculated as $P(q_l=\Ket{1}) = \sum_{j=0}^{2^{m_i}-1} \alpha_j^2 \mathbb{I}_{q_l}(\Ket{q_l q_{l+1} \dots q_{l+m_i-1}}_j)$, and $P(q_l=\Ket{0}) = 1-P(q_l=\Ket{1})$. The rotation angle, $\theta_l$ in Figure <ref> can be calculated using Eq. (<ref>) as

\begin{equation}
\label{eqn:rot_ql}
\begin{aligned}
\theta_l & = 2\times \tan^{-1} \sqrt{\dfrac{P(q_l=\Ket{1})}{P(q_l=\Ket{0})}} \\
& = 2\times \tan^{-1}\sqrt{\dfrac{\sum_{j=0}^{2^{m_i}-1} \alpha_j^2 \mathbb{I}_{q_l}(\Ket{q_l q_{l+1} \dots q_{l+m_i-1}}_i)}{1-\sum_{j=0}^{2^{m_i}-1} \alpha_j^2 \mathbb{I}_{q_l}(\Ket{q_l q_{l+1} \dots q_{l+m_i-1}}_j)}}
\end{aligned}
\end{equation}

The above procedure for decomposing $m_i$ qubit rotation into a single qubit and controlled $m_i$-1 qubit rotations can again be used to decompose the controlled $m_i$-1 qubit rotation resulting in controlled single-qubit and controlled-controlled $m_i$-2 qubit rotations. We will illustrate the decomposition of $CU_{1 \dots m_i-1, q_l=\Ket{1}}$ in Figure <ref>.

@C=1em @R=0.5em

3U_1 …m_i-1, q_l=1

U_1 …m_i-1, q_l=1        =

⋯    U_1 …m_i-1, q_l=1     ⋯

U_1 …m_i-1, q_l=1

@C=1em @R=0.8em
1     1   1   1     1

R_Y(θ_l+1,q_l=1)     1   X   1     X

2U_2 …m_i-1, q_l=1, q_l+1=11       2U_2 …m_i-1, q_l=1, q_l+1=0

⋯    ⋯    U_2 …m_i-1, q_l=1, q_l+1=11   ⋯    U_2 …m_i-1, q_l=1, q_l+1=0     ⋯

U_2 …m_i-1, q_l=1, q_l+1=11       U_2 …m_i-1, q_l=1, q_l+1=0        22571.5em–

Decomposing a controlled $m_i$-1 qubit rotation into controlled single qubit  and controlled-controlled $m_i$-2 qubit rotations

First, we implement a $CR_Y$ gate on qubit $q_{l+1}$ to obtain the probabilities of $q_{l+1}$ when $q_l=\Ket{1}$. The probabilities of $q_{l+1}=\Ket{0}$ and $q_{l+1}=\Ket{1}$ when $q_l=\Ket{1}$ are calculated using another indicator function defined over $q_l$ and $q_{l+1}$ as

\begin{equation}
\label{eqn:ql1}
\begin{split}
&\mathbb{I}_{q_l=1, q_{l+1}}(\Ket{q_l q_{l+1} \dots q_{l+m_i-1}})\\
&= \left\{
\begin{array}{ll}
1  & \mbox{if } \Ket{q_l}=\Ket{1} \text{and} \Ket{q_{l+1}}=\Ket{1} \\
0 & \mbox{if } \Ket{q_l}=\Ket{1} \text{and} \Ket{q_{l+1}}=\Ket{0}
\end{array}
\right.
\end{split}
\end{equation}

\begin{equation}
\label{eqn:rot_ql1}
\begin{split}
&\theta_{l+1, q_l=\Ket{1}}  = 2\times \tan^{-1} \sqrt{\dfrac{P(q_{l+1}=\Ket{1}|q_l=\Ket{1})}{P(q_{l+1}=\Ket{0}|q_l=\Ket{1})}}\\
& = 2\times \tan^{-1}\sqrt{\dfrac{P(q_{l+1}=\Ket{1},q_l=\Ket{1})}{P(q_{l+1}=\Ket{0},q_l=\Ket{1})}} = 2\times \\
& \tan^{-1}\sqrt{\dfrac{\sum_{j=0}^{2^{m_i}-1} \alpha_j^2 \mathbb{I}_{q_l=\Ket{1}, q_{l+1}}(\Ket{q_l q_{l+1} \dots q_{l+m_i-1}}_j)}{1-\sum_{i=0}^{2^{m_i}-1} \alpha_j^2 \mathbb{I}_{q_l=1, q_{l+1}}(\Ket{q_l q_{l+1} \dots q_{l+m_i-1}}_j)}}
\end{split}
\end{equation}

$CCU_{2 \dots m_i-1, q_l=\Ket{1}, q_{l+1}=\Ket{1}}$ and $CCU_{2 \dots m_i-1, q_l=\Ket{1}, q_{l+1}=\Ket{0}}$ are again decomposed into a set of controlled-controlled single qubit rotations and triply controlled $m_i$-3 qubit rotations following the procedure described above. This decomposition is carried out until we reach $m_i-1$ controlled qubit rotations implemented on the qubit $q_{l+m_i-1}$. In this way, a $m_i$-qubit rotation required to realize the probabilities associated with a discrete variable with more than two states is achieved through uncontrolled/controlled/multi-controlled qubit rotations. Multi-controlled qubit rotations can be implemented using ancilla qubits as detailed in Figure <ref>. When the multi-state variable is a child node, then we will have a different $m_i$ qubit rotation for each combination of the parent nodes. Depending on the number of parent nodes, Each controlled/multi-qubit controlled $m_i$-qubit rotation can be represented following the above sequential decomposition process.

In Section <ref>, we discussed the implementation of controlled rotations to realize conditional probabilities of a child node when both the parent and child nodes have two states. Here, let us consider the cases when a combination of multi-state variables and two-state variables are parent nodes for a multi-state child node. Consider a variable $V_i$ with $n_i$ states with $\Pi_{V_i}$ as the set of parent nodes. Let $\Pi_{V_{i,j}}$ represent the $j^{th}$ parent node and $n_{\Pi_{V_{i,j}}}$ represent the number of discrete states in the $j^{th}$ parent node. Number of qubits required to represent $\Pi_{V_i}$ can be calculated as

\begin{equation}
\label{eqn:nq_parent}
m_{q, \Pi_{V_i}} = \sum_{i=1}^{|\Pi_{V_i}|} \ceil{\log_2 n_{\Pi_{V_{i,j}}}}
\end{equation}

where $m_{q, \Pi_{V_i}}$ is the number of qubits required to represent $\Pi_{V_i}$ and $|\Pi_{V_i}|$ represents the cardinality of the set of parent nodes. If $n_i$ represents the number of states of child node $V_i$, then the highest order of $C^nR_Y$ gate required to realize the conditional probabilities of $V_i$ can be calculated as $n = m_{q, \Pi_{V_i}} + \ceil{\log_2 n_i}$. In order to implement this $C^nR_Y$ gate, we will need $n-1 = m_{q, \Pi_{V_i}} + \ceil{\log_2 n_i}-1$ ancilla qubits. Therefore, the total number of qubits required to obtain a Bayesian network with a combination of two-state and multi-state variables is given as

\begin{equation}
\label{eqn:nBN}
m_{BN} = \Bigg(\sum_{i=1}^m \ceil{\log_2 n_i}\Bigg) + \max_i \Big(m_{q, \Pi_{V_i}} + \ceil{\log_2 n_i} - 1\Big)
\end{equation}

where $m_{BN}$ denoted the number of qubits required to represent a given BN, $m_{q, \Pi_{V_i}} + \ceil{\log_2 n_i} - 1$ is the number of ancilla qubits required to realize the conditional probabilities of node $V_i$. As mentioned in Section <ref>, the same set of ancilla qubits can be used for various child nodes. Since qubits can represent only discrete states, any continuous variables need to be discretized to be represented using qubits. If a continuous variable is discretized into more than two states, then the above procedure to handle discrete variables with more than two levels can be used. If the discretization involves only two states, a single qubit can be used to represent it.

§ ILLUSTRATION EXAMPLES

For illustration of the proposed methodology, we consider three examples with varying properties from the financial industry: (1) a 4-node Bayesian network for an oil company stock price prediction; (2) a 10-node Bayesian network used for liquidity risk assessment; and (3) a Naive Bayes classifier with 8 features (a total of 9 nodes) used for bankruptcy prediction. The first two BNs consider random variables with only two states whereas the Naive Bayes classifier considers nodes that have two and three states. In particular, there are six features with three states, two features with two states, and a class variable with two classes. We considered both 4-node and 10-node BNs to demonstrate the scalability of the proposed methods.

For each of the three examples, we will design quantum circuits using the proposed C-QBN approach, and then execute them using Qiskit, which is a Python-based simulated quantum computing platform developed by IBM [Wille et al., 2019]. We demonstrate the proposed methods on a simulated platform instead of using real quantum computers as hardware implementation of circuits of large depths (large number of gates) are affected by noise, which leads to incorrect results [Mandviwalla et al., 2018, Martin et al., 2019]. Since simulations are not affected by hardware noise, we use them to demonstrate the proposed methods. The probabilities of various states of the BNs are computed, and these results are compared with the probabilities obtained from simulating the examples on a classical Bayesian network platform such as Netica [Netica, 2019].

§.§ 4-node BN: Oil Company Stock Price

This 4-node Bayesian network example to assess an oil company stock price is obtained from [Shenoy & Shenoy, 2000]. The four variables in this network are the interest rate (IR), stock market (SM), oil industry (OI), and oil company stock price (SP). IR has two states - high and low; SM has two states - good and bad; OI has two states - good and bad; and SP has two states - high and low. Here, we represent low/bad with state 0 and high/good with state 1. The dependence between these four variables and associated conditional probability tables are given in Figure <ref>.

The BN in Figure <ref> has two root nodes, i.e. nodes without parent nodes (IR, OI), one node with only one parent node (SM), and one node with two parent nodes (SP). Since SP has two parent nodes, we use one ancilla qubit to represent its conditional probability values as discussed in Section <ref>. This results in a five-qubit system (four qubits to represent four variables in Figure <ref> and an ancilla qubit). We discuss below the construction of quantum circuits corresponding to this BN using the C-QBN approach described in Section <ref>.

Bayesian network for an oil company stock price [Shenoy & Shenoy, 2000]

Quantum circuit: Figure <ref> provides the quantum circuit corresponding to the BN in Figure <ref> constructed using the C-QBN approach. The five qubits are denoted as $q_i, i=0\dots 4$ and the measurement bit is denoted as $c$.

The variables - IR, OI, SM, and SP are denoted using the qubits $q_4, q_3, q_2$ and $q_0$ respectively, and the ancilla qubit is $q_1$. We chose $q_1$ as the ancilla qubit for the purpose of illustration. In reality, any qubit can be chosen as an ancilla qubit in Qiskit. We used this mapping as the representation of an n+1-qubit state is given as $\Ket{q_nq_{n-1}\dots q_0}$, i.e., the state of the $n+1^{th}$ qubit ($q_n$) is written first while the first qubit ($q_0$) is written at the end. By following this mapping, the parent nodes appear ahead of their associated child nodes.

After mapping the variables to various qubits, we now identify the appropriate gates to be implemented on those qubits to obtain the required marginal or conditional probability values. Let us begin with the root nodes (IR and OI). The rotation angles required to represent those root nodes were calculated using Eq. (<ref>) as $\theta_{IR} = 2\times \tan^{-1}\bigg(\sqrt{\dfrac{0.25}{0.75}}\bigg) = \dfrac{\pi}{3}$ and $\theta_{OI} = 2\times \tan^{-1}\bigg(\sqrt{\dfrac{0.4}{0.6}}\bigg) = 1.37$.
For realizing child nodes, we compute the associated rotation angles for various combinations of the parent node(s).

Quantum circuit of the 4-node oil company stock price BN. Variables IR, OI, SM and SP are mapped to $q_4$, $q_3$, $q_2$, and $q_0$ respectively, and $q_1$ is the ancilla qubit

To represent SM node, we compute its rotation angles when IR=0 and IR=1 as $\theta_{SM,0} = 2\times \tan^{-1}\bigg(\sqrt{\dfrac{0.7}{0.3}}\bigg) = 1.982$ and $\theta_{SM,1} = 2\times \tan^{-1}\bigg(\sqrt{\dfrac{0.2}{0.8}}\bigg)=0.928$ respectively. Here, $\theta_{SM,j}$ corresponds to the rotation angle of SM for a given value $j$ of its parent node, IR. As discussed in Section <ref>, the controlled rotations are decomposed into a combination of uncontrolled rotations and CNOT gates. For example, the conditional probability values of SM when IR=1 are realized by implementing a controlled-rotation gate $CR_Y(\theta_{SM,1})$. Following Section <ref>, this gate is implemented as $\bigg(I\otimes R_Y\bigg(\dfrac{\theta_{SM,1}}{2}\bigg)\bigg)CX\bigg(I\otimes R_Y\bigg(\dfrac{-\theta_{SM,1}}{2}\bigg)\bigg)CX$. The controlled-rotation when IR=0 is implemented by first flipping the states of the $q_4$ (IR) qubit using an $X$ gate, and then applying the $CR_Y(\theta_{SM,0})$ gate. Thus, the conditional probability values of SM are realized for various values of its parent node (IR). We now consider the SP node.

Since SP has two parent nodes, we have four rotation angles ($\theta_{SP,00}$, $\theta_{SP,01}$, $\theta_{SP,10}$, $\theta_{SP,11}$) for various values of the two parent nodes; these values were calculated using Eq. (<ref>) as $0.644, 1.772, \frac{\pi}{2}, 2.22$ respectively. Here, $\theta_{SP,jk}$ corresponds to the rotation angle of SP for given values $j$ and $k$ of parent nodes OI and SM respectively. Following Section <ref>, the controlled-controlled rotations are implemented using an ancilla qubit. At the end of the circuit, we add the measurement gates and stores the measured qubit values in a classical bit register ($c$ in Figure <ref>). We consider only four measurements across the qubits associated with various nodes in the BN, and do not consider a measurement gate for the ancilla qubit as it does not represent any variable in the BN.

Circuit simulation: The BN is simulated using the circuit constructed with the C-QBN approach, and the accuracy of the results is compared with those obtained using Netica, which is a classical Bayesian network software.

After a simulation is made, the system is measured, which returns a single quantum state (such as $\Ket{1010}$). A total of 8192 shots were carried out in each simulation, and the measured states after each shot are used to estimate the the probabilities of all the states. We used 8192 shots as that was the maximum number of shots possible on the real IBM quantum computers such as the 5-qubit IBM QX5 [Mandviwalla et al., 2018].

When a measurement is made, one of the 16 states is observed as we were measuring only four qubits corresponding to four nodes in the BN. The probability associated with each state ($P(\Ket{q_4q_3q_2q_0})$) can be computed using the Monte Carlo approach as

\begin{equation}
P(\ket{q_4q_3q_2q_0}) = \dfrac{n_{\ket{q_4q_3q_2q_0}}}{N}
\end{equation}

where $P(\Ket{q_4q_3q_2q_0})$ is the probability of state $\Ket{q_4q_3q_2q_0}$; $n_{\Ket{q_4q_3q_2q_0}}$ and $N$ represent the number of times $\Ket{q_4q_3q_2q_0}$ is observed and the total number of shots  (8192) respectively. The marginal probabilities of each of the nodes can be estimated using Equation by marginalizing over the state probabilities calculated using Eq. (<ref>).

\begin{equation}
\label{eqn:marginalize}
P(\Ket{q_i}) = \sum_{q_j, j=4,3,2,0, j\neq i} P(\Ket{q_4q_3q_2q_0})
\end{equation}

Comparison of simulation results: As discussed above, we ran 8192 shots of the quantum circuit to estimate the marginal probabilities. Since the marginal probabilities are estimated from data, there could be variation across multiple runs of the quantum circuit. In order to quantify the variation across runs, we ran the circuit $r$ times and obtained the marginal probability values from each run. Given the simulation results from $r$ runs, we compute the $(1-\alpha)$ confidence intervals of the estimated marginal probabilities and checked if the marginal probabilities from Netica fall within the estimated intervals.

Let $p_i^m, i=1\dots r, m={IR, OI, SM, SP}$ represent the marginal probability value of the $m^{th}$ variable in the $i^{th}$ run, then the sample mean and standard deviation can be calculated as $\bar{p}^m = \dfrac{\sum_{i=1}^{r} p_i^m}{r}$ and $s^m = \sqrt{\dfrac{\sum_{i=1}^{r} (p_i^m-\bar{p}^m)^2}{r-1}} $ respectively. Given the sample mean and standard deviation, the $(1-\alpha)$ confidence interval were calculated as $\bar{p}^m \pm t_{\frac{\alpha}{2}} \dfrac{s^m}{\sqrt{r}}$. Here, $t_{\frac{\alpha}{2}}$ is the t-statistic corresponding to the $(1-\alpha)$ confidence interval.  In this study, we chose $r=10$ and $\alpha=0.05$. The sample mean and standard deviation, and the 95% CIs of the marginal probabilities using both the methods are provided in Table <ref>, along with the marginal probabilities obtained using Netica. The variation in the probability values obtained using the C-QBN approach, can be attributed to the variability in the measurement process.

From Table <ref>, it can be observed that the marginal probabilities from Netica fall within their estimated confidence intervals obtained from the quantum circuit simulations. Since each node has two states, we provided the probabilities of only one of the states as the probabilities of the other states can be computed from the given states. For example, $P(IR=1)=1-P(IR=0)$. Thus, the C-QBN approach was used to represent the 4-node Bayesian network.

Simulation results using Qiskit with 8192 shots of the oil company stock price BN

Comparison of marginal probabilities in the 4-node Bayesian network

Netica     3c|C-QBN

Value      Probability       Mean     SD     95% CI

IR=0      0.75      0.7504      0.0042    [0.7471, 0.7536]

SM=0      0.425       0.4252     	0.0064    [0.4219, 0.4284]

OI=0      0.6     0.5999	    0.0050    [0.5962, 0.6037]

SP=0       0.499      0.4994      0.0045    [0.4950, 0.5022]

§.§ 10-node BN: Liquidity Risk Assessment

Bayesian network for liquidity risk assessment [Tavana et al., 2018]

Here, we consider designing a quantum circuit to represent a 10-node Bayesian network obtained from [Tavana et al., 2018] used for liquidity risk assessment in banking. The 10 variables in the Bayesian network are described in Table <ref>, and the dependence between various variables are shown in Figure <ref>, and the conditional probability tables are given in Figure <ref>.

In Table <ref>, B refers to the bank under consideration, and O refers to other banks. This BN has one root node ($X_6$), six nodes with one parent node ($X_7, X_8, X_9, X_1, X_2, X_3$), two nodes with two parent nodes ($X_4, X_5$), and one node with three parent nodes ($X_{10}$). Since the maximum number of parent nodes is three, we need two ancilla qubits to represent the conditional probability values in addition to the ten qubits used to represent the ten nodes in the BN totaling to 12 qubits. The representation of the root node ($X_6$), child nodes with either one or two parent nodes follows the same procedure as detailed in Section <ref>. Therefore, we discuss below the representation of $X_{10}$, which is the child node with three parent nodes ($X_1, X_2, X_4$) using the C-QBN approach.

Variables in the 10-node liquidity risk assessment Bayesian network [Tavana et al., 2018]

Variable       Description

$X_1$     $\text{Liquidity ratio} = \dfrac{\text{Liquid assets of \textbf{B}}}{\text{Current liabilities of \textbf{B}}}$

$X_2$     $\dfrac{\text{Credits of \textbf{B} in \textbf{O}}}{\text{Credits of \textbf{O} in \textbf{B}}}$

$X_3$     $\dfrac{\text{Long term deposits of \textbf{B}}}{\text{Short term deposits of \textbf{B}}}$

$X_4$     $\dfrac{\text{Credits of \textbf{B} in \textbf{O}}}{\text{Credits of \textbf{O} in \textbf{B}}}$

$X_5$     $\dfrac{\text{Total loan of \textbf{B}}}{\text{Total deposits of \textbf{B}}}$

$X_6$     $\dfrac{\text{bonds of \textbf{B}}}{\text{Total assets of \textbf{B}}}$

$X_7$     $\dfrac{\text{Volatile deposits of \textbf{B}}}{\text{Total liabilities of \textbf{B}}}$

$X_8$     $\dfrac{\text{Short investments of \textbf{B}}}{\text{Total assets of \textbf{B}}}$

$X_9$     $\dfrac{\text{Credits of \textbf{B} in central bank}}{\text{Total deposits of \textbf{B}}}$

$X_{10}$     $\text{Bank liquidity risk} = \dfrac{\text{Long term deposits of \textbf{B}}}{\text{Short term deposits of \textbf{B}}}$

CPT for liquidity risk assessment Bayesian network [Tavana et al., 2018]

Quantum circuit: Figure <ref> provides the quantum circuit of the 10-node BN constructed the C-QBN approach. The 12 qubits are denoted as $q_i, i=0\dots 11$ and the measurements of various qubits are stored in classical bits denoted as $c$. In this circuit $X_1$ is mapped to qubit $q_7$, $X_2$ represented by $q_3$, $X_3$ to $q_4$, $X_4$ to $q_6$, $X_5$ to $q_5$, $X_6$ to $q_{11}$, $X_7$ to $q_{10}$, $X_8$ to $q_9$, $X_9$ to $q_8$. Finally, $X_{10}$ is represented using $q_0$, and $q_1, q_2$ are the ancilla qubits. Since $X_{10}$ are three parent nodes, we need to implement $C^3R_Y$ gate for each of the 8(=$2^3$) combinations of the parent nodes. Following Section <ref>, the $C^3R_Y$ gate requires the use of two ancilla qubits, and is build through a combination of one, two, and three-qubit gates($R_Y$, CNOT, CCNOT).

For example, the conditional probability values of $X_5$ when $X_8=1$ and $X_4=0$ would be obtained by implementing a controlled-controlled rotation gate $CCR_Y$. Since $X_5$ has two parent nodes, we have four rotation angles($\theta_{X_5,00}$, $\theta_{X_5,01}$, $\theta_{X_5,10}$, $\theta_{X_5,11}$) for various values of the two parent nodes. Following Section <ref>, the controlled-controlled rotations for $X_5$ are implemented using one of the two available ancilla qubits ($q_2$ is used here).

Circuit simulation and results: Following the 4-node BN, we ran the quantum circuits obtained using the C-QBN ten times each with 8192 shots. The marginal probabilities of nodes from Netica, along with the sample mean, sample standard deviation and the 95% confidence intervals of the sample mean are provided in Table <ref>.

Simulation result using Qiskit with 8192 shots of the liquidity Risk Assessment BN

Comparison of marginal probabilities in the 10-node Bayesian network

Netica     3c|C-QBN

Value     Probability     Mean     SD     95% CI

$X_1=0$      0.431     0.4306     0.0025   [0.4287,  0.4326]

$X_2=0$      0.863       0.8638 	   	0.0019    [0.8624, 0.8653]

$X_3=0$     0.976     0.9757         	0.0009    [0.9750, 0.9764]

$X_4=0$       0.57      0.5694 	   	0.0024   [0.5676,	0.5712]

$X_5=0$      0.527        0.526	   	0.0034   [0.5235,	0.5286]

$X_6=0$      0.98       0.9805  	   	0.0007   [0.9800,	0.9810]

$X_7=0$     0.977        0.9767        	0.0009   [0.9760,	0.9773]

$X_8=0$     0.0261       0.0267         	0.0009   [0.0260,	0.0274]

$X_9=0$      0.956      0.9559 	    	0.0014   [0.9548,	0.9570]

$X_{10}=0$     0.24         0.2397	   	0.002   [0.2382, 0.2412]

From the results in Table <ref>, it can be observed that the true marginal probabilities (obtained from Netica) fall within the confidence intervals obtained using the C-QBN approach. These results help conclude that the C-QBN approach is able to simulate the 10-node Bayesian network with two and three parent nodes, each with two states.

§.§ 9-node Naive Bayes Classifier: Bankruptcy Prediction

Here, we consider designing a quantum circuit to represent a Naive Bayes classifier used for bankruptcy prediction; this model is obtained from [Sun & Shenoy, 2007]. There are eight features in this classifier that correspond to several financial-accounting, market-based, and other extraneous factors. The financial-accounting factors are Cash/Total Assets (CH), a variable related to the variation in cash and short-term marketable securities (LM), a binary variable to check if the net income was negative in the last two years (IT), and a variable that represents the ratio of the change in net income and the sum of the absolute net income in the last two years (CHN). The market-based factors are a variable that represents the natural logarithm of firm's size relative to the CRSP NYSE/AMEX/NASDAQ market capitalization index (M) and a variable that represents the difference of the firm's stock return and the value-weighted CRSP NYSE/AMEX/NASDAQ index return in the previous year (R).

Naive Bayes classifier for bankruptcy prediction [Sun & Shenoy, 2007]

CPT for bankruptcy prediction naive Bayes classifier [Sun & Shenoy, 2007]

The extraneous factors are variables that relate to the Compustat codings (AU) and Industry Failure Rate (IFR). The bankruptcy classification status is denoted with the variable B. Figure <ref> shows the Naive Bayes model, and the associated conditional probability tables are provided in Figure <ref>. The variables B, AU and IT have two states $\{0,1\}$ while all the remaining variables have three states $\{0,1,2\}$. We are using this example for the sake of illustration, and the readers are referred to [Sun & Shenoy, 2007] for more details about the variables and the model. Since each the variables B, AU and IT has two states, it can be represented using a single qubit. Each of the remaining variables has three states; therefore, each node is represented using $\ceil{\log_2 3} = 2$ qubits.

The total number of qubits used to represent the 9-node Naive Bayes classifier is 16 ($3\times1 + 6\times2 + 1$). The representation of the root node (B), and child nodes with one parent node (AU, IT) follows the procedure described in Section <ref>. Here, we discuss the representation of child nodes with more than two levels (CH, LM, M, R, CHN, IFR) using the C-QBN approach.

Quantum circuit:  The 16 qubits are denoted as $q_i, i=0 \dots 15$ and the measurements of various qubits are stored in the classical bit register $c$. The nine variables B, AU, IT, CH, LM, M, R, CHN, and IFR are mapped to $q_{15}, q_{14},q_{13}, (q_{12}, q_{11}),(q_{10}, q_{9}),(q_{8}, q_{7}),(q_{6}, q_{5}), (q_{4}, q_{3}),$ and $(q_{2}, q_{1})$ respectively. Any qubit can be chosen as the ancilla qubit, and in this example, we chose $q_0$ for the sake of illustration. We discuss the representation of CH, and the same procedure can be applied to other nodes as well. We map the three states of CH {0,1,2} to the states $\ket{00}$, $\ket{01}$, $\ket{10}$ of qubits $q_{12}$ and $q_{11}$. Figure <ref> shows the associated quantum circuit with gates associated with B and CH nodes only. We apply the appropriate $CU$ transformations to realize the conditional probability values for various values of B {0,1}. Here, the control qubit is $q_{15}$ and the target is a two-qubit system $(q_{12}, q_{11})$.

First, let us consider the case when $q_{15}=\Ket{1}$, i.e., B=1. When $q_{15}=\Ket{1}$, the transformation $U$ should result in the probability values of 0.19, 0.63 and 0.18 for $(q_{12}, q_{11})$ states of $\ket{00}$, $\ket{01}$ and $\ket{10}$ respectively. The probability of state $\Ket{11}$ is fixed at 0. The multi-qubit rotation $U$ is not an elementary transformation, we will decompose it into a combination of one and two-qubit elementary transformations. The probability of $\Ket{0}$ and $\Ket{1}$ states of $q_{12}$ can be calculated as $P(\Ket{00}) + P(\Ket{01}) = 0.19+0.63 = 0.82$ and $P(\Ket{10}) + P(\Ket{11}) = 0.18 + 0 = 0.18$ respectively. We realize the marginal probabilities of $q_{12}$ using a single-qubit $R_Y$ gate with the rotation angle $\theta_{q_{12}, q_{15} = \Ket{1}} = 2\times \tan^{-1}\bigg(\sqrt{\dfrac{0.18}{0.82}}\bigg) = 0.5725$.

After realizing the marginal probabilities of $q_{12}$, we consider the conditional probabilities of $q_{11}$ given $q_{12}$. When $q_{12}=\Ket{1}$, the probability of $q_{11}=\Ket{0}$ is computed using Eq. (<ref>) as

\begin{equation}
\label{eqn:cond_prob}
\begin{split}
P(q_{11}=\Ket{0}|q_{12}=\Ket{1}) &= \dfrac{P(q_{12}=\Ket{1},q_{11}=\Ket{0})}{P(q_{12}=\Ket{1})}\\
&= \dfrac{0.18}{0.18} = 1
\end{split}
\end{equation}

Therefore, $P(q_{11}=\Ket{1}|q_{12}=\Ket{1}) = 1-P(q_{11}=\Ket{0}|q_{12}=\Ket{1}) = 0$. Thus, the probability values associated with the $\ket{10}$ and $\ket{11}$ states are applied through a $CR_Y$ where $q_{12}$  and $q_{11}$ are the control and target qubits respectively, and with a rotation angle, $\theta_{q_{11}, q_{12}=\Ket{1} , q_{15}=\Ket{1}} = 2\times \tan^{-1}\bigg(\sqrt{\dfrac{1}{0}}\bigg) = \pi$. Similarly, when $q_{12}=\Ket{0}$, the probabilities of $q_{11}=\Ket{0}$ and $q_{11}=\Ket{1}$ is computed as $P(q_{11}=\Ket{0}|q_{12}=\Ket{0}) = \dfrac{P(q_{12}=\Ket{0},q_{11}=\Ket{0})}{P(q_{12}=\Ket{0})} = \dfrac{0.19}{0.82} = 0.232$ and $P(q_{11}=\Ket{1}|q_{12}=\Ket{0}) = 1-\dfrac{P(q_{12}=\Ket{0},q_{11}=\Ket{0})}{P(q_{12}=\Ket{0})} = 0.768$. Therefore, the rotation angle to show the conditional probability values when $q_{12}=\Ket{0}$ is $\theta_{q_{11}, q_{12}=\Ket{0}, q_{15}=\Ket{1}} = 2\times \tan^{-1}\bigg(\sqrt{\dfrac{0.768}{0.232}}\bigg) = 2.1365$. In this way, the two-qubit rotation gate $U$ is decomposed into a combination of single and two-qubit ($CR_Y$) gates. Since $U$ is implemented when $q_{15}=\Ket{1}$, the controlled-rotations in $U$ gate decomposition become controlled-controlled rotations with B as an additional control qubit. Following Section <ref>, the controlled-controlled rotations are implemented using an ancilla qubit. Similar decomposition procedure is followed to implement the two-qubit $U$ gate when $q_{15}=\Ket{0}$. In this way, the conditional probabilities associated with CH are realized. This procedure is then repeated to show the conditional probability values of three-level nodes LM, M, R, CHN, and IFR. Thus, the quantum circuit of the 9-node naive Bayes classifier is constructed using the C-QBN approach.

Comparison of marginal probabilities in the 9-node Naive Bayes classifier

Netica     3c|C-QBN

Value     Probability     Mean     SD     95% CI

B=0     0.5      0.5015	   	0.0051	   	[0.4977, 0.5054]

AU=0      0.595     	0.5992	   	0.0050	   	[0.5954, 0.6030]

IT=0      0.565    	0.5637	   	0.0047	   	[0.5602, 0.5672]

CH=0       0.24       	0.2429	   	0.0076	   	[0.2372, 0.2486]

CH=1     0.63     0.6269	   	0.0075	   	[0.6213, 0.6325]

LM=0      0.23      0.2306	   	0.0060	   	[0.2261, 0.2352]

LM=1     0.635     0.6368	   	0.0040	   	[0.6337, 0.6398]

M=0     0.295       0.2960	   	0.0042	   	[0.2928, 0.2991]

M=1     0.595     0.5957	   	0.0053	   	[0.5917, 0.5998]

R=0     0.395      	0.3940	   	0.0058	   	[0.3897, 0.3984]

R=1     0.475     0.4760	   	0.0050	   	[0.4723, 0.4798]

CHN=0     0.255       	0.2576	   	0.0045	    [0.2542, 0.2610]

CHN=1     0.585     0.5836	   	0.0061	   	[0.5790	, 0.5882]

IFR=0      0.14     	0.1384	   	0.0039	   	[0.1355, 0.1413]

IFR=1     0.72     0.7212	   	0.0043	   	[0.7179, 0.7244]

Circuit simulation and results: Similar to the previous examples, we ran the circuit 10 times, each with 8192 shots.The mean, standard deviation, and the 95% CI of the marginal probabilities are given in Table <ref>, from which it can be observed that the probability values from Netica fall within the 95% CI obtained from the C-QBN approach.
For variables with three states (CH, LM, M, R, CHN, IFR), we provided the probabilities of two states as the probability of the third state can be computed using the probabilities of the given states. For example, $P(M=2)=1-P(M=0)-P(M=1)$. These results help conclude that the proposed circuit construction approach can represent the 9-node Naive Bayes classifier. The histogram in Figure <ref> shows different quantum state probabilities in the partial circuit using nodes B and CH.

Each state represents a joint probability of the corresponding variables. The first value in each of the states corresponds to B and the other two are used to represent the three states of CH. Since CH has only three states irrespective of the value of $B$, the probability of state $\Ket{11}$ is fixed at zero. Therefore, the probabilities associated with $\Ket{011}$ and $\Ket{111}$ states are equal to zero and do not appear in the histogram.

Simulation results of nodes B and CH in the 9-node naive Bayes classifier using Qiskit with 8192 shots

§ CONCLUSION

This paper detailed the design of a quantum circuit to represent a generic discrete Bayesian network with nodes that may have two or more states. The quantum circuit design follows three steps. The first step is to map a Bayesian network node to one or more qubits depending on the number of states. The second step is mapping the marginal or conditional probabilities of nodes to probability amplitudes/probabilities associated with the qubits to be in $\Ket{0}$ and $\Ket{1}$ states. The third step is to realize the required probability amplitudes using single-qubit and (multi-qubit) controlled rotation gates. We used ancilla qubits for the implementation of multi-qubit rotation gates. When a node is mapped to more than one qubit, the multi-qubit rotations required to realize the required probabilities are decomposed into a combination of single-qubit and multi-qubit controlled rotations.

The proposed approach was demonstrated with three Bayesian networks: a Bayesian network with four nodes and each with two states used for an oil company stock prediction, a Bayesian network with ten nodes and each with two states used for liquidity risk assessment, and a Naive Bayes classifier with nine nodes (eight features). Of the nine nodes, three nodes had two states and six nodes had three states. The quantum circuits are designed and simulated on Qiskit [McKay et al., 2018], which is a Python-based simulator for quantum computing. We simulated each circuit with 8192 shots, and calculated the marginal probabilities associated with each node. Since the results from quantum circuit are stochastic, we repeated the simulations 10 times, each time with 8192 shots. Using the results from 10 simulations, we estimated the 95% confidence intervals. To validate the simulation results, we simulated the Bayesian networks using a classical Bayesian network software (Netica) and tested if the Qiskit results match the results from the classical software. We found that the marginal probabilities of all the nodes obtained from the classical implementations were within the 95% confidence intervals obtained from Qiskit.

All the quantum circuits in this work were designed manually. Future work should consider automating the design of quantum circuit for a given Bayesian network. We used a simulation platform in this work to validate the accuracy of the methods. In future, we will implement the proposed methods on real quantum computers, and study the effect of hardware noise on the circuit implementation.

[Aïmeur et al., 2007]
authorAïmeur, E., authorBrassard, G., &
authorGambs, S. (year2007).
titleQuantum clustering algorithms.
In booktitleProceedings of the 24th international
conference on machine learning (pp. pages1–8).

[Ajagekar et al., 2020]
authorAjagekar, A., authorHumble, T., &
authorYou, F. (year2020).
titleQuantum computing based hybrid solution strategies
for large-scale discrete-continuous optimization problems.
journalComputers & Chemical Engineering,  volume132, pages106630.

[Baritompa et al., 2005]
authorBaritompa, W. P., authorBulger, D. W., &
authorWood, G. R. (year2005).
titleGrover's quantum algorithm applied to global
journalSIAM Journal on Optimization,  volume15, pages1170–1184.

[Boixo et al., 2013]
authorBoixo, S., authorAlbash, T.,
authorSpedalieri, F. M., authorChancellor, N., &
authorLidar, D. A. (year2013).
titleExperimental signature of programmable quantum
journalNature communications,  volume4, pages2067.

[Brassard et al., 2002]
authorBrassard, G., authorHoyer, P.,
authorMosca, M., & authorTapp, A.
titleQuantum amplitude amplification and estimation.
journalContemporary Mathematics,  volume305, pages53–74.

[Bunyk et al., 2014]
authorBunyk, P. I., authorHoskinson, E. M.,
authorJohnson, M. W., authorTolkacheva, E.,
authorAltomare, F., authorBerkley, A. J.,
authorHarris, R., authorHilton, J. P.,
authorLanting, T., authorPrzybysz, A. J. et al.
titleArchitectural considerations in the design of a
superconducting quantum annealing processor.
journalIEEE Transactions on Applied
Superconductivity,  volume24, pages1–10.

[Büyüközkan et al., 2015]
authorBüyüközkan, G., authorKayakutlu, G.,
& authorKarakadılar, İ. S. (year2015).
titleAssessment of lean manufacturing effect on business
performance using bayesian belief networks.
journalExpert Systems with Applications,  volume42, pages6539–6551.

[Cai et al., 2016]
authorCai, B., authorLiu, H., & authorXie,
M. (year2016).
titleA real-time fault diagnosis methodology of complex
systems using object-oriented bayesian networks.
journalMechanical Systems and Signal Processing,
volume80, pages31–44.

[Cross et al., 2017]
authorCross, A. W., authorBishop, L. S.,
authorSmolin, J. A., & authorGambetta, J. M.
titleOpen quantum assembly language.
journalarXiv preprint arXiv:1707.03429, .

[Dallaire-Demers & Wilhelm, 2016]
authorDallaire-Demers, P.-L., & authorWilhelm, F. K.
titleQuantum gates and architecture for the quantum
simulation of the fermi-hubbard model.
journalPhysical Review A,  volume94, pages062304.

[Ferreiro et al., 2012]
authorFerreiro, S., authorArnaiz, A.,
authorSierra, B., & authorIrigoien, I.
titleApplication of bayesian networks in prognostics for a
new integrated vehicle health management concept.
journalExpert Systems with Applications,  volume39, pages6402–6418.

[Garvey et al., 2015]
authorGarvey, M. D., authorCarnovale, S., &
authorYeniyurt, S. (year2015).
titleAn analytical framework for supply network risk
propagation: A bayesian network approach.
journalEuropean Journal of Operational Research,
volume243, pages618–627.

[Gilks & Wild, 1992]
authorGilks, W. R., & authorWild, P.
titleAdaptive rejection sampling for gibbs sampling.
journalJournal of the Royal Statistical Society:
Series C (Applied Statistics),  volume41,

[Grover, 1996]
authorGrover, L. K. (year1996).
titleA fast quantum mechanical algorithm for database
journalarXiv preprint quant-ph/9605043, .

[Hosseini & Barker, 2016]
authorHosseini, S., & authorBarker, K.
titleModeling infrastructure resilience using bayesian
networks: A case study of inland waterway ports.
journalComputers & Industrial Engineering,  volume93, pages252–266.

[Kahn Jr et al., 1997]
authorKahn Jr, C. E., authorRoberts, L. M.,
authorShaffer, K. A., & authorHaddawy, P.
titleConstruction of a bayesian network for mammographic
diagnosis of breast cancer.
journalComputers in biology and medicine,  volume27, pages19–29.

[Kalet et al., 2015]
authorKalet, A. M., authorGennari, J. H.,
authorFord, E. C., & authorPhillips, M. H.
titleBayesian network models for error detection in
radiotherapy plans.
journalPhysics in Medicine & Biology,  volume60, pages2735.

[Kothamasu et al., 2006]
authorKothamasu, R., authorHuang, S. H., &
authorVerDuin, W. H. (year2006).
titleSystem health monitoring and prognostics—a review
of current paradigms and practices.
journalThe International Journal of Advanced
Manufacturing Technology,  volume28,

[Lee & Song, 2016]
authorLee, S.-H., & authorSong, J.
titleBayesian-network-based system identification of
spatial distribution of structural parameters.
journalEngineering Structures,  volume127, pages260–277.

[Li et al., 2017]
authorLi, C., authorMahadevan, S.,
authorLing, Y., authorChoze, S., &
authorWang, L. (year2017).
titleDynamic bayesian network for aircraft wing health
monitoring digital twin.
journalAIAA Journal,  volume55, pages930–941.

[Low et al., 2014]
authorLow, G. H., authorYoder, T. J., &
authorChuang, I. L. (year2014).
titleQuantum inference on bayesian networks.
journalPhysical Review A,  volume89, pages062315.

[Mandviwalla et al., 2018]
authorMandviwalla, A., authorOhshiro, K., &
authorJi, B. (year2018).
titleImplementing grover’s algorithm on the ibm quantum
In booktitle2018 IEEE International Conference on Big
Data (Big Data) (pp. pages2531–2537).

[Martin et al., 2019]
authorMartin, A., authorCandelas, B.,
authorRodríguez-Rozas, Á.,
authorMartín-Guerrero, J. D., authorChen, X.,
authorLamata, L., authorOrús, R.,
authorSolano, E., & authorSanz, M.
titleTowards pricing financial derivatives with an ibm
quantum computer.
journalarXiv preprint arXiv:1904.05803, .

[McKay et al., 2018]
authorMcKay, D. C., authorAlexander, T.,
authorBello, L., authorBiercuk, M. J.,
authorBishop, L., authorChen, J.,
authorChow, J. M., authorCórcoles, A. D.,
authorEgger, D., authorFilipp, S. et al.
titleQiskit backend specifications for openqasm and
openpulse experiments.
journalarXiv preprint arXiv:1809.03452, .

[Miyauchi & Nishimura, 2018]
authorMiyauchi, Y., & authorNishimura, H.
titleBayesian network modeling for specific health
checkups on metabolic syndrome.
In booktitleAdvances in Biomedical Informatics
(pp. pages79–96).

[Murphy & Russell, 2002]
authorMurphy, K. P., & authorRussell, S.
titleDynamic bayesian networks: representation,
inference and learning.
Ph.D. thesis.

[Nannapaneni et al., 2017]
authorNannapaneni, S., authorDubey, A., &
authorMahadevan, S. (year2017).
titlePerformance evaluation of smart systems under
In booktitle2017 IEEE SmartWorld, Ubiquitous
Intelligence & Computing, Advanced & Trusted Computed, Scalable Computing
& Communications, Cloud & Big Data Computing, Internet of People and Smart
City Innovation (SmartWorld/SCALCOM/UIC/ATC/CBDCom/IOP/SCI) (pp.

[Nannapaneni et al., 2018]
authorNannapaneni, S., authorDubey, A., &
authorMahadevan, S. (year2018a).
titleAutomated aircraft separation safety assurance using
bayesian networks.
In booktitle2018 Aviation Technology, Integration,
and Operations Conference (p. pages3199).

[Nannapaneni et al., 2018]
authorNannapaneni, S., authorMahadevan, S., &
authorDubey, A. (year2018b).
titleReal-time control of cyber-physical manufacturing
process under uncertainty.
In booktitleASME 2018 13th International
Manufacturing Science and Engineering Conference.
organizationAmerican Society of Mechanical Engineers
Digital Collection.

[Nannapaneni et al., 2016]
authorNannapaneni, S., authorMahadevan, S., &
authorRachuri, S. (year2016).
titlePerformance evaluation of a manufacturing process
under uncertainty using bayesian networks.
journalJournal of Cleaner Production,  volume113, pages947–959.

[Netica, 2019]
authorNetica (year2019).
titleNorsys software corporation, netica version 6.05.

[Nielsen & Chuang, 2002]
authorNielsen, M. A., & authorChuang, I.
titleQuantum computation and quantum information.
publisherAmerican Association of Physics Teachers.

[Ozols et al., 2013]
authorOzols, M., authorRoetteler, M., &
authorRoland, J. (year2013).
titleQuantum rejection sampling.
journalACM Transactions on Computation Theory
(TOCT),  volume5, pages11.

[Pettet et al., 2017]
authorPettet, G., authorNannapaneni, S.,
authorStadnick, B., authorDubey, A., &
authorBiswas, G. (year2017).
titleIncident analysis and prediction using clustering and
bayesian network.
In booktitle2017 IEEE SmartWorld, Ubiquitous
Intelligence & Computing, Advanced & Trusted Computed, Scalable Computing
& Communications, Cloud & Big Data Computing, Internet of People and Smart
City Innovation (SmartWorld/SCALCOM/UIC/ATC/CBDCom/IOP/SCI) (pp.

[Rebentrost et al., 2014]
authorRebentrost, P., authorMohseni, M., &
authorLloyd, S. (year2014).
titleQuantum support vector machine for big data
journalPhysical review letters,  volume113, pages130503.

[Shende & Markov, 2008]
authorShende, V. V., & authorMarkov, I. L.
titleOn the cnot-cost of toffoli gates.
journalarXiv preprint arXiv:0803.2316, .

[Shenoy & Shenoy, 2000]
authorShenoy, C., & authorShenoy, P. P.
titleBayesian network models of portfolio risk and
publisherThe MIT Press.

[Shor, 1994]
authorShor, P. W. (year1994).
titleAlgorithms for quantum computation: Discrete
logarithms and factoring.
In booktitleProceedings 35th annual symposium on
foundations of computer science (pp. pages124–134).

[Sun & Shenoy, 2007]
authorSun, L., & authorShenoy, P. P.
titleUsing bayesian networks for bankruptcy prediction:
Some methodological issues.
journalEuropean Journal of Operational Research,
volume180, pages738–753.

[Sun et al., 2006]
authorSun, S., authorZhang, C., & authorYu,
G. (year2006).
titleA bayesian network approach to traffic flow
journalIEEE Transactions on intelligent
transportation systems,  volume7,

[Tavana et al., 2018]
authorTavana, M., authorAbtahi, A.-R.,
authorDi Caprio, D., & authorPoortarigh, M.
titleAn artificial neural network and bayesian network
model for liquidity risk assessment in banking.
journalNeurocomputing,  volume275, pages2525–2554.

[Wille et al., 2019]
authorWille, R., authorVan Meter, R., &
authorNaveh, Y. (year2019).
titleIbm’s qiskit tool chain: Working with and
developing for real quantum computers.
In booktitle2019 Design, Automation & Test in Europe
Conference & Exhibition (DATE) (pp. pages1234–1240).

[Woerner & Egger, 2019]
authorWoerner, S., & authorEgger, D. J.
titleQuantum risk analysis.
journalnpj Quantum Information,  volume5, pages15.

[Xu, 2012]
authorXu, B. G. (year2012).
titleIntelligent fault inference for rotating flexible
rotors using bayesian belief network.
journalExpert Systems with Applications,  volume39, pages816–822.

[Zhu & Deshmukh, 2003]
authorZhu, J., & authorDeshmukh, A.
titleApplication of bayesian decision networks to life
cycle engineering in green design and manufacturing.
journalEngineering Applications of Artificial
Intelligence,  volume16, pages91–103.

Quantum circuit of the 10-node liquidity risk assessment BN. Variables $X_6$, $X_7$, $X_8$, $X_9$, $X_1$, $X_4$, $X_5$, $X_3$, $X_2$ and $X_{10}$ are mapped to $q_{11}$, $q_{10}$, $q_{9}$, $q_{8}$, $q_{7}$, $q_{6}$, $q_{5}$, $q_{4}$, $q_{3}$, and $q_{0}$ respectively, and $q_1$ and $q_0$ are the ancilla qubits.

Quantum circuit of the 10-node liquidity risk assessment BN. Variables $X_6$, $X_7$, $X_8$, $X_9$, $X_1$, $X_4$, $X_5$, $X_3$, $X_2$ and $X_{10}$ are mapped to $q_{11}$, $q_{10}$, $q_{9}$, $q_{8}$, $q_{7}$, $q_{6}$, $q_{5}$, $q_{4}$, $q_{3}$, and $q_{0}$ respectively, and $q_1$ and $q_0$ are the ancilla qubits. (contd)

Quantum circuit of the 10-node liquidity risk assessment BN. Variables $X_6$, $X_7$, $X_8$, $X_9$, $X_1$, $X_4$, $X_5$, $X_3$, $X_2$ and $X_{10}$ are mapped to $q_{11}$, $q_{10}$, $q_{9}$, $q_{8}$, $q_{7}$, $q_{6}$, $q_{5}$, $q_{4}$, $q_{3}$, and $q_{0}$ respectively, and $q_1$ and $q_0$ are the ancilla qubits. (contd)

Quantum circuit of the 10-node liquidity risk assessment BN. Variables $X_6$, $X_7$, $X_8$, $X_9$, $X_1$, $X_4$, $X_5$, $X_3$, $X_2$ and $X_{10}$ are mapped to $q_{11}$, $q_{10}$, $q_{9}$, $q_{8}$, $q_{7}$, $q_{6}$, $q_{5}$, $q_{4}$, $q_{3}$, and $q_{0}$ respectively, and $q_1$ and $q_0$ are the ancilla qubits. (contd)

Quantum circuit representing nodes B and CH in the 9-node naive Bayes classifier. Variables B, AU, IT, CH, LM, M, R, CHN, and IFR are mapped to $q_{15}, q_{14},q_{13}, (q_{12}, q_{11}),(q_{10}, q_{9}),(q_{8}, q_{7}),(q_{6}, q_{5}), (q_{4}, q_{3}),$ and $(q_{2}, q_{1})$ respectively, and $q_0$ is the ancilla qubit.