\node[factor] (P) {}; \node [below=.1cm of P] {$\diag(\prob_\rv{X})$};
\path (P) edge[double] node[above=0pt] {$s$} node[below=0pt] {$\ts$} ([xshift=1.5cm]P);
\node[fit=(current bounding box),inner ysep=1mm,inner xsep=0]{};
\end{tikzpicture}
} & $\diag(\prob_\rv{X})(s,\ts)= \delta_{s,\ts}\cdot \prob_\rv{X}(s)$ \\
\hline
\centering\raisebox{-.5\height}{
\begin{tikzpicture}[nodes = {draw= none, minimum size = 0pt},
factor/.style={rectangle, minimum size=.5cm, draw},
node distance=1.7cm]
\node[factor] (e) {$=$};
\node (U)[above left=.5cm and .8cm of e, anchor=east] {$s'$};
\node (UH)[below left=.5cm and .8cm of e, anchor=east] {$\ts'$};
\path (e) edge node[above=0cm, pos=1] {$y$} ([xshift=1cm]e);
\draw (e) |- (U);
\draw (e) |- (UH);
\node[fit=(current bounding box),inner ysep=1mm,inner xsep=0]{};
\end{tikzpicture}
} & \centering\raisebox{-.5\height}{
\begin{tikzpicture}[nodes = {draw= none, minimum size = 0pt},
factor/.style={rectangle, minimum size=.5cm, draw},
node distance=1.7cm]
\node[factor] (I) {}; \node [below = 0pt of I] {$I_y$};
\path (I) edge[double] node[above=0pt, pos=1] {$s$} node[below=0pt, pos=1] {$\ts$} ([xshift=-1cm]I);
\path (I) edge node[above=0pt, pos=1] {$y$} ([xshift=1cm]I);
\node[fit=(current bounding box),inner ysep=1mm,inner xsep=0]{};
\end{tikzpicture}
} & $I_y(s,\ts) = \delta_{s,\ts} \cdot \delta_{s,y}$ \\
\hline
\end{tabular}
\caption{Conversions between factor graphs and DeFGs}
\label{tb:CintoDeFG}
\end{table}
\subsection{``Closing-the-Box'' Operations on DeFGs}
We define the ``closing-the-box'' operations on DeFGs in the same manner as for factor graphs.
\begin{definition}[``Closing-the-Box'' Operations on DeFGs] \label{def:DeFG:CtB} \index{closing-the-box operations!of DeFGs}
Let $\set{G}=(\set{V}_1\sqcup\set{V}_2,\set{F},\set{E}_1\sqcup\set{E}_2)$ be a DeFG as defined in Definition~\ref{def:DeFG}.
Let $\set{G}'=(\set{V}'_1\sqcup\set{V}'_2,\set{F}')$ be a subgraph of $\set{G}$ such that if a variable vertex is in $\set{G}'$, then so do all of its neighbors (all of which are in $\set{F}$).
(We call such a subgraph a \emph{box} of $\set{G}$.)
The ``closing-the-box'' operation (\wrt $\set{G}'$) is to replace $\set{G}'$ in $\set{G}$ by a factor vertex associated with the \emph{exterior function} $f_{\set{G}'}$ of $\set{G}'$, where $f_{\set{G}'}$ is the resultant function by summing the product of the local functions associated with $\set{F}'$ over the variables associated with $\set{V}'_1\sqcup\set{V}'_2$.
Namely, $f_{\set{G}'}$ is defined as
\[
f_{\set{G}'}(\vs_{\cup_{a\in\set{F}'}\nb{a}\xk\set{V}'_2},\tvs_{\cup_{a\in\set{F}'}\nb{a}\xk\set{V}'_2};\vx_{\cup_{a\in\set{F}'}\delta{a}\xk\set{V}'_1}) \defeq \sum_{\vs_{\set{V}'_2},\tvs_{\set{V}'_2},\vx_{\set{V}'_1}} \prod_{a\in\set{F}'} f_a(\vs_\nb{a},\tvs_\nb{a};\vx_{\delta{a}}).\qedhere
\]
\end{definition}
An advantage of DeFGs over factor graphs for quantum probabilities is that a DeFG remains to be DeFG after any ``closing-the-box'' operations.
\begin{theorem}\label{thm:DeFG:CtB}
Given a DeFG, it remains a DeFG after a ``closing-the-box'' operation.
\end{theorem}
\begin{proof}
Consider the setup in Definition~\ref{def:DeFG:CtB}.
It suffices to show that the matrices associated with the exterior function $[f_{\set{G}'}(\vx)]_{\vs,\tvs}\defeq f_{\set{G}'}(\vs,\tvs;\vx)$ are PSD.
Using mathematical induction, it suffices to show that given any pair of functions $f_a(\vs_\nb{a},\tvs_\nb{a};\vx_{\delta{a}})$ and $f_b(\vs_\nb{b},\tvs_\nb{b};\vx_{\delta{b}})$ such that the matrices $[f_a(\vx_{\delta{a}})]_{\vs_\nb{a},\tvs_\nb{a}}\defeq f_a(\vs_\nb{a},\tvs_\nb{a};\vx_{\delta{a}})$ and $[f_b(\vx_{\delta{b}})]_{\vs_\nb{b},\tvs_\nb{b}}\defeq f_b(\vs_\nb{b},\tvs_\nb{b};\vx_{\delta{b}})$ are PSD, then, for each $i\in\delta{a}\cap\delta{b}$, $j\in\nb{a}\cap\nb{b}$, and $\vx_{\delta{a}\cup\delta{b}\xk i}\in\Tensor_{\ell\in\delta{a}\cup\delta{b}\xk i}\set{X}_\ell$, the matrix $[f(\vx_{\delta{a}\cup\delta{b}\xk i})]$ with its $(\vs_{\nb{a}\cup\nb{b}\xk j},\tvs_{\nb{a}\cup\nb{b}\xk j})$-th entry being
\sum_{s_j,\ts_j,x_i} f_a(\vs_\nb{a},\tvs_\nb{a};\vx_{\delta{a}})\cdot f_b(\vs_\nb{b},\tvs_\nb{b};\vx_{\delta{b}})
must also be PSD.
However, notice that given any complex-valued function $h(\vs_{\nb{a}\cup\nb{b}\xk j})$, it holds that
\begin{align*}
&\sum_{\vs_{\nb{a}\cup\nb{b}\xk j},\atop\tvs_{\nb{a}\cup\nb{b}\xk j}}
h(\vs_{\nb{a}\cup\nb{b}\xk j})\cdot
\left[\sum_{s_j,\ts_j,x_i} f_a(\vs_\nb{a},\tvs_\nb{a};\vx_{\delta{a}})\cdot f_b(\vs_\nb{b},\tvs_\nb{b};\vx_{\delta{b}})\right]
\cdot \conj{h(\tvs_{\nb{a}\cup\nb{b}\xk j})} = \\
h(\vs_{\nb{a}\cup\nb{b}\xk j})\!\cdot\!\mathbf{1}(s_j)\cdot
\bigg[f_a(\vs_\nb{a},\tvs_\nb{a};\vx_{\delta{a}})\cdot f_b(\vs_\nb{b},\tvs_\nb{b};\vx_{\delta{b}})\bigg]
\cdot \conj{h(\tvs_{\nb{a}\cup\nb{b}\xk j})\!\cdot\!\mathbf{1}(\ts_j)}
\geq 0,
\end{align*}
since the Hadamard product of two PSD matrices is PSD.\footnote{Here, $\mathbf{1}$ stands for the constant-$1$ function.}
\end{proof}
Similar to factor graphs, we define the partition sum of a DeFG\index{partition sum!of DeFGs} as the result of summing the global function over all of its variables.
Namely, we have the definition
\begin{equation}
Z(\set{G}) \defeq \sum_{\vs,\tvs,\vx} g(\vs,\tvs;\vx).
\end{equation}
Since the partition sum can be understood as the result of ``closing-the-box'' \wrt the graph itself, we have the following corollary as a direct result of Theorem~\ref{thm:DeFG:CtB}.
\begin{corollary}
The partition sum of a DeFG is real non-negative.
\end{corollary}
\section{DeFGs and Quantum Systems: Examples}
In this section, we would like to present several examples of DeFGs, especially the DeFGs representing elementary quantum systems.
Some of the examples presented here are related to the examples in~\cite{loeliger2017factor, loeliger2012factor}.
In particular, we would like to illustrate the connection between the marginals of DeFGs and elements from quantum information theory.
\begin{example}
\begin{figure}\centering
\begin{tikzpicture}[nodes = {draw= none, minimum size = 0pt},
factor/.style={rectangle, minimum size=.7cm, draw},
node distance=2cm]
\node[factor] (P) {}; \node [below=0pt of P] {$\diag(\prob_\rv{X})$};
\node[factor] (u1) [right of= P] {}; \node [below=0pt of u1] {$\hat{U}_1$};
\node[factor] (u2) [right of= u1] {}; \node [below=0pt of u2] {$\hat{U}_2$};
\node (um) [right of = u2] {$\cdots$};
\node[factor] (un) [right of= um] {}; \node [below=0pt of un] {$\hat{U}_n$};
\node[factor] (b) [right of= un] {}; \node [below=0pt of b] {$\hat{B}$};
\node[factor] (Q) [right of= b] {}; \node [below=0pt of Q] {$I_y$};

\path (P) edge[double] node[above] {$s_0$} node[below] {$\ts_0$} (u1);
\path (u1) edge[*-, double] (u2);
\path (u2) edge[*-, double] (um);
\path (um) edge[double] (un);
\path (un) edge[*-*, double] (b);
\path (b) edge[double] (Q);
\path (Q) edge node[above, pos=1] {$y$} ([xshift=1.5cm]Q);

\node(R1A) [above left = .1cm and .3cm of P]{};
\node(R1C) [below right = .5cm and .25cm of u1]{};
\draw[dashed, red] (R1A) rectangle (R1C);
\node [anchor=south east, font=\scriptsize, red] at (R1C) {$\rho_1$};

\node(R2A) [above left = .2cm and .4cm of P]{};
\node(R2C) [below right = .6cm and .25cm of u2]{};
\draw[dashed, red] (R2A) rectangle (R2C);
\node [anchor=south east, font=\scriptsize, red] at (R2C) {$\rho_2$};

\node(R3A) [above left = .3cm and .5cm of P]{};
\node(R3C) [below right = .7cm and .25cm of un]{};
\draw[dashed, red] (R3A) rectangle (R3C);
\node [anchor=south east, font=\scriptsize, red] at (R3C) {$\rho_n$};

\node(R4A) [above left = .3cm and .25cm of b]{};
\node(R4C) [below right = .7cm and .05cm of Q]{};
\draw[dotted, blue] (R4A) rectangle (R4C);

\node(R5A) [above left = .4cm and .25cm of un]{};
\node(R5C) [below right = .8cm and .15cm of Q]{};
\draw[dotted, blue] (R5A) rectangle (R5C);

\node(R6A) [above left = .5cm and .25cm of u2]{};
\node(R6C) [below right = .9cm and .25cm of Q]{};
\draw[dotted, blue] (R6A) rectangle (R6C);

\node(R7A) [above left = .6cm and .25cm of u1]{};
\node(R7C) [below right = 1cm and .35cm of Q]{};
\draw[dotted, blue] (R7A) rectangle (R7C);
\end{tikzpicture}
\caption{$n$ steps of unitary evolution followed by a projective measurement \wrt the computation basis.}
\label{fig:DeFG_2}\end{figure}
The DeFG in Figure~\ref{fig:DeFG_2} describes a quantum system with $n$ steps of unitary evolutions followed by a projective measurement \wrt the computation basis.
For every $k\in\{1,2,\ldots,n\}$, the exterior function of the k-th dashed box can be expressed as\footnote{Note that we may sometimes group the arguments of some functions (\eg, $\hat{U}_k$ in~\eqref{eq:footnote:group:argumnets}) using parentheses for better readability.}
\begin{align} \label{eq:footnote:group:argumnets}
\rho_k(s_k,\ts_k) &= \sum_{s_{k-1},\ts_{s-1}} \hat{U}_k((s_k,s_{k-1}),(\ts_k,\ts_{k-1}))\cdot \rho_{k-1}(s_{k-1},\ts_{k-1}).
\end{align}
Here, note that $\hat{U}_k((s_k,s_{k-1}),(\ts_k,\ts_{k-1}))=U_{s_k,s_{k-1}}U^\Herm_{\ts_{k-1},\ts_k}$ for some unitary matrix $U$.
The functions $\{\rho_k\}_{k=1}^n$ are the Schrödinger representation of the system.
Similarly, the exterior functions of the dotted boxes correspond to
the Heisenberg representation.
\end{example}
\begin{example}\label{ex:DeFG:unitary:measurement}
\begin{figure}\centering
\begin{tikzpicture}[nodes = {draw= none, minimum size = 0pt},
factor/.style={rectangle, minimum size=.7cm, draw},
node distance=2cm]
\node[factor] (P) {}; \node [below=0pt of P] {$\diag(\prob_\rv{X})$};
\node[factor] (u0) [right of= P] {}; \node [below=0pt of u0] {$\hat{U}_0$};
\node[factor] (A1) [right of= u0] {}; \node [below=0pt of A1] {$\hat{A}_1$};
\node[factor] (u1) [right of= A1] {}; \node [below=0pt of u1] {$\hat{U}_1$};
\node[factor] (A2) [right of= u1] {}; \node [below=0pt of A2] {$\hat{A}_2$};
\node[factor] (I) [right of = A2] {=}; \node [below=0cm of I] {$I$};
\path (P) edge[double] node[above] {$s_0$} node[below] {$\ts_0$} (u0);
\path (u0) edge[*-, double] node[above] {$s_1$} node[below] {$\ts_1$} (A1);
\path (A1) edge[*-, double] node[above] {$s_1'$} node[below] {$\ts_1'$} (u1);
\path (u1) edge[*-, double] node[above] {$s_2$} node[below] {$\ts_2$} (A2);
\path (A2) edge[*-, double] node[above] {$s_2'$} node[below] {$\ts_2'$} (I);
\path (A1) edge node[above, pos=1] {$y_1$} ([yshift=1cm]A1);
\path (A2) edge node[above, pos=1] {$y_2$} ([yshift=1cm]A2);
\end{tikzpicture}
\caption{A factor graph describing a two-measurement quantum system.}
\label{fig:DeFG_3}
\end{figure}
Figure~\ref{fig:DeFG_3} describes a DeFG for a quantum system with two measurements, where $\hat{A}_1$, $\hat{A}_2$ are functions such that $\sum_{y_k}\sum_{s_k'=\ts_k'} A_k(s_k',s_k,\ts_k',\ts_k;y_k)=\delta_{s_k,\ts_k}$ for each $k=1,2$.
\end{example}
\begin{example}
\begin{figure}\centering
\begin{tikzpicture}[nodes = {draw= none, minimum size = 0pt},
factor/.style={rectangle, minimum size=.7cm, draw},
node distance=1.45cm]
\node[factor] (P) {}; \node [below=0pt of P] {$\diag(\prob_\rv{X})$};
\node[factor] (u0) [right of= P] {}; \node [below=0pt of u0] {$\hat{U}_0$};
\node[factor] (b1) [right of= u0] {}; \node [below=0pt of b1] {$\hat{P}_1$};
\node[factor] (A1) [right of= b1] {};\node at (A1) {$I_y$};
\node[factor] (b1h) [right of= A1] {}; \node [below=0pt of b1h] {$\hat{P}_1$};
\node[factor] (u1) [right of= b1h] {}; \node [below=0pt of u1] {$\hat{U}_1$};
\node[factor] (b2) [right of= u1] {}; \node [below=0pt of b2] {$\hat{P}_2$};
\node[factor] (A2) [right of= b2] {};\node at (A2) {$I_y$};
\node[factor] (b2h) [right of= A2] {}; \node [below=0pt of b2h] {$\hat{P}_2$};
\node[factor] (I) [right of = b2h] {=};\node [below=0pt of I] {$I$};
\path (P) edge[double] node[above] {$s_0$} node[below] {$\ts_0$} (u0);
\path (u0) edge[*-, double] (b1);
\path (b1) edge[*-, double] (A1);
\path (A1) edge[*-, double] (b1h);
\path (b1h) edge[*-, double] (u1);
\path (u1) edge[*-, double] (b2);
\path (b2) edge[*-, double] (A2);
\path (A2) edge[*-, double] (b2h);
\path (b2h) edge[*-, double] (I);
\path (A1) edge node[above, pos=1] {$y_1$} ([yshift=1cm]A1);
\path (A2) edge node[above, pos=1] {$y_2$} ([yshift=1cm]A2);
\end{tikzpicture}
\caption{A factor graph describing a two-measurement quantum system with projective measure onto 1-dimension eigenspace.}
\label{fig:DeFG_4}
\end{figure}
The DeFG in Figure~\ref{fig:DeFG_4} is a special case of Example~\ref{ex:DeFG:unitary:measurement}, in which both measurements are projective measurements with one-dimensional eigenspaces.
Here, $\hat{P}_k(y_k,s_k,\ty_k,\ts_k)=P^{(k)}_{y_k,s_k}P^{(k)\Herm}_{\ts_k.\ty_k}$ for some projective matrix $P^{(k)}$ for each $k=1,2$.
\end{example}
\begin{example}
\begin{figure}\centering
\begin{tikzpicture}[nodes = {draw= none, minimum size = 0pt},
factor/.style={rectangle, minimum size=.7cm, draw},
Factor/.style={rectangle, minimum width=.7cm, minimum height=1.5cm, draw},
node distance=2cm]
\node[factor] (P) {}; \node [below=0pt of P] {$\diag(\prob_\rv{X})$};
\node[Factor] (u0) [right of= P] {}; \node [below=0pt of u0] {$\hat{U}_0$};
\node (a1) [right of= u0] {};
\node[factor] (A1) [above = -.04cm of a1] {}; \node at (A1) {$\hat{A}_1$};
\node (A1h) [below = .1cm of a1] {};
\node[Factor] (u1) [right of=  a1] {};
\node [below=0pt of u1] {$\hat{U}_1$};
\node (a2) [right of= u1] {};
\node[factor] (A2) [above = -.04cm of a2] {}; \node at (A2) {$\hat{A}_2$};
\node (A2h) [below = .1cm of a2] {};
\node[Factor] (u2) [right of= a2] {}; \node [below=0pt of u2] {$\hat{U}_2$};
\node[factor] (I) [right of = u2] {=}; \node [below=0cm of I] {$I$};

\path (P) edge[double] node[above] {$s_0$} node[below] {$\ts_0$} (u0);
\path (A1-|u0.east) edge[*-, double] node[above] {$s_1$} node[below] {$\ts_1$} (A1);
\path (A1) edge[*-, double] node[above] {$s_1'$} node[below] {$\ts_1'$} (A1-|u1.west);
\path (A2-|u1.east) edge[*-, double] node[above] {$s_2$} node[below] {$\ts_2$} (A2);
\path (A2) edge[*-, double] node[above] {$s_2'$} node[below] {$\ts_2'$} (A2-|u2.west);
\path (u2) edge[*-, double] node[above] {$s_3$} node[below] {$\ts_3$} (I);
\path (A1h-|u0.east) edge[*-, double] node[above] {$w_1$} node[below] {$\tilde{w}_1$} (A1h-|u1.west);
\path (A2h-|u1.east) edge[*-, double] node[above] {$w_2$} node[below] {$\tilde{w}_2$} (A2h-|u2.west);
\path (A1) edge node[above, pos=1] {$y_1$} ([yshift=1cm]A1);
\path (A2) edge node[above, pos=1] {$y_2$} ([yshift=1cm]A2);
\end{tikzpicture}
\caption{A quantum system with two partial measurements.}
\label{fig:DeFG_5}
\end{figure}
The DeFG in Figure~\ref{fig:DeFG_5} depicts a quantum system with two partial measurements.
Here, $\hat{A}_1$, $\hat{A}_2$ satisfy the same requirement as in Example~\ref{ex:DeFG:unitary:measurement}, and $\hat{U}_1$, $\hat{U}_2$, and $\hat{U}_3$ are functions such that
\begin{align*}
\hat{U}_1(s_1,w_1,s_0,\ts_1,\tilde{w}_1,\ts_0)
&= U^{(1)}_{(s_1,w_1),s_0} U^{(1)\Herm}_{\ts_0,(\ts_1,\tilde{w}_1)}\\
\hat{U}_2(s_2,w_2,s_1',w_1,\ts_2,\tilde{w}_2,\ts_1',\tilde{w}_1)
&= U^{(2)}_{(s_2,w_2),(s_1',w_1)}U^{(2)\Herm}_{(\ts_1',\tilde{w}_1),(\ts_2,\tilde{w}_2)}\\
\hat{U}_3(s_3,s_2',w_2,\ts_3,\ts_2',\tilde{w}_2)
&= U^{(3)}_{s_3,(s_2',w_2)}U^{(3)\Herm}_{(\ts_2',\tilde{w}_2),\ts_3}
\end{align*}
for some unitary matrices $U^{(1)}$, $U^{(2)}$, $U^{(3)}$.
Note that this DeFG contains cycles.
\end{example}
\begin{table}\centering
\begin{tabular}{|p{3.5cm}|p{3.5cm}|m{5.5cm}|}
\hline
FG Description & DeFG Description & Remarks\\
\hline
\centering\raisebox{-.5\height}{
\begin{tikzpicture}[nodes = {draw= none, minimum size = 0pt, font=\small},
factor/.style={rectangle, minimum size=.5cm, draw},
node distance=1.7cm]
\node[factor] (rho) {}; \node at (rho) {$\rho$};
\node[factor, above right = .15cm and .7cm of rho] (u) {}; \node at (u) {$U$};
\node[factor, below right = .15cm and .7cm of rho] (l) {}; \node at (l) {$U^\Herm$};
\draw[*-] (rho) |- (u);
\draw[-*] (rho) |- (l);
\draw[*-] (u) -- ([xshift=1cm]u.east);
\draw     (l) -- ([xshift=1cm]l.east);
\node[fit=(current bounding box),inner ysep=1mm,inner xsep=0]{};
\end{tikzpicture}
} &  \centering\raisebox{-.5\height}{
\begin{tikzpicture}[nodes = {draw= none, minimum size = 0pt, font=\small},
factor/.style={rectangle, minimum size=.5cm, draw},
node distance=1.2cm]
\node[factor] (rho) {}; \node at (rho) {$\rho$};
\node[factor, right of= rho] (f) {}; \node at (f) {$\hat{U}$};
\draw[*-,double] (f) -- ([xshift=1cm]f.east);
\draw[double] (f) -- (rho);
\node[fit=(current bounding box),inner ysep=1mm,inner xsep=0]{};
\end{tikzpicture}
} & $\hat{U}(s',s,\ts',\ts)=U_{s',s}U^\Herm_{\ts,\ts'}$\\
\hline
\centering\raisebox{-.5\height}{
\begin{tikzpicture}[nodes = {draw= none, minimum size = 0pt, font=\small},
factor/.style={rectangle, minimum size=.5cm, draw},
node distance=1.7cm]
\node[factor] (rho) {}; \node at (rho) {$\rho$};
\node[factor, above right = .15cm and .7cm of rho] (u) {}; \node at (u) {$E_k$};
\node[factor, below right = .15cm and .7cm of rho] (l) {}; \node at (l) {$E_k^\Herm$};
\draw[*-] (rho) |- (u);
\draw[-*] (rho) |- (l);
\draw[*-] (u) -- ([xshift=1cm]u.east);
\draw     (l) -- ([xshift=1cm]l.east);
\path (u) edge[draw] node[right] {$k$} (l);
\node[fit=(current bounding box),inner ysep=1mm,inner xsep=0]{};
\end{tikzpicture}
} & \centering\raisebox{-.5\height}{
\begin{tikzpicture}[nodes = {draw= none, minimum size = 0pt, font=\small},
factor/.style={rectangle, minimum size=.5cm, draw},
node distance=1.2cm]
\node[factor] (rho) {}; \node at (rho) {$\rho$};
\node[factor, right of= rho] (f) {}; \node at (f) {$N$};
\draw[*-,double] (f) -- ([xshift=1cm]f.east);
\draw[double] (f) -- (rho);
\node[fit=(current bounding box),inner ysep=1mm,inner xsep=0]{};
\end{tikzpicture}
} & $N(s',s,\ts',\ts)=\sum_{k}E_{s',s}E^\Herm_{\ts,\ts'}$\\
\hline
\centering\raisebox{-.5\height}{
\begin{tikzpicture}[nodes = {draw= none, minimum size = 0pt, font=\small},
factor/.style={rectangle, minimum size=.5cm, draw}]
\node[factor] (rho) {}; \node at (rho) {$\rho$};
\node[factor, above right = .25cm and .7cm of rho] (u) {}; \node at (u) {$M_y$};
\node[factor, below right = .25cm and .7cm of rho] (l) {}; \node at (l) {$M_y^\Herm$};
\draw[*-] (rho) |- (u);
\draw[-*] (rho) |- (l);
\draw[*-] (u) -- ([xshift=1cm]u.east);
\draw     (l) -- ([xshift=1cm]l.east);
\path (u) edge[draw=none] node[factor] (Y) {} (l); \node at (Y) {$I_y$};
\draw (u) -- (Y) -- (l);
\node (y) at ([xshift=.7cm,yshift=1.3cm]Y) {$y$};
\draw (Y) -| (y);
\node[fit=(current bounding box),inner ysep=1mm,inner xsep=0]{};
\end{tikzpicture}
} & \centering\raisebox{-.5\height}{
\begin{tikzpicture}[nodes = {draw= none, minimum size = 0pt, font=\small},
factor/.style={rectangle, minimum size=.5cm, draw},
node distance=1.2cm]
\node[factor] (rho) {}; \node at (rho) {$\rho$};
\node[factor, right of= rho] (f) {}; \node at (f) {$A$};
\draw[*-,double] (f) -- ([xshift=1cm]f.east);
\draw[double] (f) -- (rho);
\draw (f) -- ([yshift=1cm]f.north);
\node[fit=(current bounding box),inner ysep=1mm,inner xsep=0]{};
\end{tikzpicture}
} & $A(s',s,\ts',\ts;y) = M_y(s',s)M_y^\Herm(\ts,\ts')$ \\
\hline
\centering\raisebox{-.5\height}{
\begin{tikzpicture}[nodes = {draw= none, minimum size = 0pt, font=\small},
factor/.style={rectangle, minimum size=.5cm, draw}]
\node[factor] (rho) {}; \node at (rho) {$\rho$};
\node[factor, above right = .25cm and .7cm of rho] (u) {}; \node at (u) {$M_y$};
\node[factor, below right = .25cm and .7cm of rho] (l) {}; \node at (l) {$M_y^\Herm$};
\draw[*-] ([xshift=.1cm]rho.north) |- (u);
\draw[*-] ([xshift=-.1cm]rho.north) |- ([xshift=1cm,yshift=.5cm]u.east);
\draw[-*] ([xshift=.1cm]rho.south) |- (l);
\draw ([xshift=-.1cm]rho.south) |- ([xshift=1cm,yshift=-.5cm]l.east);
\draw[*-] (u) -- ([xshift=1cm]u.east);
\draw     (l) -- ([xshift=1cm]l.east);
\path (u) edge[draw=none] node[factor] (Y) {} (l); \node at (Y) {$I_y$};
\draw (u) -- (Y) -- (l);
\node (y) at ([xshift=.7cm,yshift=1.8cm]Y) {$y$};
\draw (Y) -| (y);
\node[fit=(current bounding box),inner ysep=1mm,inner xsep=0]{};
\end{tikzpicture}
} & \centering\raisebox{-.5\height}{
\begin{tikzpicture}[nodes = {draw= none, minimum size = 0pt, font=\small},
factor/.style={rectangle, minimum size=.5cm, draw},
node distance=1.2cm]
\node[factor, minimum height = 1cm] (rho) {}; \node at (rho) {$\rho$};
\node[factor, anchor=north, xshift=1.2cm] at (rho.north) (f) {}; \node at (f) {$A$};
\draw[*-,double] (f) -- ([xshift=1cm]f.east);
\draw[double] (f) -- (f-|rho.east);
\draw (f) -- ([yshift=1cm]f.north);
\draw[double] ([yshift=-.25cm]rho.east) -- ([xshift=2.24cm,yshift=-.25cm]rho.east);
\node[fit=(current bounding box),inner ysep=1mm,inner xsep=0]{};
\end{tikzpicture}
} & Same as above \\
\hline
\centering\raisebox{-.5\height}{
\begin{tikzpicture}[nodes = {draw= none, minimum size = 0pt, font=\small},
factor/.style={rectangle, minimum size=.5cm, draw}]
\node[factor] (rho) {}; \node at (rho) {$\rho$};
\node[factor, right = 1.2cm of rho] (I) {}; \node at (I) {$I$};
\draw[*-] (rho.north) -- ([yshift=.5cm]rho.north) -| (I.north);
\draw (I.south) |- ([yshift=-.5cm]rho.south) -- (rho.south);
\node[fit=(current bounding box),inner ysep=1mm,inner xsep=0]{};
\end{tikzpicture}
} &
\centering\raisebox{-.5\height}{
\begin{tikzpicture}[nodes = {draw= none, minimum size = 0pt, font=\small},
factor/.style={rectangle, minimum size=.5cm, draw},
node distance=1.2cm]
\node[factor] (rho) {}; \node at (rho) {$\rho$};
\node[factor, right of= rho] (f) {}; \node at (f) {$I$};
\draw[double] (f) -- (rho);
\node[fit=(current bounding box),inner ysep=1mm,inner xsep=0]{};
\end{tikzpicture}
} & - \\
\hline
\end{tabular}
\caption{Representing quantum systems using factor graphs and DeFGs.}
\label{tb:quantum:system:FGs}
\end{table}
As illustrated by the above examples, the dynamics of a quantum system (see Section~\ref{sec:quantum_postulates}) can be described by DeFGs systematically, as summarized in Table~\ref{tb:quantum:system:FGs}.
\section{Belief-Propagation Algorithms for DeFGs}
In this section, we consider the problem of computing the partition sums of DeFGs.
For acyclic cases, the problem is not so different from that on a factor graph and can be solved by a slightly modified version of the method in Section~\ref{subsec:marginal:acyclic:FGs}.
For DeFGs with cycles, we propose and analyze a generalized version of the belief-propagation algorithms.
\par
Without loss of generality, we assume all the DeFGs involved in the rest of this chapter do not have ``single edges''.
Namely, we only consider global functions in the form
\begin{equation}\label{eq:global:function:DeFG:simplified}
g(\vs,\tvs) = \prod_{a\in\mathcal{F}} f_a(\vs_{\nb{a}},\tvs_{\nb{a}}).
\end{equation}
\subsection{Computing the marginals/partition sum of an acyclic DeFG}
Similar to the methods for acyclic factor graphs in Section~\ref{subsec:marginal:acyclic:FGs}, one can also ``shrink'' an acyclic DeFG to a root factor via a sequence of ``closing-the-box'' operations starting from the leaf nodes.
The following example illustrates this idea.
\begin{example}
\begin{figure}\centering
\begin{tikzpicture}[nodes = {draw= none, minimum size = 0pt},
factor/.style={rectangle, minimum size=.7cm, draw},
Factor/.style={rectangle, minimum width=.7cm, minimum height=1.5cm, draw},
node distance=2cm]
\pgfdeclarelayer{front}
\pgfdeclarelayer{back}
\pgfsetlayers{back,main,front}
\begin{pgfonlayer}{front}
\node[factor] (A) {a};
\node[factor] (B) [below left of= A] {b};
\node[factor] (C) [below right of=A] {c};
\node[factor] (D) [below left of=B] {d};
\node[factor] (E) [below left of=C] {e};
\node[factor] (F) [below right of=C] {f};
\path (A) edge[double, thick] (B);
\path (A) edge[double, thick] (C);
\path (B) edge[double, thick] (D);
\path (C) edge[double, thick] (E);
\path (C) edge[double, thick] (F);
\end{pgfonlayer}
\begin{pgfonlayer}{main}
\path (B)--(D) coordinate [midway] (bd);
\draw[rotate=45, dashed, fill opacity=.4,draw opacity=1, fill=blue!40]
(bd) ellipse (1.6cm and .8cm);
\path (C)--(E) coordinate [midway] (ce);
\draw[rotate=45, dashed, fill opacity=.4,draw opacity=1, fill=blue!40]
(ce) ellipse (1.6cm and .8cm);
\path (E)--(F) coordinate [midway] (ef);
\draw[dashed, fill opacity=.4, draw opacity=1, fill=blue!40]
([yshift=.4cm]ef) ellipse (2.2cm and 1.6cm);
\path (A)--(D) coordinate [midway] (ad);
\path (A)--(B) coordinate [midway] (ab);
\draw[rotate=45, dashed, fill opacity=.4, draw opacity=1, fill=blue!40]
([xshift=-.1cm]ad) ellipse (2.7cm and .9cm);
\path (B)--(C) coordinate [midway] (bc);
\path (D)--(E) coordinate [midway] (de);
\draw[dashed, fill opacity=.4, draw opacity=1, fill=blue!40]
([yshift=-.5cm]bc) ellipse (4.6cm and 2.5cm);
\end{pgfonlayer}
\begin{pgfonlayer}{front}
\node[red] at ([xshift=-.2cm,yshift=.2cm]bd) {\textbf{i}};
\node[red] at ([xshift=-.2cm,yshift=.2cm]ce) {\textbf{ii}};
\node[red] at ([yshift=-.4cm]ef) {\textbf{iii}};
\node[red] at ([xshift=-.2cm,yshift=.2cm]ab) {\textbf{iv}};
\node[red] at ([yshift=-1cm]de) {\textbf{v}};
\end{pgfonlayer}
\end{tikzpicture}
\caption{Computing the partition sum of a normal \emph{acyclic} DeFG.}
\label{fig:SPA_1}
\end{figure}
By taking a sequence of ``closing-the-box'' operations for each adjacent factor, the normal DeFG in Figure~\ref{fig:SPA_1} can be ``shrunk'' to a null graph with a single local constant function.
The roman numbers indicate the sequence of the ``closing-the-box'' operations.
The constant obtained in the end is the partition sum.
\end{example}
We summarize the method above as Algorithm~\ref{alg:BP:acyclic:DeFG}.
Without loss of generality, we have assumed all the leaf vertices are from $\set{F}$, since we can always append a constant-$1$ local function to a leaf vertex from $\set{V}$ without changing the partition sum.
\begin{algorithm}
\caption{Belief-Propagation Algorithm for Acyclic DeFGs}
\label{alg:BP:acyclic:DeFG}
\begin{algorithmic}[1]
\Require{An acyclic DeFG $\left(\set{G}=(\set{V},\set{F},\set{E}\in\set{V}\times\set{F}), \mathfrak{V}=\{\set{S}_j\}_{j\in\set{V}}, \mathfrak{F}=\{f_a\}_{a\in\set{F}}\right)$ with all leaf vertices belonging to $\set{F}$, a root vertex $r\in\mathcal{F}$}
\Ensure{The partition sum $Z(\mathcal{G})\defeq\sum_{\vs,\tvs}g(\vs,\tvs)$}
\State Define the bipartite graph $G'=(\set{V}',\set{F}',\set{E}')\gets \set{G}$;
\While{$\set{F}'\neq\{r\}$}
\ForAll{$a\in\set{F}'$ being a leaf and $j$ being its parent in $\set{G}'$}
\State $m_{a\to j}(s_j,\ts_j) \gets \sum_{\vs_{\nb{a}\xk j},\tvs_{\nb{a}\xk j}} f_a(\vs_\nb{a},\tvs_\nb{a}) \cdot \prod_{k\in\nb{a}\xk{j}} m_{k\to a}(s_k,\ts_k)$;
\State $\set{F}'\gets \set{F}'\xk a$, $\set{E}'\gets \set{E}'\xk (\nb{a}\times a)$;
\Comment{Remove $a$ from $\set{G}'$.}
\EndFor
\ForAll{$j\in\set{V}'$ being a leaf and $a$ being its parent in $\set{G}'$}
\State $m_{j\to a}(s_j,\ts_j)\gets\prod_{c\in\nb{j}\xk{a}} m_{c\to j}(s_j,\ts_j)$;
\State $\set{V}'\gets \set{V}'\xk j$, $\set{E}'\gets \set{E}'\xk (j\times\nb{j})$;
\Comment{Remove $j$ from $\set{G}'$.}
\EndFor
\EndWhile
\State $Z(\set{G})\gets \sum_{\vs_\nb{r},\tvs_\nb{r}}f_r(\vs_\nb{r},\tvs_\nb{r}) \cdot \prod_{j\in\nb{r}}m_{j\to r}(s_j,\ts_j)$;
\end{algorithmic}
\end{algorithm}
\par
In analogy to Theorem~\ref{thm:BP:tree}, we have the following theorem for acyclic DeFGs.
\begin{theorem}\label{thm:BP:DeFG:tree}
Given an acyclic DeFG $\left(\set{G}=(\set{V},\set{F},\set{E}\in\set{V}\times\set{F}), \{\set{S}_j\}_{j\in\set{V}}, \{f_a\}_{a\in\set{F}}\right)$, there exists a unique set of messages $\{m_{j\to a},m_{a\to j}:\set{S}_j^2\to\Complex\}_{(j,a)\in\set{E}}$ such that
\begin{align}
\label{eq:msg:acyclic:DeFG:ja}
m_{j\to a}(s_j,\ts_j)&=\prod_{c\in\nb{j}\xk{a}} m_{c\to j}(s_j,\ts_j) \\
\label{eq:msg:acyclic:DeFG:aj}
m_{a\to j}(s_j,\ts_j)&=\sum_{\vs_{\nb{a}\xk j},\tvs_{\nb{a}\xk j}} f_a(\vs_\nb{a},\tvs_\nb{a}) \cdot \prod_{k\in\nb{a}\xk{j}} m_{k\to a}(s_k,\ts_k).
\end{align}
Moreover, in this case,
\begin{align}
\sum_{\vs_{\set{V}\xk{j}},\tvs_{\set{V}\xk{j}}}\prod_{a\in\set{F}} f_a(\vs_\nb{a},\tvs_\nb{a}) &= \prod_{c\in\nb{j}} m_{c\to j}(s_j,\ts_j) && \forall j\in\set{V},\\
\sum_{\vs_{\set{V}\xk\nb{a}},\tvs_{\set{V}\xk\nb{a}}}\prod_{\hat{a}\in\set{F}} f_{\hat{a}}(\vs_\nb{\hat{a}},\tvs_\nb{\hat{a}}) &= f_a(\vs_\nb{a},\tvs_\nb{a})\cdot\prod_{j\in\nb{a}} m_{j\to a}(s_j,\ts_j) && \forall a\in\set{F}.
\end{align}
\end{theorem}
\begin{proof}
By treating $(s_j,\ts_j)$ as a single variable for each $j$, the theorem is essentially the same as Theorem~\ref{thm:BP:tree}.
We omit the details.
\end{proof}
\begin{remark}
By Theorem~\ref{thm:DeFG:CtB}, the matrices corresponding to the messages defined in~\eqref{eq:msg:acyclic:DeFG:ja} and~\eqref{eq:msg:acyclic:DeFG:aj} are PSD.
\end{remark}
\subsection{Belief-Propagation Algorithms for DeFG and BP Fixed Points}
Similar to BP algorithms for factor graphs, we define BP algorithms\index{belief-propagation algorithm!for DeFGs} as a heuristic generalization based on the messaging-passing rules~\eqref{eq:msg:acyclic:DeFG:ja} and~\eqref{eq:msg:acyclic:DeFG:aj}.
Namely, we consider an iterative method with the updating rules
\begin{align}
\label{eq:msg:DeFG:ja}
m_{j\to a}^{(t)}(s_j,\ts_j)&\propto \prod_{c\in\nb{j}\xk{a}} m_{c\to j}^{(t)}(s_j,\ts_j), \\
\label{eq:msg:DeFG:aj}
m_{a\to j}^{(t)}(s_j,\ts_j)&\propto \sum_{\vs_{\nb{a}\xk j},\tvs_{\nb{a}\xk j}} f_a(\vs_\nb{a},\tvs_\nb{a}) \cdot \prod_{k\in\nb{a}\xk{j}} m_{k\to a}^{(t-1)}(s_k,\ts_k),
\end{align}
where the initial messages $\{m_{j\to a}^{(0)}\}_{(j,a)\in\set{E}}$ are some constant functions.
% Schedules
Same as the BP algorithms for factor graphs, the updating sequence of the messages in~\eqref{eq:msg:DeFG:ja} and~\eqref{eq:msg:DeFG:aj} (\aka schedule) can be cleverly designed to suit different scenarios.
In this thesis, we choose to focus on the synchronous schedule (\aka flooding schedule).
Algorithm~\ref{alg:BP:DeFG} lists BP algorithm for DeFGs with the flooding schedule.
\begin{algorithm}
\caption{Belief-Propagation Algorithm for DeFGs (Flooding Schedule with Timeout)}
\label{alg:BP:DeFG}
\begin{algorithmic}[1]
\Require{A DeFG $\left(\set{G}=(\set{V},\set{F},\set{E}\in\set{V}\times\set{F}), \mathfrak{V}=\{\set{S}_j\}_{j\in\set{V}}, \mathfrak{F}=\{f_a\}_{a\in\set{F}}\right)$, $\epsilon>0$}
\Ensure{Messages $\{m_{j\to a},m_{a\to j}:\set{S}_j^2\to\Complex\}_{(j,a)\in\set{E}}$, $\mathsf{FLAG}\in\{\mathrm{completed},\mathrm{timeout}\}$.}
\ForAll{$(j,a)\in\set{E}$}
\State $m_{j\to a}(s_j,\ts_j)\gets 1/\abs{\set{S}}^2$ for each $(s_j,\ts_j)\in\set{S}_j^2$;
%\State $m_{a\to j}(s_j,\ts_j)\gets 1/\abs{\set{S}}^2$ for each $(s_j,\ts_j)\in\set{S}_j^2$;
\EndFor
\State $t\gets 0$;
\Do
\State $t\gets t+1$;
\ForAll{$(j,a)\in\set{E}$}
%\State $m_{j\to a}^{(t)}(s_j,\ts_j)\defpropto\prod_{c\in\nb{j}\xk{a}} m_{c\to j}^{(t-1)}(s_j,\ts_j)$ for each $(s_j,\ts_j)\in\set{S}_j^2$;
\State $m_{a\to j}^{(t)}(s_j,\ts_j)\defpropto \sum_{\vs_{\nb{a}\xk j},\tvs_{\nb{a}\xk j}} f_a(\vs_\nb{a},\tvs_\nb{a}) \cdot \prod_{k\in\nb{a}\xk{j}} m_{k\to a}^{(t-1)}(s_k,\ts_k)$ for each $(s_j,\ts_j)\in\set{S}_j^2$;
\EndFor
\ForAll{$(j,a)\in\set{E}$}
\State $m_{j\to a}^{(t)}(s_j,\ts_j)\defpropto\prod_{c\in\nb{j}\xk{a}} m_{c\to j}^{(t)}(s_j,\ts_j)$ for each $(s_j,\ts_j)\in\set{S}_j^2$;
\EndFor
\DoWhile{$\left(\neg\mathsf{timeout}\right) \land \left( \exists(j,a)\in\set{E} \text{ s.t. }\norm{m_{j\to a}^{(t)}-m_{j\to a}^{(t-1)}}_2>\varepsilon\text{ or }\norm{m_{a\to j}^{(t)}-m_{a\to j}^{(t-1)}}_2>\varepsilon\right)$}
\Comment{$\mathsf{timeout}=\mathsf{false}$ unless the operating time exceeds a pre-selected waiting time.}
\If{$\mathrm{timeout}$}
\State{$\mathsf{FLAG}\gets\mathrm{timeout}$;}
\Else
\State{$\mathsf{FLAG}\gets\mathrm{completed}$;}
\ForAll{$(j,a)\in\set{E}$}
\State{$m_{j\to a}\gets m_{j\to a}^{(t)}$;}
\State{$m_{a\to j}\gets m_{a\to j}^{(t)}$;}
\EndFor
\EndIf
\end{algorithmic}
\end{algorithm}
\par
BP fixed points of a DeFG, defined similarly below as those of a factor graph, are of great importance for investigating the properties of the BA algorithms for DeFGs.
\begin{definition}[BP Fixed Points of a DeFG]\label{def:DeFG:BP:fixed:points} \index{BP fixed points!of DeFGs}
Applying Algorithm~\ref{alg:BP:DeFG} to a DeFG, a resulting set of messages $\{m_{j\to a},m_{a\to j}:\set{S}_j^2\to\Complex\}_{(j,a)\in\set{E}}$ is said to be a BP fixed point if
\begin{align}
\label{eq:fixed:DeFG:ja}
m_{j\to a}(s_j,\ts_j)&\propto\prod_{c\in\nb{j}\xk{a}} m_{c\to j}(s_j,\ts_j), \\
\label{eq:fixed:DeFG:aj}
m_{a\to j}(s_j,\ts_j)&\propto\sum_{\vs_{\nb{a}\xk j},\tvs_{\nb{a}\xk j}} f_a(\vs_\nb{a},\tvs_\nb{a}) \cdot \prod_{k\in\nb{a}\xk{j}} m_{k\to a}(s_k,\ts_k).
\end{align}
In this case, the set $\{m_{j\to a},m_{a\to j}\}_{(j,a)\in\set{E}}$ is also called a set of fixed-point messages.
\end{definition}
\begin{definition} \index{induced partition sum}
Given a set of normalized PSD messages $\{m_{j\to a},m_{a\to j}\}_{(j,a)\in\set{E}}$, not necessarily a BP fixed point, the \emph{induced} partition sum (\wrt the messages) is defined as
\begin{equation}
Z_{\mathsf{induced}}\left(\{m_{j\to a},m_{a\to j}\}_{(j,a)\in\set{E}}\right)=\frac{\prod_{a\in\set{F}}Z_a(\{m_{j\to a}\}_{j\in\nb{a}})\cdot\prod_{j\in\set{V}}Z_j(\{m_{a\to j}\}_{a\in\nb{j}})}{\prod_{(j,a)\in\set{E}}Z_{j,a}(m_{j\to a},m_{a\to j})},
\end{equation}
\begin{align*}
Z_a(\{m_{j\to a}\}_{j\in\nb{a}}) &\defeq \sum_{\vs_\nb{a},\tvs_\nb{a}}f_a(\vs_\nb{a},\tvs_\nb{a}) \cdot \prod_{j\in\nb{a}} m_{j\to a}(s_j,\ts_j) && \forall a\in\set{F},\\
Z_j(\{m_{a\to j}\}_{a\in\nb{j}}) &\defeq \sum_{s_j,\ts_j}\prod_{a\in\nb{j}} m_{a\to j}(s_j,\ts_j) && \forall j\in\set{V},\\
Z_{j,a}(m_{j\to a},m_{a\to j}) &\defeq \sum_{s_j,\ts_j} m_{j\to a}(s_j,\ts_j)\cdot m_{a\to j}(s_j,\ts_j) && \forall (j,a)\in\set{E}. \qedhere
\end{align*}
\end{definition}
\begin{proposition}\label{prop:DeFG:Zinduced:stationary}
The function $Z_{\mathsf{induced}}$	is real non-negative, and its stationary points correspond to BP fixed points.
\end{proposition}
\begin{proof}
It suffice to show that the set of equations
\begin{equation}\label{eq:proof:prop:DeFG:Zinduced:stationary:1}
\begin{aligned}
\left.\frac{\D}{\D h}\right\rvert_{h=0} Z_{\mathsf{induced}}(m_{c\to k}+h\cdot \eta_{c\to k}) = 0 & \quad\forall \eta_{c\to k}(s_k,\ts_k)\text{ PSD}\\
\left.\frac{\D}{\D h}\right\rvert_{h=0} Z_{\mathsf{induced}}(m_{k\to c}+h\cdot \eta_{k\to c}) = 0 & \quad\forall \eta_{k\to c}(s_k,\ts_k)\text{ PSD}
\end{aligned}
\qquad \forall (k,c)\in\set{E}
\end{equation}
is equivalent to the updating rules~\eqref{eq:fixed:DeFG:ja} and~\eqref{eq:fixed:DeFG:aj}.

First, suppose $\{m_{j\to a},m_{a\to j}\}_{(j,a)\in\set{E}}$ is a stationary point of $Z_{\mathsf{induced}}$, \ie,~\eqref{eq:proof:prop:DeFG:Zinduced:stationary:1} holds.
By definition of $Z_{\mathsf{induced}}$, one can rewrite the upper set of~\eqref{eq:proof:prop:DeFG:Zinduced:stationary:1} as
\[
\left.\frac{\D}{\D h}\right\rvert_{h=0} Z_{k,c}(m_{c\to k}+h\cdot \eta_{c\to k}) / Z_{k,c} =
\left.\frac{\D}{\D h}\right\rvert_{h=0} Z_k(m_{c\to k}+h\cdot \eta_{c\to k}) / Z_k.
\]
Substituting the definitions of $Z_k$ and $Z_{k,c}$, the above is equivalent to
\begin{equation}\label{eq:proof:prop:DeFG:Zinduced:stationary:2}
\sum_{s_k,\ts_k} m_{k\to c}(s_k,\ts_k)\cdot\eta_{c\to k}(s_k,\ts_k) = \frac{Z_{k,c}}{Z_k}\cdot \sum_{s_k,\ts_k} \tilde{m}_{k\to c}(s_k,\ts_k)\cdot\eta_{c\to k}(s_k,\ts_k),
\end{equation}
where $\tilde{m}_{k\to c}(s_k,\ts_k)\defeq\prod_{a\in\nb{k}\xk{c}}m_{a\to k}(s_k,\ts_k)$.
Since this holds for all PSD functions $\eta_{c\to k}$, linear algebra must hold that $m_{k\to c}\propto\tilde{m}_{k\to c}$, which recovers~\eqref{eq:fixed:DeFG:ja}.
Similarly, the lower set of equations of~\eqref{eq:proof:prop:DeFG:Zinduced:stationary:1} can be rewritten as
\[
\left.\frac{\D}{\D h}\right\rvert_{h=0} Z_{k,c}(m_{k\to c}+h\cdot \eta_{k\to c}) / Z_{k,c} =
\left.\frac{\D}{\D h}\right\rvert_{h=0} Z_c(m_{k\to c}+h\cdot \eta_{k\to c}) / Z_c,
\]
which is, in turn, equivalent to
\begin{equation}\label{eq:proof:prop:DeFG:Zinduced:stationary:3}
\sum_{s_k,\ts_k}m_{c\to k}(s_k,\ts_k)\cdot\eta_{k\to c}(s_k,\ts_k) =
\frac{Z_{k,c}}{Z_c}\cdot\sum_{s_k\ts_k}\tilde{m}_{c\to k}(s_k,\ts_k)\cdot\eta_{k\to c}(s_k,\ts_k),
\end{equation}
where $\tilde{m}_{c\to k}(s_k,\ts_k)\defeq\sum_{\vs_{\nb{c}\xk k},\tvs_{\nb{c}\xk k}}f_c(\vs_\nb{c},\tvs_\nb{c})\cdot\prod_{j\in\nb{c}\xk k}m_{j\to c}(s_j,\ts_j)$.
Again, since this also holds for all PSD functions $\eta_{k\to c}$, we have $m_{c\to k}\propto\tilde{m}_{c\to k}$, which recovers~\eqref{eq:fixed:DeFG:aj}.

Second, suppose $\{m_{j\to a},m_{a\to j}\}_{(j,a)\in\set{E}}$ is a BP fixed point, \ie,~\eqref{eq:fixed:DeFG:ja} and~\eqref{eq:fixed:DeFG:aj} hold.
To show~\eqref{eq:proof:prop:DeFG:Zinduced:stationary:1}, it suffices to verify~\eqref{eq:proof:prop:DeFG:Zinduced:stationary:2} and~\eqref{eq:proof:prop:DeFG:Zinduced:stationary:3}.
The latter can be shown rather straightforwardly as soon as one notices that
\begin{align*}
\frac{Z_{k,c}}{Z_k} &= \frac{\sum_{s_k,\ts_k}m_{k\to c}(s_k,\ts_k)\cdot m_{c\to k}(s_k,\ts_k)}{\sum_{s_k,\ts_k}\left(\prod_{a\in\nb{k}\xk{c}}m_{a\to k}(s_k,\ts_k)\right)\cdot m_{c\to k}(s_k,\ts_k)}
= \frac{m_{k\to c}(s_k,\ts_k)}{\prod_{a\in\nb{k}\xk{c}}m_{a\to k}(s_k,\ts_k)}\\
\frac{Z_{k,c}}{Z_c} &= \frac{\sum_{s_k,\ts_k}m_{c\to k}(s_k,\ts_k)\cdot m_{k\to c}(s_k,\ts_k)}{\sum_{s_k,\ts_k}\left(\sum_{\vs_{\nb{c}\xk k},\tvs_{\nb{c}\xk k}}f_c(\vs_\nb{c},\tvs_\nb{c})\cdot\prod_{j\in\nb{c}\xk k}m_{j\to c}(s_j,\ts_j)\right)\cdot m_{k\to c}(s_k,\ts_k)}\\
&= \frac{m_{c\to k}(s_k,\ts_k)}{\sum_{\vs_{\nb{c}\xk k},\tvs_{\nb{c}\xk k}}f_c(\vs_\nb{c},\tvs_\nb{c})\cdot\prod_{j\in\nb{c}\xk k}m_{j\to c}(s_j,\ts_j)}
\end{align*}
for all $s_k$, $\ts_k$ since $m_{k\to c}$ is proportional to $\prod_{a\in\nb{k}\xk{c}}m_{a\to k}$, and $m_{c\to k}$ is proportional to $\sum_{\vs_{\nb{c}\xk k},\tvs_{\nb{c}\xk k}}f_c\cdot\prod_{j\in\nb{c}\xk k}m_{j\to c}$.
\end{proof}
One \emph{must} note that $Z_{\mathsf{induced}}$ is conceptually different from $Z_{\mathsf{B}}$ for factor graphs.
In particular, $Z_{\mathsf{induced}}$ is a function of messages, instead of some local beliefs or marginals.
More importantly, in the classical case, $Z_{\mathsf{induced}}=Z_{\mathsf{B}}$ for messages corresponding to the belief minimizing $\bethe$.
However, although $\bethe$ can be generalized to DeFGs by analytical continuation, it is not clear how to define a similar version of $Z_{\mathsf{B}}$ based on the minimum of $\bethe$ while maintaining the connections to BP algorithms.
Thus, it is currently unclear how $Z_{\mathsf{induced}}$ is related to the partition sum $Z$ (for general DeFGs).
Nevertheless, for acyclic DeFGs, we still have the following corollary.
\begin{corollary}
For an acyclic DeFG $\set{G}$, its BP fixed point is unique.
Also, in this case, $Z_{\mathsf{induced}}$ has only one stationary point, and at that point, $Z_{\mathsf{induced}}=Z(\set{G})$.
\end{corollary}
\begin{proof}
This is a direct result of Theorem~\ref{thm:BP:DeFG:tree} and Proposition~\ref{prop:DeFG:Zinduced:stationary}.
\end{proof}
\subsection{Holographic Transformations and Loop Calculus for DeFGs}
In this section, we consider the generalization of the holographic transformation and the loop calculus expansion from factor graphs~\cite{mori2015loop, chernyak2007loop} to DeFGs.

The generalization of the holographic transformation for DeFG is rather straightforward.
The following theorem is a direct generalization of Theorem~\ref{thm:holant}.
\begin{theorem}[Holant Theorem for DeFGs] \label{thm:DeFG:holant} \index{Holant theorem}
Let $\set{G}=(\set{V},\set{F},\set{E})$ be a DeFG representing the factorization $g(\vs,\tvs) = \prod_{a\in\mathcal{F}} f_a(\vs_{\nb{a}},\tvs_{\nb{a}})$.
Given the Hermitian functions\footnote{Here, a function $f:\bigtimes_{k}\set{X}_k^2\to\Complex$ is said to be Hermitian if $f(x_1,\ldots,x_k;\tx_1,\ldots,\tx_k)=\conj{f(\tx_1,\ldots,\tx_k;x_1,\ldots,x_k)}$ for all $x_1,\ldots,x_k,\tx_1,\ldots,\tx_k$.} $\{\hat{\phi}_{j,a}:\set{T}_{j,a}^2\times\set{S}_j^2\to\Complex\}_{(j,a)\in\set{E}}$ and $\{\phi_{j,a}:\set{S}_j^2\times\set{T}_{j,a}^2\to\Complex\}_{(i,a)\in\set{E}}$ such that (where the sets $\set{T}_{j,a}$ and $\set{S}_j$ are finite)
\begin{equation}\label{eq:holographic:requirement:DeFG}
\sum_{t,\tit} \phi_{j,a}(s,\ts;t,\tit)\cdot\hat{\phi}_{j,a}(t,\tit;s',\ts') = \delta_{s,s'}\cdot\delta_{\ts,\ts'},
\end{equation}
the partition sum $Z(\set{G})$ can be expressed as
\begin{equation}
Z(\set{G}) \defeq \sum_{\vs,\tvs} \prod_{a\in\set{F}} f_a(\vs_\nb{a},\tvs_\nb{a})
= \sum_{\vt,\tvt} \prod_{a\in\set{F}} \hat{f}_a(\vt_{\nb{a},a},\tvt_{\nb{a},a}) \prod_{j\in\set{V}} \hat{h}_j(\vt_{j,\nb{j}},\tvt_{i,\nb{j}}),
\end{equation}
\begin{align}
\label{eq:DeFG:holographic:1}
\hat{f}_a(\vt_{\nb{a},a},\tvt_{\nb{a},a}) &\defeq \sum_{\vs_\nb{a},\tvs_\nb{a}} f_a(\vs_\nb{a},\tvs_\nb{a}) \cdot \prod_{j\in\nb{a}} \hat{\phi}_{j,a}(t_{j,a},\tit_{j,a};s_j,\ts_j),\\
\label{eq:DeFG:holographic:2}
\hat{h}_j(\vt_{j,\nb{j}},\tvt_{i,\nb{j}}) &\defeq \sum_{s_j,\ts_j} \prod_{a\in\nb{j}} \phi_{j,a}(s_j,\ts_j;t_{j,a},\tit_{j,a}).
\end{align}
\end{theorem}
The idea behind the above theorem is the same as that of Theorem~\ref{thm:holant}, and we omit the proof.
Similar to the case of factor graphs, the holographic transform\index{holographic transformation!of DeFGs} of $\set{G}$ (\wrt $\{\hat{\phi}_{j,a},\phi_{j,a}\}_{(j,a)}$) is defined to be the DeFG $\hat{\set{G}}=(\set{E},\set{F}\cup\set{V},\setdef{(e,e_1),(e,e_2)}{e\in\set{E}})$ representing the factorization
\begin{equation}
\hat{g}(\vt,\tvt) = \prod_{a\in\set{F}} \hat{f}_a(\vt_{\nb{a},a},\tvt_{\nb{a},a}) \prod_{j\in\set{V}} \hat{h}_j(\vt_{j,\nb{j}},\tvt_{i,\nb{j}}).
\end{equation}
\par
Following the idea of the method of loop calculus (recall Section~\ref{subsec:FG:LoopCalculus}), we consider a specific holographic transform such that
\begin{align}
\label{eq:DeFG:lc:assumption:1}
\hat{f}_a(\vt_{\nb{a},a},\tvt_{\nb{a},a})
&= 0,\text{ if } \wt(\vt_{\nb{a},a}\tensor\tvt_{\nb{a},a}) = 1,\\
\label{eq:DeFG:lc:assumption:2}
\hat{h}_j(\vt_{j,\nb{j}},\tvt_{i,\nb{j}})
&= 0,\text{ if } \wt(\vt_{j,\nb{j}}\tensor\tvt_{i,\nb{j}}) = 1,
\end{align}
where we have assumed that each alphabet $\set{T}_{j,a}$ contains an elements labeled as $0$.\footnote{Note that $\wt(\vx_1^n\tensor\tvx_1^n)\defeq\sum_{i=1}^n 1_{(x_i,\tx_i)\neq(0,0)}$, where $1_\text{true}=1$ and $1_\text{false}=0$.}
In this case, the support of $\hat{g}$ is limited to those $(t_{j,a},\tit_{j,a})_{(j,a)\in\set{E}}$ such that the edges $(j,a)$ corresponding to $(t_{j,a},\tit_{j,a})\neq\vect{0}$ form a \emph{generalized loop} (see~\eqref{eq:def:extended:loops}).
Substituting~\eqref{eq:DeFG:holographic:1} and~\eqref{eq:DeFG:holographic:2} into~\eqref{eq:DeFG:lc:assumption:1} and~\eqref{eq:DeFG:lc:assumption:2}, respectively, we can rewrite the latter as
\begin{align}
\label{eq:DeFG:lc:assumption:3}
\sum_{s_j,\ts_j}\left(\sum_{\vs_{\nb{a}\xk j},\tvs_{\nb{a}\xk j}} f_a(\vs_\nb{a},\tvs_\nb{a}) \cdot \prod_{k\in\nb{a}\xk j} \hat{\phi}_{k,a}(0,0;s_k,\ts_k)\right) \cdot \hat{\phi}_{j,a}(t_{j,a},\tit_{j,a};s_j,\ts_j) &= 0 \\
\label{eq:DeFG:lc:assumption:4}
\sum_{s_j,\ts_j}\left(\prod_{c\in\nb{j}\xk a} \phi_{j,c}(s_j,\ts_j;0,0)\right)\cdot\phi_{j,a}(s_j,\ts_j;t_{j,a},\tit_{j,a}) &= 0
\end{align}
for each $(j,a)\in\set{E}$ and $(t_{j,a},\tit_{j,a})\neq\vect{0}$.
Since all functions involved in~\eqref{eq:DeFG:lc:assumption:3} and~\eqref{eq:DeFG:lc:assumption:4} are Hermitian, the \LHS of these equations are nothing more than the Frobenius inner product between matrices.
In other words,
\begin{align}
\label{eq:DeFG:lc:assumption:3a}
\left[\sum_{\vs_{\nb{a}\xk j},\tvs_{\nb{a}\xk j}}\!\! f_a(\vs_\nb{a},\tvs_\nb{a}) \cdot\!\! \prod_{k\in\nb{a}\xk j} \hat{\phi}_{k,a}(0,0;s_k,\ts_k)\right]_{s_j,\ts_j}\!\!
&\perp \bigg[\hat{\phi}_{j,a}(t_{j,a},\tit_{j,a};s_j,\ts_j)\bigg]_{s_j,\ts_j}\\
\label{eq:DeFG:lc:assumption:4a}
\left[\prod_{c\in\nb{j}\xk a} \phi_{j,c}(s_j,\ts_j;0,0)\right]_{s_j,\ts_j}\!\!
&\perp \bigg[\phi_{j,a}(s_j,\ts_j;t_{j,a},\tit_{j,a})\bigg]_{s_j,\ts_j}
\end{align}
for each $(j,a)\in\set{E}$ and $(t_{j,a},\tit_{j,a})\neq\vect{0}$.
Considering~\eqref{eq:holographic:requirement:DeFG}, we have
\begin{align}
\label{eq:DeFG:lc:assumption:5}
\phi_{j,a}(\cdot,\cdot;0,0) &\propto
\left[\sum_{\vs_{\nb{a}\xk j},\tvs_{\nb{a}\xk j}}\!\! f_a(\vs_\nb{a},\tvs_\nb{a}) \cdot\!\! \prod_{k\in\nb{a}\xk j} \hat{\phi}_{k,a}(0,0;s_k,\ts_k)\right]_{s_j,\ts_j},\\
\label{eq:DeFG:lc:assumption:6}
\hat{\phi}_{j,a}(0,0;\cdot,\cdot) &\propto
\left[\prod_{c\in\nb{j}\xk a} \phi_{j,c}(s_j,\ts_j;0,0)\right]_{s_j,\ts_j}.
\end{align}
Compare above with Definition~\ref{def:DeFG:BP:fixed:points}.
Eq~\eqref{eq:DeFG:lc:assumption:5} and~\eqref{eq:DeFG:lc:assumption:6} are equivalent to the existence of some fixed-point messages $\{m_{j\to a}, m_{a\to j}\}_{(i,a)}$ such that
\begin{align}
\label{eq:DeFG:lc:assumption:7}
\phi_{j,a}(s_j,\ts_j\cdot;0,0) &= c_{j,a}\cdot m_{a\to j}(s_j,\ts_j)\\
\label{eq:DeFG:lc:assumption:8}
\hat{\phi}_{j,a}(0,0;s_j,\ts_j) &= \hat{c}_{j,a}\cdot m_{j\to a}(s_j,\ts_j)
\end{align}
for some constants $c_{j,a}$, $\hat{c}_{j,a}$ such that $c_{j,a}\cdot \hat{c}_{j,a}=Z_{j,a}^{-1}(m_{j\to a},m_{a\to j})$ for each $(j,a)\in\set{E}$.
Retracing the steps above, given any BP fixed point $\{m_{j\to a}, m_{a\to j}\}_{(j,a)\in\set{E}}$ of the DeFG, one can construct a holographic transform satisfying~\eqref{eq:DeFG:lc:assumption:7} and~\eqref{eq:DeFG:lc:assumption:8}; and thus  satisfying~\eqref{eq:DeFG:lc:assumption:1} and~\eqref{eq:DeFG:lc:assumption:2}.
Additionally, in such a case, for each $a\in\set{F}$ and $j\in\set{V}$, we have
\begin{equation}
\hat{f}_a(\vect{0},\vect{0}) = Z_a \prod_{j\in\nb{a}} \hat{c}_{j,a},\quad
\hat{h}_j(\vect{0},\vect{0}) = Z_j \prod_{c\in\nb{j}} c_{j,c},
\end{equation}
and thus,
\begin{equation}
Z_{\mathsf{induced}}(\{m_{j\to a},m_{a\to j}\}_{(j,a)\in\set{E}})=
\prod_{a\in\set{F}} \hat{f}_a(\vect{0},\vect{0}) \cdot \prod_{j\in\set{V}} \hat{h}_j(\vect{0},\vect{0}).
\end{equation}

\begin{theorem}[Loop Calculus Expansion for DeFGs] \index{loop calculus!of DeFGs}
Consider a DeFG representing the factorization $g(\vs,\tvs) = \prod_{a\in\mathcal{F}} f_a(\vs_{\nb{a}},\tvs_{\nb{a}})$.
Let $\{m_{j\to a}, m_{a\to j}\}_{(i,a)}$ be a set of fixed-point messages.
Then, it holds that
\begin{equation}\label{eq:DeFG:lc}
Z(\set{G})=Z_{\mathsf{induced}}(\{m_{j\to a},m_{a\to j}\}_{(j,a)\in\set{E}}) \cdot \sum_{E\in\mathfrak{L}(\set{E})}\mathcal{K}(E),
\end{equation}
where the set of \emph{generalized loops} $\mathfrak{L}(\set{E})$ has been defined in~\eqref{eq:def:extended:loops} and where $\mathcal{K}\left(E\right)$ is some function of $E$ such that $\mathcal{K}(\emptyset)=1$.
\end{theorem}
\begin{proof}
Consider a holographic transform \wrt $\{\hat{\phi}_{j,a},\phi_{j,a}\}_{(j,a)}$ as established throughout~\eqref{eq:DeFG:lc:assumption:1} to~\eqref{eq:DeFG:lc:assumption:8}.
Under such a setup,
\begin{fleqn}\begin{equation*}
Z(\set{G}) = \sum_{(\vt,\tvt)\in\support(\hat{g})} \prod_{a\in\set{F}} \hat{f}_a(\vt_{\nb{a},a},\tvt_{\nb{a},a}) \prod_{j\in\set{V}} \hat{h}_j(\vt_{j,\nb{j}},\tvt_{i,\nb{j}}),
\end{equation*}\end{fleqn}
\begin{fleqn}\begin{equation*}\phantom{Z(\set{G})}
= Z_{\mathsf{induced}} \cdot \sum_{(\vt,\tvt)\in\support(\hat{g})} \prod_{a\in\set{F}} \frac{\hat{f}_a(\vt_{\nb{a},a},\tvt_{\nb{a},a})}{\hat{f}_a(\vect{0},\vect{0})} \prod_{j\in\set{V}} \frac{\hat{h}_j(\vt_{j,\nb{j}},\tvt_{i,\nb{j}})}{\hat{h}_j(\vect{0},\vect{0})},
\end{equation*}\end{fleqn}
\begin{fleqn}\begin{equation*}\phantom{Z(\set{G})}
= Z_{\mathsf{induced}} \cdot \sum_{(\vt,\tvt)\in\support(\hat{g})}
\begin{aligned}[t]
&\prod_{a\in\set{F}} \left[\sum_{\vs_\nb{a},\tvs_\nb{a}}b_a(\vs_\nb{a},\tvs_\nb{a})\cdot\prod_{j\in\nb{a}}\frac{\hat{\phi}_{j,a}(t_{j,a},\tit_{j,a};s_j,\ts_j)}{\hat{\phi}_{j,a}(0,0;s_j,\ts_j)}\right]\cdot\\
&\prod_{j\in\set{V}} \left[\sum_{s_j,\ts_j}b_j(s_j,\ts_j)\cdot\prod_{a\in\nb{j}}\frac{\phi_{j,a}(s_j,\ts_j;t_{j,a},\tit_{j,a})}{\phi_{j,a}(s_j,\ts_j;0,0)}\right],
\end{aligned}
\end{equation*}\end{fleqn}
\begin{fleqn}\begin{equation*}\phantom{Z(\set{G})}
= Z_{\mathsf{induced}} \cdot \sum_{E\in\mathfrak{L}(\set{E})} \sum_{(\vt_E,\tvt_E)\neq\vect{0}}
\begin{aligned}[t]
&\prod_{a\in\set{F}} \left[\sum_{\vs_\nb{a},\tvs_\nb{a}}b_a(\vs_\nb{a},\tvs_\nb{a})\cdot\prod_{j\in\nb{a}:\:(j,a)\in E}\frac{\hat{\phi}_{j,a}(t_{j,a},\tit_{j,a};s_j,\ts_j)}{\hat{\phi}_{j,a}(0,0;s_j,\ts_j)}\right]\cdot\\
&\prod_{j\in\set{V}} \left[\sum_{s_j,\ts_j}b_j(s_j,\ts_j)\cdot\prod_{a\in\nb{j}:\:(j,a)\in E}\frac{\phi_{j,a}(s_j,\ts_j;t_{j,a},\tit_{j,a})}{\phi_{j,a}(s_j,\ts_j;0,0)}\right],
\end{aligned}
\end{equation*}\end{fleqn}
\begin{align}
b_a(\vs_\nb{a},\tvs_\nb{a}) &\defeq \frac{1}{Z_a}\cdot f_a(\vs_\nb{a},\tvs_\nb{a})\cdot \prod_{j\in\nb{a}} m_{j \to a} (s_j,\ts_j),\\
b_j(s_j\ts_j) &\defeq \frac{1}{Z_j}\cdot \prod_{a\in\nb{j}} m_{a\to j}(s_j,\ts_j).
\end{align}
Finally, by letting
\begin{equation}\label{eq:lc:DeFG:K}
\begin{aligned}
\mathcal{K}(E)\defeq \sum_{(\vt_E,\tvt_E)\neq\vect{0}}
&\prod_{a\in\set{F}} \left[\sum_{\vs_\nb{a},\tvs_\nb{a}}b_a(\vs_\nb{a},\tvs_\nb{a})\cdot\prod_{j\in\nb{a}:\:(j,a)\in E}\frac{\hat{\phi}_{j,a}(t_{j,a},\tit_{j,a};s_j,\ts_j)}{\hat{\phi}_{j,a}(0,0;s_j,\ts_j)}\right]\cdot\\
&\prod_{j\in\set{V}} \left[\sum_{s_j,\ts_j}b_j(s_j,\ts_j)\cdot\prod_{a\in\nb{j}:\:(j,a)\in E}\frac{\phi_{j,a}(s_j,\ts_j;t_{j,a},\tit_{j,a})}{\phi_{j,a}(s_j,\ts_j;0,0)}\right],
\end{aligned}
\end{equation}
Eq.~\eqref{eq:DeFG:lc} can be justified.
\end{proof}
%Note that the above theorem does not provide an expansion of $\mathcal{K}(E)$ as in Theorem~\ref{thm:loop:calculus}.
Unfortunately, even for the simplest case where $\set{T}_{j,a}$ is binary for each $(j,a)\in\set{E}$,~\eqref{eq:lc:DeFG:K} is pretty complicated.
However, the theorem does \emph{suggest} that $Z_{\mathsf{induced}}$ at a BP fixed point for DeFGs with a relatively smaller number of cycles tends to be closer to the partition sum.
\section{Numerical Examples}
In this section, we discuss various examples of DeFGs.
In particular, we compare the induced partition sum $Z_{\mathsf{induced}}$ with the exact partition sum $Z$.
(The DeFGs in this section have a modest size so that the exact partition sums are tractable.)
Moreover, for the first example, we also make some analytical statements.
\par
\begin{example}\label{numerical:ex:DeFG:1}
\begin{figure}
\begin{subfigure}[c]{0.4\columnwidth}\centering
\begin{tikzpicture}[nodes = {draw= none, minimum size = 0pt},
factor/.style={rectangle, minimum size=1cm, draw},
node distance=3cm]
\node[factor] (f1) {}; \node[right=0pt of f1] {$f_1$};
\node[factor, left of = f1] (f2) {}; \node[left=0pt of f2] {$f_2$};
\node[factor, below of = f2] (f3) {}; \node[left=0pt of f3] {$f_3$};
\node[factor, right of = f3] (f0) {}; \node[right=0pt of f0] {$f_0$};
\path (f0) edge[double] node[left]{$s_1$} node[right]{$\ts_1$} (f1);
\path (f1) edge[double] node[above]{$s_2$} node[below]{$\ts_2$} (f2);
\path (f2) edge[double] node[left]{$s_3$} node[right]{$\ts_3$} (f3);
\path (f3) edge[double] node[above]{$s_0$} node[below]{$\ts_0$} (f0);
\end{tikzpicture}
\caption{DeFG in Example~\ref{numerical:ex:DeFG:1}.}
\label{fig:numerical:ex:DeFG:1:a}
\end{subfigure}
\begin{subfigure}[c]{0.6\columnwidth}\centering
\begin{tikzpicture}[nodes = {draw=none, minimum size = 0pt, inner sep = 0pt, outer sep = 0pt}]
\node (plot) {\includegraphics[width=6cm]{1155001913-cao_michael_xuan-202104-phd-Figure_DeFG_Numerical_Example_1.png}};
\node (o) at (plot.south west) {};
\node (xend) at (plot.south east) {};
\node (yend) at (plot.north west) {};
\path (o) edge[draw=none]
node[anchor=north, yshift=-15pt] {$Z$}
node[pos=0, anchor=north, yshift=-2pt, font=\scriptsize] {$10^{-12}$}
node[pos=.3333, anchor=north, yshift=-2pt, font=\scriptsize] {$10^{-6}$}
node[pos=.6667, anchor=north, yshift=-2pt, font=\scriptsize] {$10^{0}$}
node[pos=1, anchor=north, yshift=-2pt, font=\scriptsize] {$10^{6}$}
\path (o) edge[draw=none]
node[anchor=south, yshift=25pt, sloped] {$Z_{\mathsf{induced}}$}
node[pos=0, anchor=east, xshift=-2pt, font=\scriptsize] {$10^{-12}$}
node[pos=.3333, anchor=east, xshift=-2pt, font=\scriptsize] {$10^{-6}$}
node[pos=.6667, anchor=east, xshift=-2pt, font=\scriptsize] {$10^{0}$}
node[pos=1, anchor=east, xshift=-2pt, font=\scriptsize] {$10^{6}$}
\draw[red,dashed] (o) -- (plot.north east);
\end{tikzpicture}
\caption{Numerical demonstration in Example~\ref{numerical:ex:DeFG:1}.}
\label{fig:numerical:ex:DeFG:1:b}
\end{subfigure}
\caption{Plots for Example~\ref{numerical:ex:DeFG:1}.}
\label{fig:numerical:ex:DeFG:1}
\end{figure}
Consider a normal DeFG whose topology is an $n$-cycle ($n>1$) and where all variables take on values in the same finite alphabet $\set{S}$.
(Figure~\ref{fig:numerical:ex:DeFG:1:a} shows such a DeFG for $n=4$.)
Let $f$ be a complex-valued PD matrix of size $\size{\set{S}}^2\times\size{\set{S}}^2$ with its $((s_0,s_1),(\ts_0,\ts_1))$-th  entries being $f(s_0,s_1;\ts_0,\ts_1)$.
For $i\in\{0,1,\ldots,n-1\}$, we define the local function $f_i$ to be $f_i(s_i,s_{i+1};\ts_i,\ts_{i+1})\defeq f(s_i,s_{i+1};\ts_i,\ts_{i+1})$.
(All indices are modulo $n$.)
\par
To proceed, it is convenient to define the complex-valued matrix $F$ of size $\size{\set{S}}^2\times\size{\set{S}}^2$ with its $((s_0,\ts_0),(s_1,\ts_1))$-th entries being $f(s_0,s_1;\ts_0,\ts_1)$.
\par
For $i\in\{0,1,\ldots,n-1\}$, let $m^{(t)}_{i\to i+1}(s_{i+1},\ts_{i+1})$ and $m^{(t)}_{i\to i-1}(s_i,\ts_i)$ be the belief-propagation messages from $f_i$ to $f_{i+1}$ and $f_{i-1}$ at time index $t$, respectively.
\begin{align}
\label{eq:numerical:ex:DeFG:1:1}
m^{(t)}_{i\to i+1}(s_{i+1},\ts_{i+1}) &\propto \sum_{s_i,\ts_i} m^{(t-1)}_{i-1\to i}(s_i,\ts_i) \cdot F_{(s_i,\ts_i),(s_{i+1},\ts_{i+1})}, \\
\label{eq:numerical:ex:DeFG:1:2}
m^{(t)}_{i\to i-1}(s_i,\ts_i) &\propto \sum_{s_{i+1},\ts_{i+1}} F_{(s_i,\ts_i),(s_{i+1},\ts_{i+1})} \cdot m^{(t)}_{i+1\to i}(s_{i+1},\ts_{i+1}).
\end{align}
We assume $m^{(0)}_{i\to i+1}(s_{i+1},\ts_{i+1})\defeq\delta_{s_{i+1},\ts_{i+1}}$ and $m^{(0)}_{i\to i-1}(s_i,\ts_i)\defeq\delta_{s_i,\ts_i}$ for each $i\in\{0,1,\ldots,n-1\}$.
\par
Due to the properties of $F$ (which are induced from that of $f$), the mappings specified in~\eqref{eq:numerical:ex:DeFG:1:1} and~\eqref{eq:numerical:ex:DeFG:1:2} are completely positive.
Using generalizations of Perron--Frobenius theory (see~\cite{evans1977spectral, schrader2000perron}), one can make the following statements:
\begin{itemize}
\item For each $i$, the messages $m^{(t)}_{i\to i+1}$ converge to a PD matrix as $t\to\infty$.
\item For each $i$, the messages $m^{(t)}_{i\to i-1}$ converge to a PD matrix as $t\to\infty$.
\item The eigenvalue of $F$ with the largest absolute value is real and is unique. Denote it by $\lambda_0$.
\item When the messages converge, the induced partition sum $Z_{\mathsf{induced}} = \lambda_0^n$.
\end{itemize}
Compare this result with the exact partition sum, which is
\begin{equation}
Z = \sum_{k=1}^{\size{\set{S}}^2-1} \lambda_k^n = \lambda_0^n \cdot \left( 1 +\sum_{k=1}^{\size{\set{S}}^2-1} \left(\frac{\lambda_k}{\lambda_0}\right)^n\right),
\end{equation}
where $\lambda_0,\ldots,\lambda_{\size{\set{S}}^2-1}$ are the eigenvalues of $F$.
We see that the smaller the ratios $(\lambda_k/\lambda_0)^n$ for each $k$ are, the better the approximation is.
\par
For $n=4$ and $\size{\set{S}}=2$, Figure~\ref{fig:numerical:ex:DeFG:1:b} plots a million instances of the values of $Z$ and $Z_{\mathsf{induced}}$ \wrt the randomly generated matrices $F=U\cdot D\cdot U^\Herm$, where the unitary matrix $U$ is randomly generated according to the Haar measure and where $D$ is a diagonal matrix with each of its diagonal entries drawn from the square of the standard normal distribution in an {i.i.d.}~fashion.
We see that, very often, the ratio $Z_{\mathsf{induced}}/Z$ is rather close to $1$.
\end{example}
\begin{example}\label{numerical:ex:DeFG:2}
\begin{figure}
\begin{subfigure}[c]{0.4\columnwidth}\centering
\begin{tikzpicture}[nodes = {draw= none, minimum size = 0pt},
factor/.style={rectangle, minimum size=1cm, draw},
node distance=3cm]
\node[factor] (f1) {}; \node[right=0pt of f1] {$f_1$};
\node[factor, left of = f1] (f2) {}; \node[left=0pt of f2] {$f_2$};
\node[factor, below of = f2] (f3) {}; \node[left=0pt of f3] {$f_3$};
\node[factor, right of = f3] (f0) {}; \node[right=0pt of f0] {$f_0$};
\path (f0) edge[double] node[left]{$s_1$} node[right]{$\ts_1$} (f1);
\path (f1) edge[double] node[above]{$s_2$} node[below]{$\ts_2$} (f2);
\path (f2) edge[double] node[left]{$s_3$} node[right]{$\ts_3$} (f3);
\path (f3) edge[double] node[above]{$s_0$} node[below]{$\ts_0$} (f0);
\path (f2) edge[double] node[above right=-5pt]{$s_4$} node[below left=-5pt]{$\ts_4$} (f0);
\end{tikzpicture}
\caption{DeFG in Example~\ref{numerical:ex:DeFG:2}.}
\label{fig:numerical:ex:DeFG:2:a}
\end{subfigure}
\begin{subfigure}[c]{0.6\columnwidth}\centering
\begin{tikzpicture}[nodes = {draw=none, minimum size = 0pt, inner sep = 0pt, outer sep = 0pt}]
\node (plot) {\includegraphics[width=6cm]{1155001913-cao_michael_xuan-202104-phd-Figure_DeFG_Numerical_Example_2.png}};
\node (o) at (plot.south west) {};
\node (xend) at (plot.south east) {};
\node (yend) at (plot.north west) {};
\path (o) edge[draw=none]
node[anchor=north, yshift=-15pt] {$Z$}
node[pos=0, anchor=north, yshift=-2pt, font=\scriptsize] {$10^{-4}$}
node[pos=.5, anchor=north, yshift=-2pt, font=\scriptsize] {$10^{0}$}
node[pos=1, anchor=north, yshift=-2pt, font=\scriptsize] {$10^{4}$}
\path (o) edge[draw=none]
node[anchor=south, yshift=25pt, sloped] {$Z_{\mathsf{induced}}$}
node[pos=0, anchor=east, xshift=-2pt, font=\scriptsize] {$10^{-4}$}
node[pos=.5, anchor=east, xshift=-2pt, font=\scriptsize] {$10^{0}$}
node[pos=1, anchor=east, xshift=-2pt, font=\scriptsize] {$10^{4}$}
\draw[red,dashed] (o) -- (plot.north east);
\end{tikzpicture}
\caption{Numerical demonstration in Example~\ref{numerical:ex:DeFG:2}.}
\label{fig:numerical:ex:DeFG:2:b}
\end{subfigure}
\caption{Plots for Example~\ref{numerical:ex:DeFG:2}.}
\label{fig:numerical:ex:DeFG:2}
\end{figure}
Consider the DeFG in Figure~\ref{fig:numerical:ex:DeFG:2:a}.
For $\size{\set{S}}=2$, Figure~\ref{fig:numerical:ex:DeFG:2:b} plots a million instances of the values of $Z$ and $Z_{\mathsf{induced}}$ \wrt randomly generated local functions.
In contrast to Example~\ref{numerical:ex:DeFG:1}, where all local functions were the same for every instantiation, in this example, all local functions are generated independently.
We observe that the ratio $Z_{\mathsf{induced}}/Z$ is reasonably close to~$1$ but typically larger than~$1$.
\end{example}
\begin{example}\label{numerical:ex:DeFG:3}
\begin{figure}
\begin{minipage}{0.4\columnwidth}
\begin{subfigure}[c]{\linewidth}\centering
\begin{tikzpicture}[nodes = {draw= none, minimum size = 0pt},
factor/.style={rectangle, minimum size=.5cm, draw}]
\node[factor] (f) {}; \node at (f) {$f_{i,j}$};
\node[factor, below left = .2cm and 1.2cm of f] (fL) {};
\node[left=0pt of fL] {$f_i^L$};
\node[yshift=-.9cm] (L1) at (f.west) {};
\node[yshift=-1.5cm] (L2) at (f.west) {};
\node[factor, above right = .2cm and 1.5cm of f] (fR) {};
\node[right=0pt of fR] {$f_j^R$};
\node[yshift=.9cm] (R1) at (f.east) {};
\node[yshift=1.5cm] (R2) at (f.east) {};
\path (fL) edge node[above]{$x_{i,j}^{L}$} (f);
\path (fL) edge[draw=none] coordinate[midway] (Lm1) (L1);
\draw (fL) -- (Lm1); \draw[dashed] (Lm1) -- (L1);
\path (fL) edge[draw=none] coordinate[midway] (Lm2) (L2);
\draw (fL) -- (Lm2); \draw[dashed] (Lm2) -- (L2);
\path (fR) edge node[below]{$x_{i,j}^{R}$} (f);
\path (fR) edge[draw=none] coordinate[midway] (Rm1) (R1);
\draw (fR) -- (Rm1); \draw[dashed] (Rm1) -- (R1);
\path (fR) edge[draw=none] coordinate[midway] (Rm2) (R2);
\draw (fR) -- (Rm2); \draw[dashed] (Rm2) -- (R2);
\end{tikzpicture}
\caption{FG in Example~\ref{numerical:ex:DeFG:3}.}
\label{fig:numerical:ex:DeFG:3:a}
\end{subfigure}
\begin{subfigure}[c]{\linewidth}\centering
\begin{tikzpicture}[nodes = {draw= none, minimum size = 0pt},
factor/.style={rectangle, minimum size=.5cm, draw}]
\node[factor] (f) {}; \node at (f) {$f_{i,j}$};
\node[factor, below left = .2cm and 1.2cm of f] (fL) {};
\node[left=0pt of fL] {$f_i^L$};
\node[yshift=-.9cm] (L1) at (f.west) {};
\node[yshift=-1.5cm] (L2) at (f.west) {};
\node[factor, above right = .2cm and 1.5cm of f] (fR) {};
\node[right=0pt of fR] {$f_j^R$};
\node[yshift=.9cm] (R1) at (f.east) {};
\node[yshift=1.5cm] (R2) at (f.east) {};
\path (fL) edge[draw=none] coordinate[midway] (Lm1) (L1);
\draw[double] (fL) -- (Lm1); \draw[dashed,double] (Lm1) -- (L1);
\path (fL) edge[draw=none] coordinate[midway] (Lm2) (L2);
\draw[double] (fL) -- (Lm2); \draw[dashed,double] (Lm2) -- (L2);
\path (fR) edge[draw=none] coordinate[midway] (Rm1) (R1);
\draw[double] (fR) -- (Rm1); \draw[dashed,double] (Rm1) -- (R1);
\path (fR) edge[draw=none] coordinate[midway] (Rm2) (R2);
\draw[double] (fR) -- (Rm2); \draw[dashed,double] (Rm2) -- (R2);
\path (fL) edge[double] node[above,pos=.2]{$s_{i,j}^{L}$}
node[below,pos=.8]{$\ts_{i,j}^{L}$} (f);
\path (fR) edge[double] node[above,pos=.8]{$s_{i,j}^{R}$}
node[below,pos=.2]{$\ts_{i,j}^{R}$} (f);
\end{tikzpicture}
\caption{DeFG in Example~\ref{numerical:ex:DeFG:3}.}
\label{fig:numerical:ex:DeFG:3:b}
\end{subfigure}
\end{minipage}
\begin{minipage}{0.6\columnwidth}
\begin{subfigure}[c]{\linewidth}\centering
\begin{tikzpicture}[nodes = {draw=none, minimum size = 0pt, inner sep = 0pt, outer sep = 0pt}]
\node (plot) {\includegraphics[width=6cm]{1155001913-cao_michael_xuan-202104-phd-Figure_DeFG_Numerical_Example_3.png}};
\node (o) at (plot.south west) {};
\node (xend) at (plot.south east) {};
\node (yend) at (plot.north west) {};
\path (o) edge[draw=none]
node[anchor=north, yshift=-15pt] {$Z$}
node[pos=0, anchor=north, yshift=-2pt, font=\scriptsize] {$10^{0}$}
node[pos=.3333, anchor=north, yshift=-2pt, font=\scriptsize] {$10^{2}$}
node[pos=.6667, anchor=north, yshift=-2pt, font=\scriptsize] {$10^{4}$}
node[pos=1, anchor=north, yshift=-2pt, font=\scriptsize] {$10^{6}$}
\path (o) edge[draw=none]
node[anchor=south, yshift=25pt, sloped] {$Z_{\mathsf{induced}}$}
node[pos=0, anchor=east, xshift=-2pt, font=\scriptsize] {$10^{0}$}
node[pos=.3333, anchor=east, xshift=-2pt, font=\scriptsize] {$10^{2}$}
node[pos=.6667, anchor=east, xshift=-2pt, font=\scriptsize] {$10^{4}$}
node[pos=1, anchor=east, xshift=-2pt, font=\scriptsize] {$10^{6}$}
\draw[red,dashed] (o) -- (plot.north east);
\end{tikzpicture}
\caption{Numerical demonstration in Example~\ref{numerical:ex:DeFG:3}.}
\label{fig:numerical:ex:DeFG:3:c}
\end{subfigure}
\end{minipage}
\caption{Plots for Example~\ref{numerical:ex:DeFG:3}.}
\label{fig:numerical:ex:DeFG:3}
\end{figure}
Let $\boldsymbol{\theta}$ be a complex-valued matrix of size $n\times n$ with its $(i,j)$-th entries being $\theta_{i,j}$.
The permanent~\cite{minc1984permanents} of $\boldsymbol{\theta}$ is defined to be $\perm(\boldsymbol{\theta})\defeq\sum_{\sigma}\prod_{i=1}^n \theta_{i,\sigma(i)}$, where the summation is over all $n!$ permutations of the set $\{1,\ldots,n\}$.
Ryser's algorithm, one of the most efficient algorithms for computing $\perm(\boldsymbol{\theta})$ for general matrices $\boldsymbol{\theta}$ exactly, requires $\Theta(n\cdot 2^n)$ arithmetic operations~\cite{ryser1963combinatorial}, and so the exact computation of the permanent is intractable, even for moderate values of $n$.
(Note that even the computation of the permanent of matrices containing only zeros and ones is \#P-complete~\cite{valiant1979complexity}.)
\par
One can formulate an NFG whose partition sum equals $\perm(\boldsymbol{\theta})$ (see, \eg,~\cite[Figure~1]{vontobel2013bethe}).
That factor graph is a complete bipartite graph with $n$ factor vertices on the left and $n$ factor vertices on the right.
Here, Figure~\ref{fig:numerical:ex:DeFG:3:a} shows a slightly modified version of that NFG.
All variables take values in the set $\set{X}=\{0,1\}$.
Moreover, for each $i$, the function $f_i^L$ is defined to be
\begin{equation}
f_i^L(\{x_{i,j}^L\}_{j=1}^{n}) \defeq \begin{cases}
1 & \text{exactly one of }\{x_{i,j}^L\}_{j=1}^{n}\text{ equals }1 \\
0 & \text{otherwise}\end{cases}
\end{equation}
for each $j$, the function $f_j^R$ is defined analogously; and for each $(i,j)$, the function $f_{i,j}$ is defined to be
\begin{equation}
f_{i,j}(x_{i,j}^L,x_{i,j}^R) \defeq \delta_{x_{i,j}^L,x_{i,j}^R} \cdot
\begin{cases}
\theta_{i,j} & \text{ if }x_{i,j}^L=1\\
1 & \text{ if }x_{i,j}^L=0
\end{cases}.
\end{equation}
\par
In this example, we consider the following rather natural generalization to the DeFG in Figure~\ref{fig:numerical:ex:DeFG:3:b}.
Assume that for each $(i,j)$, $\tilde{\boldsymbol{\theta}}_{i,j}$ is a PSD matrix of size $2\times 2$ with its $(k,\ell)$-th entries being $\tilde{\theta}_{i,j}(k,\ell)$.
With this, for each $i$, the function $\tilde{f}_i^L$ is defined to be
\begin{equation}
\tilde{f}_i^L(\{s_{i,j}^L,\ts_{i,j}^L\}_{j=1}^{n}) \defeq
f_i^L(\{s_{i,j}^L\}_{j=1}^{n})\cdot f_i^L(\{\ts_{i,j}^L\}_{j=1}^{n})
\end{equation}
for each $j$, the function $\tilde{f}_j^R$ is defined analogously; and for each $(i,j)$, the function $\tilde{f}_{i,j}$ is defined to be
\begin{equation}
\tilde{f}_{i,j}(s_{i,j}^L,s_{i,j}^R;\ts_{i,j}^L,\ts_{i,j}^R)\defeq \delta_{s_{i,j}^L,s_{i,j}^R}\cdot\delta_{\ts_{i,j}^L,\ts_{i,j}^R} \cdot\tilde{\theta}_{i,j}(s_{i,j}^L,\ts_{i,j}^L).
\end{equation}
(One can easily verify that these local functions satisfy the requirement of a DeFG.)
Finally, let $\tilde{Z}$ be the partition sum of this DeFG.
\par
This DeFG definition has the following two important special cases:
\begin{itemize}
\item If $\tilde{\boldsymbol{\theta}}_{i,j}=\left(\begin{smallmatrix} 1 & 0 \\ 0 & \theta_{i,j} \end{smallmatrix}\right)$ for each $(i,j)$, then $\tilde{Z} = \perm(\boldsymbol{\theta})$.
\item If $\tilde{\boldsymbol{\theta}}_{i,j}=\left(\begin{smallmatrix} 1 \\ \theta_{i,j} \end{smallmatrix}\right) \cdot \left(\begin{smallmatrix} 1 & \overline{\theta_{i,j}} \end{smallmatrix}\right) = \left(\begin{smallmatrix} 1 & \overline{\theta_{i,j}} \\ \theta_{i,j} & \abs{\theta_{i,j}}^2 \end{smallmatrix}\right)$ for each $(i,j)$, then $\tilde{Z} = \perm(\boldsymbol{\theta}) \cdot \perm(\conj{\boldsymbol{\theta}}) = \abs{\perm(\boldsymbol{\theta})}^2$, where $\conj{\boldsymbol{\theta}}$ denotes the matrix whose entries are the complex-conjugate values of the entries of $\boldsymbol{\theta}$.
(Note that such partition sums are of interest in quantum information processing~\cite{aaronson2013computational}, where $\boldsymbol{\theta}$ are certain types of square matrices over the complex numbers.
We refer to\cite{aaronson2013computational} for details.)
\end{itemize}
\par
In our simulations, we considered the following setup.
Namely, for every $(i,j)\in\{1,\ldots,n\}^2$, we independently generate $\tilde{\boldsymbol{\theta}}_{i,j}$ as follows:
$\tilde{\theta}_{i,j}(0,0)\defeq 1$;
$\tilde{\theta}_{i,j}(1,0)$ is picked uniformly from the unit circle in the complex plane;
$\tilde{\theta}_{i,j}(0,1) \defeq \conj{\tilde{\theta}_{i,j}(1,0)}$;
$\tilde{\theta}_{i,j}(1,1)$ is picked uniformly (and independently of the other entries) from the real line interval $[1.10, 11.10]$.
Figure~\ref{fig:numerical:ex:DeFG:3:c} plots $5000$ instances of the values of
$Z_{\mathsf{induced}}$ and $Z$ for the case when $n$ is $5$.
We observe that the ratio $Z_{\mathsf{induced}}/ Z$ is concentrated around a value smaller than $1$.
\end{example}
% Chapter 3 Quantum Factor Graphs***********************************************
\chapter{Quantum Factor Graphs}\label{chapter:QFGs}
In this chapter, we consider a generalization of factor graphs known as quantum factor graphs\index{quantum factor graph} (QFGs)~\cite{Leifer08}. % proposed in~\cite{Leifer08} ?
This graphical model is a direct generalization of the bifactor networks proposed in the same paper, in which they considered generalized ``factorizations'' of positive operators like
\begin{equation}\label{eq:QFG:global}
\rho \defeq \bigstar_{a \in \set{F}}\rho_a = \exp\left(\sum_{a\in\set{F}}\log{\rho_a}\right),
\end{equation}
where, for each $a\in\set{F}$, $\rho_a$ is some positive operators and where $\star$ is some associative and commutative binary operator on PSD matrices (see~\eqref{eq:def:star} and~\eqref{eq:def:star:2}).
In this case, the generalized partition sum is defined to be
\begin{equation}\label{eq:QFG:partition}
Z(\set{G})\defeq\tr(\rho) = \tr\left(\exp\left(\sum_{a\in\set{F}}\log{\rho_a}\right)\right).
\end{equation}
Notice that the (classical) factor graphs are a special case of QFGs where all the involved local operators $\{\rho_a\}_{a\in\set{F}}$ are diagonal.
In~\cite{Leifer08}, Leifer and Poulin also proposed and studied a generalized belief-propagation algorithm for bifactor networks.

In our study, we are interested in the scenarios without commutativity constraints as those in~\cite{Leifer08}.
In such cases, many vital expressions that hold precisely for factor graphs only hold approximately for QFGs, provided the local operators are chosen randomly according to some distributions.
We give some analytical and numerical characterizations of these approximations.
In particular, we study how the ``closing-the-box'' operations and Bethe's approximation can be generalized to QFGs in an approximate manner.
\section{The $\star$-Product and Quantum Factor Graphs (QFGs)}
This section reviews the definition of the $\star$-product and quantum factor graphs.
We discuss various properties of the $\star$-product, particularly the (lack of) distributivity of $\star$ over (partial) trace operations.
\subsection{Definition of the $\star$-product and QFGs}
As already mentioned in~\eqref{eq:QFG:global}, for QFGs, we consider the factorization of some positive operator into the $\star$-product~\cite{warmuth2005Bayes},\footnote{Note that in~\cite{warmuth2005Bayes} this operation is denoted by $\odot$. However, in this thesis, $\odot$ denotes the Hadamard product.} of some local operators.
Given (strictly) PD operators $\rho,\sigma\in\StPositiveOp(\hilbert)$, their $\star$-product is defined to be
\begin{equation}\label{eq:def:star}\index{$\star$-product}
\rho\star\sigma\defeq \exp(\log{\rho}+\log{\sigma}),
\end{equation}
where $\exp$ and $\log$ stand for matrix exponential and logarithm, respectively.
For PSD operators, we consider the Lie product formula\index{Lie product formula}~\cite{bhatia2013Matrix} and rewrite~\eqref{eq:def:star} as
\begin{equation}\label{eq:def:star:2}
\rho\star\sigma = \lim_{n\to \infty} \left(\rho^{\frac{1}{n}}\sigma^{\frac{1}{n}}\right)^n.
\end{equation}
Using a continuity argument, one can generalize the $\star$-product to PSD operators $\rho,\sigma\in \PositiveOp(\hilbert)$.
(For the proof of the convergence of the \RHS of~\eqref{eq:def:star:2} for PSD operators $\rho$ and $\sigma$, see, \eg,~\cite{bhatia2013Matrix} and~\cite[Theorem 1.2]{simon2005functional}.)
The $\star$-product is associative and commutative, \ie,
\begin{align}
\rho_1 \star \rho_2 &= \rho_2 \star \rho_1
&&\forall \rho_1, \rho_2 \in \PositiveOp(\hilbert),\\
(\rho_1 \star \rho_2) \star \rho_3 &= \rho_1 \star (\rho_2 \star \rho_3)
&&\forall \rho_1, \rho_2, \rho_3 \in \PositiveOp(\hilbert).
\end{align}
\par
As a convention, given $\rho$ and $\sigma$ acting on different Hilbert spaces, we treat the expression $\rho\star\sigma$ as the $\star$-product of the \emph{embedded} operators of $\rho$ and $\sigma$ on some smallest \emph{common} Hilbert space.
For example, given $\rho_\system{AB}\in\PositiveOp(\hilbert_\system{A}\tensor\hilbert_\system{B})$ and $\rho_\system{BC}\in\PositiveOp(\hilbert_\system{B}\tensor\hilbert_\system{C})$, the convention
\begin{equation}\label{eq:blowupConvention}
\rho_\system{AB} \star \rho_\system{BC} \defeq (\rho_\system{AB} \tensor I_\system{C}) \star (I_\system{A} \tensor \rho_\system{BC})
\end{equation}
holds, where $I_\system{C}$ and $I_\system{A}$ are the identity operators on $\hilbert_\system{A}$ and $\hilbert_\system{C}$, respectively;
and $\rho_\system{AB} \star \rho_\system{BC}$ is an operator acting on $\hilbert_\system{A} \tensor \hilbert_\system{B} \tensor \hilbert_\system{C}$.
This convention also applies to the expression $\bigstar_{a \in \set{F}}\rho_a$, where some equations similar to~\eqref{eq:blowupConvention} are applied recursively.
As a reminder, note that $\log(\rho\tensor I)\equiv\log{\rho}\tensor I$.
\begin{definition}[Quantum Factor Graph~\cite{Leifer08}] \label{def:QFG} \index{quantum factor graph}
A quantum factor graph (QFG) is a bipartite graph $\set{G}=(\set{V},\set{F},\set{E}\in\set{V}\times\set{F})$ associated with a variable set $\mathfrak{V}$ and a factor set $\mathfrak{F}$, where
\begin{itemize}
\item $\mathfrak{V}=\{\hilbert_i\}_{i\in\set{V}}$ is indexed by $\set{V}$, and each element of $\mathfrak{V}$ is a Hilbert space;
\item $\mathfrak{F}=\{\rho_a\}_{a\in\set{F}}$ is indexed by $\set{F}$, and $\rho_a \in \PositiveOp(\Tensor_{i\in\nb{a}}\hilbert_i)$ for each $a\in\set{F}$.
\end{itemize}
The operator $\rho \defeq \bigstar_{a \in \set{F}}\rho_a$ is called the \emph{global operator} of $\set{G}$, and in this case, $\set{G}$ is also said to be representing the factorization $\rho = \bigstar_{a \in \set{F}}\rho_a$.
Similar to factor graphs, a QFG is said to be \emph{normal} if the degree of any vertex in $\set{V}$ is at most 2.
\end{definition}
Note that the global operator $\rho$ is always a PSD operator on $\Tensor_{i\in \set{V}} \hilbert_i$ (i.e., $\rho\in\PositiveOp{\Tensor_{i\in \set{V}} \hilbert_i}$).
Moreover, if all the local operators are \emph{strictly} positive, \ie, $\rho_a \in \StPositiveOp(\hilbert_a)$ for each $a$, so is $\rho$.
\begin{remark}
Similar to NFGs, in a normal QFG, we redraw the vertices in $\set{V}$ as edges (see \RHS of Figure~\ref{fig:QFG:1} and Figure~\ref{fig:QFG:2}).
\end{remark}
\begin{example}\label{ex:QFG:1}
\begin{figure}\centering
\begin{subfigure}[c]{0.49\textwidth}\centering
\begin{tikzpicture}[node distance=2.2cm,
var/.style={circle, minimum size=.5cm, draw},
factor/.style={rectangle, minimum size=.7cm, draw}]
\node[var] (A) {}; \node at (A) {$\system{A}$};
\node[factor, left=1cm of A] (rho) {$\rho_\system{A}$};
\node[factor, above right = .8660cm and .5cm of A] (sigma) {$\sigma_\system{A}$};
\node[factor, below right = .8660cm and .5cm of A] (tau) {$\tau_\system{A}$};
\draw[line width=2pt] (A) -- (rho);
\draw[line width=2pt] (A) -- (sigma);
\draw[line width=2pt] (A) -- (tau);
\end{tikzpicture}
\end{subfigure}
\begin{subfigure}[c]{0.49\textwidth}\centering
\begin{tikzpicture}[node distance=2.2cm,
var/.style={circle, minimum size=.5cm, draw},
factor/.style={rectangle, minimum size=.7cm, draw}]
\node[factor] (pi) {$\pi$};
\node[factor, left=1cm of pi] (rho) {$\rho_\system{A}$};
\node[factor, above right = .8660cm and .5cm of pi] (sigma) {$\sigma_\system{B}$};
\node[factor, below right = .8660cm and .5cm of pi] (tau) {$\tau_\system{C}$};
\path (pi) edge[line width=2pt] node[above]{$\system{A}$} (rho);
\path (pi) edge[line width=2pt] node[below, anchor=north west]{$\system{B}$} (sigma);
\path (pi) edge[line width=2pt] node[below, anchor=north east]{$\system{C}$} (tau);
\end{tikzpicture}
\end{subfigure}
\caption{QFG in Example~\ref{ex:QFG:1}.}
\label{fig:QFG:1}
\end{figure}
The \LHS of Figure~\ref{fig:QFG:1} depicts a QFG with a single variable vertex and three factor vertices.
Here, all local factors $\rho_\system{A}$, $\sigma_\system{A}$, and $\tau_\system{A}$ act on the same Hilbert space $\hilbert_\system{A}$, and the global operator is given by $\rho_\set{G}\defeq\rho_\system{A}\star\sigma_\system{A}\star\tau_\system{A}$.
On the \RHS of Figure~\ref{fig:QFG:1}, we have a normal QFG, which is equivalent to the QFG on the left.
Here, the new-introduced variable vertices $\system{B}$ and $\system{C}$ are associated with the Hilbert spaces $\hilbert_\system{B}$ and $\hilbert_\system{C}$, each being of the same dimension as that of $\hilbert_\system{A}$.
The local operators $\sigma_\system{B}$ and $\tau_\system{C}$ are the same as $\sigma_\system{A}$ and $\tau_\system{A}$, except that they act on $\hilbert_\system{B}$ and $\hilbert_\system{C}$, respectively.
The new-introduced operator $\pi$ acts on $\hilbert_\system{A}\tensor\hilbert_\system{B}\tensor\hilbert_\system{C}$ and is defined as
\begin{equation}\label{eq:QFG:convert:normal}
\pi\defeq\exp\left(\log{\sigma_\system{A}}\!\tensor\! I_\system{BC} + \log{\tau_\system{A}}\!\tensor\! I_\system{BC} - I_\system{A}\!\tensor\!\log{\sigma_\system{B}}\!\tensor\! I_\system{C} - I_\system{AB}\!\tensor\!\log{\tau_\system{C}}\right).
\end{equation}
In this case, the global operator of the QFG on the \RHS in Figure~\ref{fig:QFG:1} can be expressed as
\begin{align*}
\tilde{\rho} &\defeq \rho_\system{A} \star \sigma_\system{B} \star \tau_\system{C}\star \pi\\
&=\exp\left(\log{\rho_\system{A}}\tensor I_\system{BC} + \log{\sigma_\system{A}}\tensor I_\system{BC} + \log{\tau_\system{A}}\tensor I_\system{BC}\right)\\
&=\rho_\set{G}\tensor I_\system{BC}. \qedhere
\end{align*}
\end{example}
\begin{remark}
As illustrated in Example~\ref{ex:QFG:1}, any QFG can be converted into an equivalent normal QFG by introducing additional local operators.
However, in contrast to factor graphs or DeFGs, the additional local operator introduced depends on the original local operators (see, \eg,~\eqref{eq:QFG:convert:normal}).
In the remaining part of this chapter, we will focus solely on normal QFGs.
\end{remark}
\par
\subsection{Approximated Distributivity of the $\star$-Product over (Partial) Trace}
For a factor graph or a DeFG, the ``closing-the-box'' operation is a handy visualization of the distributive law of addition over multiplication.
However, for a QFG, the $\star$-product does not distribute over the partial trace operations in general, as illustrated in the example below.
\begin{example}\label{ex:QFG:2}
\begin{figure}\centering
\begin{subfigure}[c]{0.49\textwidth}\centering
\begin{tikzpicture}[node distance=2.2cm,
var/.style={circle, minimum size=.5cm, draw},
factor/.style={rectangle, minimum size=.7cm, draw}]
\node[factor] (a) {$\rho_a$};
\node[factor] (b)[right of=a] {$\rho_b$};
\node[factor] (c)[right of=b] {$\rho_c$};
\path (a) edge[draw=none] node[var] (A) {} (b); \node at (A) {$\system{A}$};
\path (b) edge[draw=none] node[var] (B) {} (c); \node at (B) {$\system{B}$};
\draw[line width=2pt] (a) -- (A) -- (b) -- (B) -- (c);
\draw[dashed] ([xshift=-.5cm,yshift=.5cm]b) rectangle ([xshift=.5cm,yshift=-.5cm]c);
\draw[dashed] ([xshift=-.5cm,yshift=.7cm]a) rectangle ([xshift=.7cm,yshift=-.7cm]c);
\end{tikzpicture}
\end{subfigure}
\begin{subfigure}[c]{0.49\textwidth}\centering
\begin{tikzpicture}[node distance=2.2cm,
factor/.style={rectangle, minimum size=.7cm, draw}]
\node[factor] (a) {$\rho_a$};
\node[factor] (b)[right of=a] {$\rho_b$};
\node[factor] (c)[right of=b] {$\rho_c$};
\draw[line width=2pt] (a) -- (b) -- (c);
\draw[dashed] ([xshift=-.5cm,yshift=.5cm]b) rectangle ([xshift=.5cm,yshift=-.5cm]c);
\draw[dashed] ([xshift=-.5cm,yshift=.7cm]a) rectangle ([xshift=.7cm,yshift=-.7cm]c);
\end{tikzpicture}
\end{subfigure}
\caption{QFG in Example~\ref{ex:QFG:2}.}
\label{fig:QFG:2}
\end{figure}
Consider the QFG in Figure~\ref{fig:QFG:1} with the variable vertices $\set{V} =\{\system{A},\system{B}\}$, the factor vertices $\set{F} = \{a,b,c\}$, and the local operators $\rho_a\in\PositiveOp(\hilbert_\system{A})$, $\rho_b\in \PositiveOp(\hilbert_\system{A}\tensor\hilbert_\system{B})$, and $\rho_c\in\PositiveOp(\hilbert_\system{B})$.
This QFG represents the factorization $\rho=\rho_a\star\rho_b\star\rho_c$, and the partition sum is $Z = \tr(\rho_a\star\rho_b\star\rho_c)$.
However, in general, we cannot compute $Z$ \emph{in steps}, \ie,
\begin{equation}\label{eq:notwork}
\tr(\rho_a\star\rho_b\star\rho_c)
\not\equiv \tr_\system{A}\left(\rho_a\star\tr_\system{B}(\rho_b\star\rho_c)\right).
\end{equation}
In particular, let $\rho_a=\frac{1}{2}\left[\begin{smallmatrix}+1 & -1\\ -1 & +1 \end{smallmatrix}\right]$, $\rho_b=\diag([0,1,1,0])$, and $\rho_c=\left[\begin{smallmatrix} 1 & 0 \\ 0 & 1 \end{smallmatrix}\right]$, then $\tr_\system{A}(\tr_\system{B}(\rho_a\star\rho_b\star\rho_c))=0$, but $\tr_\system{A}(\rho_a\star\tr_\system{B}(\rho_b\star\rho_c))=1$.
(Here, we have used~\eqref{eq:def:star:2}.)
\end{example}
\par
However, there do exist situations where $\tr_\system{A}(\rho_a\star\tr_\system{B}(\rho_b\star\rho_c))$ \emph{approximates} $\tr_\system{A}(\tr_\system{B}(\rho_a\star\rho_b\star\rho_c))$ reasonably well.
This subsection aims to understand when this happens so that an approximated notion of the ``closing-the-box'' operations can be salvaged.
\begin{lemma}\label{lem:partialTraceBound}
Given $\rho_a\in\StPositiveOp(\hilbert_\system{A})$, $\rho_b\in \StPositiveOp(\hilbert_\system{A}\tensor\hilbert_\system{B})$, and $\rho_c\in\PositiveOp(\hilbert_\system{B})$, we have
\begin{equation}\label{eq:partialTraceBound}
S\left(\kappa(\rho_a)\right)^{-1} \leqslant
\frac{\tr_\system{A}(\rho_a\star\tr_\system{B}(\rho_b\star\rho_c))}
\leqslant S\left(\kappa(\rho_a)\right),
\end{equation}
where $\kappa(\rho_a)\geqslant 1$ is the condition number of the operator $\rho_a$, and $S(\cdot)$ is the Specht ratio function defined as
\begin{equation} \label{eq:Specht} \index{Specht ratio function}
S(r) \defeq \frac{(r-1)\cdot r^{\frac{1}{r-1}}}{e\cdot \log{r}} \quad \forall r>0.
\end{equation}
\end{lemma}
\begin{proof}
Consider the Golden--Thompson inequality\index{Golden--Thompson inequality} and its reverse~\cite{bourin2007Reverse}, \ie,
\begin{equation}\label{eq:Golden-Thompson}
\tr\left(e^{V+W}\right) \leqslant \tr\left(e^V \cdot e^W\right)
\leqslant S(\alpha)\cdot \tr\left(e^{V+W}\right),
\end{equation}
where $V$ and $W$ are Hermitian operators, and $\alpha$ is the condition number of $e^V$.
For arbitrary (strict) PD operators $\rho$ and $\sigma$, since both $\log{\rho}$ and $\log{\sigma}$ are Hermitian, by substituting $V=\log{\rho}$ and $W=\log{\sigma}$ into~\eqref{eq:Golden-Thompson}, we have
\begin{equation}\label{eq:Golden-Thompson-log}
\tr(\rho\star\sigma) \leqslant \tr(\rho\cdot\sigma)
\leqslant S(\kappa(\rho))\cdot\tr(\rho\star\sigma) \quad \forall \rho,\sigma>0.
\end{equation}
\par
To prove the first inequality in~\eqref{eq:partialTraceBound}, we have
\begin{align*}
\tr(\rho_a\star\rho_b\star\rho_c)
&\overset{\text{(a)}}{\leqslant} \tr(\rho_a\cdot(\rho_b\star\rho_c))
= \tr_\system{A}(\rho_a\cdot\tr_\system{B}(\rho_b\star\rho_c))\\
&\overset{\text{(b)}}{\leqslant} S(\kappa(\rho_a))\cdot \tr_\system{A}(\rho_a\star\tr_\system{B}(\rho_b\star\rho_c))
= S(\kappa(\rho_a))\cdot \tr(\rho_a\star\rho_b\star\rho_c),
\end{align*}
where we have applied the first and second inequalities in~\eqref{eq:Golden-Thompson-log} to step~(a) and step~(b), respectively.
Similarly, to show the second inequality in~\eqref{eq:partialTraceBound}, we have
\begin{align*}
\tr_\system{A}(\rho_a \star \tr_\system{B}(\rho_b\star\rho_c))
&\overset{\text{(a)}}{\leqslant} \tr_\system{A}(\rho_a \cdot \tr_\system{B}(\rho_b\star\rho_c))
= \tr(\rho_a \cdot (\rho_b\star\rho_c))\\
&\overset{\text{(b)}}{\leqslant} S(\kappa(\rho_a)) \cdot \tr(\rho_a\star(\rho_b\star\rho_c))
= S(\kappa(\rho_a))\cdot \tr(\rho_a\star\rho_b\star\rho_c),
\end{align*}
where, again, we have used~\eqref{eq:Golden-Thompson-log} in step~(a) and step~(b).
\end{proof}
Lemma~\ref{lem:partialTraceBound} indicates that $\tr_\system{A}(\rho_a\star\tr_\system{B}(\rho_b\star\rho_c))$ is expected to approximate $\tr(\rho_a\star\rho_b\star\rho_c)$ reasonably well when $\rho_a$ or $\rho_b\star\rho_c$ is proportionally close to the identity matrix.
This fact is further elaborated in the following theorem, where $\rho_a$ and $\rho_b\star\rho_c$ are close to the identity matrix in a linear fashion, \ie, $\rho_a=I+tX$ and $\rho_b\star\rho_c=I+tY$ for some Hermitian matrices $X$ and $Y$, and some real number $t$ in a small neighborhood of zero.
Another approach to study such approximations is to consider $\rho_a=e^{tX}$ and $\rho_b\star\rho_c=e^{tY}$, again, for some Hermitian matrices $X$ and $Y$, and some real number $t$ in a small neighborhood of zero.
We present the second approach in Appendix~\ref{app:exp:approx}.
\begin{theorem}\label{thm:approx:distri}
Consider finite-dimensional Hilbert spaces $\hilbert_\system{A}$ and $\hilbert_\system{B}$.
Given $X \in \HermitianOp(\hilbert_\system{A})$ and $Y\in\HermitianOp(\hilbert_\system{A} \tensor \hilbert_\system{B})$, it holds that
\begin{equation}\label{eq:approx:distri}
\tr\left((I+t X)\star(I+t Y)\right) = \tr_\system{A} \left( (I+t X) \star \tr_\system{B}(I+t Y) \right) + O(t^4),
\end{equation}
where the real number $t$ is in a neighborhood of $0$ such that $I+tX$ and $I+tY$ are always positive definite.
In other words, $\tr_\system{A} \left( (I+t X) \star \tr_\system{B}(I+t Y) \right)$ approximates $\tr\left((I+t X)\star(I+t Y)\right)$ when $t$ is small, and the error is of fourth order in $t$.
\end{theorem}
\begin{proof}
The theorem is proven using the Taylor series expansion.
Recall that, for a Hermitian matrix $V$ and a positive definite matrix $W$ with spectral radius less than $1$, we have
\begin{align*}
\exp{V} &= I + V + \frac{1}{2} V^2 + \frac{1}{3!} V^3 + \cdots + \frac{1}{n!} V^n + \cdots,\\
\log{(I+W)} &= B - \frac{1}{2} W^2 + \frac{1}{3} W^3 - \cdots + \frac{(-1)^{n-1}}{n} W^n + \cdots.
\end{align*}
To simplify the proof, we introduce the \emph{normalized} (partial) trace functions
\[
\overline{\tr}(\rho) \defeq \frac{\tr(\rho)}{\tr(I)},\qquad
\overline{\tr}_\system{A}(\rho) \defeq \frac{\tr_\system{A}(\rho)}{\tr_\system{A}(I)}.
\]
Using the above notations, we rewrite~\eqref{eq:approx:distri} as
\[
\overline{\tr}\left((I+t X)\star(I+t Y)\right) = \overline{\tr}_\system{A} \left( (I+t X) \star \overline{\tr}_\system{B}(I+t Y) \right) + O(t^4).
\]
Let $\tilde{X}\defeq X\tensor I \in \HermitianOp(\hilbert_\system{A} \tensor \hilbert_\system{B})$, and consider the Taylor series expansion of the terms (without $O(t^4)$) on both sides of the above equation:
\begin{align}
\label{eq:taylor:LHS:ADT}
\text{LHS} &= \begin{aligned}[t]
1 &+ t\cdot \overline{\tr}(\tilde{X}+Y) + t^2\cdot\frac{\overline{\tr}(\tilde{X}Y + Y\tilde{X})}{2}\\
&+ t^4 \cdot \frac{\overline{\tr}\left( \tilde{X}Y\tilde{X}Y - \tilde{X}^2Y^2 \right)}{12} + O(t^5),
\end{aligned}\\
\label{eq:taylor:RHS:ADT}
\text{RHS} &= \begin{aligned}[t]
1 &+ t\cdot \overline{\tr}_\system{A}( X + \overline{\tr}_\system{B}(Y) ) + t^2 \cdot \frac{\overline{\tr}_\system{A} \left( X\overline{\tr}_\system{B}(Y) + \overline{\tr}_\system{B} (Y)X \right)}{2}\\
&+ t^4 \cdot \frac{\overline{\tr}_\system{A} \left( X\overline{\tr}_\system{B}(Y)X\overline{\tr}_\system{B}(Y) - X^2\overline{\tr}_\system{B}(Y)^2 \right)}{12}+O(t^5).
\end{aligned}
\end{align}
Note that $\overline{\tr}_\system{B}(\tilde{X}\cdot Z) = X\cdot\overline{\tr}_\system{B}(Z)$ for any operator $Z\in \HermitianOp(\hilbert_\system{A}\tensor\hilbert_\system{B})$.
Thus, one can easily check that~\eqref{eq:taylor:LHS:ADT} and~\eqref{eq:taylor:RHS:ADT} agree up to $t^3$.
(Note that the coefficients of $t^3$ are both $0$ for~\eqref{eq:taylor:LHS:ADT}
In particular, we have
\[
\overline{\tr}\left((I+t X)\star(I+t Y)\right) =
\begin{aligned}[t]
&\overline{\tr}_\system{A} \left( (I+t X) \star \overline{\tr}_\system{B}(I+t Y) \right)\\
&\hspace{-60pt}+ \frac{\overline{\tr}_\system{A}\left( X \cdot [\overline{\tr}_2(Y),X]\cdot \overline{\tr}_2(Y) \right) - \overline{\tr}\left( \tilde{X} \cdot[\tilde{X},Y] \cdot Y \right)}{12} \cdot t^4 + O(t^5),
\end{aligned}
\]
where $[V,W]\defeq VW-WV$ for matrices $V,W$.
\end{proof}
Using the same method, we have the following approximation as well.
\begin{proposition}\label{prop:approx:distri}
Under the same setup as in Theorem~\ref{thm:approx:distri}, it holds that
\begin{equation}\label{eq:approx:distri:prop}
\tr_\system{B}\left((I+t X)\star(I+t Y)\right) = (I+t X) \star \tr_\system{B}(I+t Y) + O(t^3).
\end{equation}
\end{proposition}
\begin{proof}
We use the same method as that in the proof of Theorem~\ref{thm:approx:distri}.
In particular, we rewrite~\eqref{eq:approx:distri:prop} as
\[
\overline{\tr}_\system{B}\left((I+t X)\star(I+t Y)\right) = (I+t X) \star \overline{\tr}_\system{B}(I+t Y) + O(t^3)
\]
and expand each side (without $O(t^3)$) of the above equation as
\begin{align}
\label{eq:taylor:LHS:ADP}
\text{LHS}
&= \begin{aligned}[t]
I &+  t \cdot \overline{\tr}_\system{B}(\tilde{X}+Y) + t^2 \cdot \frac{\overline{\tr}_\system{B}(\tilde{X}Y+Y\tilde{X})}{2} \\
&+ t^3 \cdot \frac{\overline{\tr}_\system{B}\left( 2\tilde{X}Y\tilde{X} + 2Y\tilde{X}Y - \tilde{X}^2 Y - Y^2\tilde{X} - \tilde{X}Y^2 - Y \tilde{X}^2 \right)}{12} + O(t^4),\!
\end{aligned}\\
\label{eq:taylor:RHS:ADP}
\text{RHS}
&= \begin{aligned}[t]
I &+ t\cdot (X+\overline{\tr}_\system{B}(Y)) + t^2 \cdot \frac{X\overline{\tr}_\system{B}(Y) + \overline{\tr}_\system{B}(Y)X}{2}\\
&+ t^3 \cdot \begin{aligned}[t]
\bigg(&\frac{2X\overline{\tr}_\system{B}(Y)X - X^2\overline{\tr}_\system{B}(Y) - X \overline{\tr}_\system{B}(Y)^2}{12} \\
&+\frac{2\overline{\tr}_\system{B}(Y)X\overline{\tr}_\system{B}(Y) - \overline{\tr}_\system{B}(Y)^2X - \overline{\tr}_\system{B}(Y) X^2}{12}\bigg) + O(t^4).
\end{aligned}
\end{aligned}
\end{align}
Comparing~\eqref{eq:taylor:LHS:ADP} with~\eqref{eq:taylor:RHS:ADP}, we have
\[
\begin{aligned}
&\overline{\tr}_\system{B}\left((I+t X)\star(I+t Y)\right) = (I+t X) \star \overline{\tr}_\system{B}(I+t Y) + \\
&t^3\cdot\frac{2\left(\overline{\tr}_\system{B}(Y\tilde{X}Y) - \overline{\tr}_\system{B}(Y)X\overline{\tr}_\system{B}(Y)\right) + \left(\overline{\tr}_\system{B}(Y)^2 - \overline{\tr}_\system{B}(Y^2)\right)X + X\left(\overline{\tr}_\system{B}(Y)^2 - \overline{\tr}_\system{B}(Y^2)\right)}{12}\\
& + O(t ^4),
\end{aligned}
\]
which concludes the proof.
\end{proof}
\begin{remark}
Theorem~\ref{thm:approx:distri} and Proposition~\ref{prop:approx:distri} also hold if the local operators are \emph{proportionally} close to the identity matrix.
Namely, it holds that
\begin{align}
\tr\left(a(I+t X)\star b(I+t Y)\right) & = \tr_\system{A} \left( a(I+t X) \star \tr_\system{B}b(I+t Y) \right) + O(t^4)\\
\tr_\system{B}\left(a(I+t X)\star b(I+t Y)\right) &= \left( a(I+t X) \star \tr_\system{B} b(I+t Y) \right) + O(t^3)
\end{align}
for any real numbers $a$, $b$.
\end{remark}
\begin{corollary}\label{cor:QFG:chain}
\begin{figure}\centering
\begin{tikzpicture}[node distance=2cm, nodes={draw=none},
factor/.style={rectangle, minimum size=1cm, draw}]
\node[factor] (1) {}; \node at (1) {$\rho_1$};
\node[factor] (2)[right of=1] {}; \node at (2) {$\rho_2$};
\node[factor] (3)[right of=2] {}; \node at (3) {$\rho_3$};
\node[factor] (4)[right =2cm of 3] {}; \node at (4) {$\rho_{n\!-\!1}$};
\node[factor] (5)[right of=4] {}; \node at (5) {$\rho_n$};
\path (3) edge[draw=none] node[midway] (A) {$\cdots$} (4);
\draw[line width = 2pt] (1) -- (2) -- (3) -- (4) -- (5);
\draw[dashed] ([xshift=-.7cm,yshift=.7cm]1) rectangle ([xshift=.7cm,yshift=-.7cm]2);
\draw[dashed] ([xshift=-.9cm,yshift=.9cm]1) rectangle ([xshift=.7cm,yshift=-.9cm]3);
\draw[dashed] ([xshift=-1.1cm,yshift=1.1cm]1) rectangle ([xshift=.7cm,yshift=-1.1cm]4);
\draw[dashed] ([xshift=-1.3cm,yshift=1.3cm]1) rectangle ([xshift=.7cm,yshift=-1.3cm]5);
\end{tikzpicture}
\caption{A chain QFG. ($n\geqslant 3$).}
\label{fig:QFG:chain}
\end{figure}
Let $n\geqslant 3$.
Consider a chain QFG as in Figure~\ref{fig:QFG:chain}, where $\rho_1 \in \StPositiveOp(\hilbert_{1})$, $\rho_n \in \StPositiveOp(\hilbert_{n-1})$, and $\rho_k \in \StPositiveOp(\hilbert_{k-1}\tensor\hilbert_{k})$ for each $k=2,\ldots,n-1$.
Suppose that for each $k$, $\rho_k\propto I+t\cdot H_k$ for some Hermitian operator $H_k$ and some real number $t$ close to $0$, then Theorem~\ref{thm:approx:distri} implies the estimate
\begin{equation}\label{eq:chain:QFG}
\tr\left(\bigstar_{k=1}^{n}\rho_k\right) =
\tr_{n\!-\!1}\left( \tr_{n\!-\!2} \left(\cdots\tr_1(\rho_1\star\rho_2) \star \cdots \star \rho_{n\!-\!1}\right)\star\rho_{n}\right) + O(t^4).
\end{equation}
\end{corollary}
\begin{proof}
We use mathematical induction to prove~\eqref{eq:chain:QFG}.
For $n=3$,~\eqref{eq:chain:QFG} is the same as~\eqref{eq:approx:distri}.
Assume that~\eqref{eq:chain:QFG} is true when $n=m$, for some arbitrary integer $m\geqslant 3$.
Under this hypothesis, consider the case when $n=m+1$, \ie,
\begin{align*}
\tr\left(\bigstar_{k=1}^{m+1}\rho_k\right)
&= \tr\left(\rho_1\star\cdots\star\rho_{m-1}\star(\rho_m\star\rho_{m+1})\right)\\
&\overset{\text{(a)}}{=} \tr_{m,m\!-\!1}\left( \tr_{m\!-\!2}\left( \cdots \tr_1(\rho_1\star\rho_2) \cdots \star\rho_{m\!-\!1} \right) \star(\rho_{m}\star\rho_{m\!+\!1}) \right) + O(t^4)\\
&\overset{\text{(b)}}{=} \tr_{m}\left(\tr_{m\!-\!1}\left( \tr_{m\!-\!2}\left( \cdots \tr_1(\rho_1\star\rho_2) \cdots \star\rho_{m\!-\!1} \right) \star\rho_{m} \right) \star\rho_{m\!+\!1} \right) + O(t^4),
\end{align*}
where we have used the induction hypothesis in step (a) and Theorem~\ref{thm:approx:distri} in step (b).
Thus, we have shown that~\eqref{eq:chain:QFG} holds for $n=m+1$ provided the same expression holding for $n=m$.
By mathematical induction, the corollary is proven.
\end{proof}
Via Theorem~\ref{thm:approx:distri} and Proposition~\ref{prop:approx:distri}, we have established the following \emph{approximate distributive laws} of the $\star$-product over the trace and the partial trace functions.
\begin{align}
\label{eq:distributive:star}
\tr(\rho_a\star\rho_b) &\approx \tr_{\nb{b}\xk\set{I}}(\rho_a\star\tr_{\set{I}}(\rho_b)),\\
\label{eq:distributive:star:partial}
\tr_{\set{I}}(\rho_a\star\rho_b) &\approx \rho_a\star\tr_{\set{I}}(\rho_b),
\end{align}
where $\partial{a}\subsetneq\partial{b}$ and where $\set{I}\subset\partial{b}\setminus\partial{a}$ and where $\rho_a \in \StPositiveOp{ \Tensor_{ i\in \partial{a}}\hilbert_i}$ and $\rho_b \in \StPositiveOp{ \Tensor_{ i\in \partial{b}}\hilbert_i}$ are proportionally close to the identity matrix $I$.
\par
\begin {figure}\centering
\begin{tikzpicture}[every axis/.append style={font=\footnotesize},
every mark/.append style={scale=.9}]
\begin{semilogyaxis}[width = \textwidth, height = .618\textwidth,
xlabel={Relative Error $\eta$},
ylabel={Frequency Density}, ylabel shift = -4 pt,
xmin=0.002, xmax=0.2, ymin=0.0001,
legend style={font=\small}, legend cell align={left},
mark repeat={5}]
\addplot[dashed] table[x=error,y=freq_N.25] {1155001913-cao_michael_xuan-202104-phd-Data_approx_distributive.txt};
\addlegendentry{$\abs{\mathcal{N}(\mu,\sigma^2)}$ distributed Eigenvalues ($\mu=1$, $\sigma=0.25$)}
\addplot[solid] table[x=error,y=freq_N.5] {1155001913-cao_michael_xuan-202104-phd-Data_approx_distributive.txt};
\addlegendentry{$\abs{\mathcal{N}(\mu,\sigma^2)}$ distributed eigenvalues ($\mu=1$, $\sigma=0.5$)}
\addplot[solid,mark=+] table[x=error,y=freq_N1] {1155001913-cao_michael_xuan-202104-phd-Data_approx_distributive.txt};
\addlegendentry{$\abs{\mathcal{N}(\mu,\sigma^2)}$ distributed Eigenvalues ($\mu=1$, $\sigma=1$)}
\addplot[solid,mark=o] table[x=error,y=freq_U01] {1155001913-cao_michael_xuan-202104-phd-Data_approx_distributive.txt};
\addlegendentry{Uniformly distributed Eigenvalues ($a=0$, $b=1$)}
\end{semilogyaxis}\end{tikzpicture}
\caption{Distribution of $\eta$ for random positive operators $\rho_a$ and $\rho_b$ under different randomization schemes.}
\label{fig:approx:distributive:star}
\end{figure}
It is worthwhile to make a brief numerical comparison between $\tr_\system{A}( \rho_a\star \tr_\system{B}(\rho_b))$ and $\tr(\rho_\system{a}\star\rho_b)$.
In Figure~\ref{fig:approx:distributive:star}, we randomly generate $\rho_a\in\StPositiveOp(\hilbert_\system{A})$ and $\rho_b\in\StPositiveOp(\hilbert_\system{A}\tensor\hilbert_\system{B})$, where $\hilbert_\system{A}=\hilbert_\system{B}=\Complex^2$, and plot statistical distribution of the relative error as in
\begin{equation}
\eta \defeq \frac{\abs{\tr_\system{A}( \rho_a\star \tr_\system{B}(\rho_b)) - \tr(\rho_a\star\rho_b)}}{\tr(\rho_a\star\rho_b)}.
\end{equation}
Here, $\rho_a\defeq U_\system{A}^\Herm\Lambda_\system{A}U_\system{A}$ and $\rho_b\defeq U_\system{AB}^\Herm\Lambda_\system{AB}U_\system{AB}$, where the matrices $U_\system{A}$ and $U_\system{AB}$ are, respectively, random unitary matrices in $\Complex^2$ and $\Complex^4$ generated according to the Haar measures over unitary matrices of corresponding sizes and where $\Lambda_\system{A}$ and $\Lambda_\system{AB}$ are positive diagonal matrices with {i.i.d.}~entries (these entries are eigenvalues of $\rho_a$ and $\rho_b$).
The distributions used to generate the eigenvalues are marked in the legend.
For example, in the legend of Figure~\ref{fig:approx:distributive:star}, $\abs{\mathcal{N}(\mu,\sigma^2)}$ stands for the random variable distributed according to the absolute value of a Gaussian random variable with mean $\mu$ and variance $\sigma^2$.
\section{Quantum Belief-Propagation Algorithms}
In this section, we propose an approximated version of the ``closing-the-box'' operations for QFGs.
The approximation is based on the approximated distributivity discussed in the previous section.
The quantum belief-propagation algorithm, which was first proposed in~\cite{Leifer08}, can then be understood as a natural extension of the approximated ``closing-the-box'' operations.
At the end of this section, we discuss the holographic transformations of QFGs.
\subsection{Approximated ``Closing-the-Box'' Operations on QFGs}
Motivated by the approximated distributive law of the $\star$-product over partial trace operations (see~\eqref{eq:distributive:star:partial}), we define the ``closing-the-box'' operations on QFGs as the process to replace the box with the result of the partial trace of the $\star$-product of the local operators \emph{in} the box \wrt the Hilbert spaces \emph{in} the box.
\begin{definition}[``Closing-the-Box'' Operations on QFGs] \label{def:QFG:CtB} \index{closing-the-box operations!of QFGs}
Let $\set{G}=(\set{V},\set{F},\set{E})$ be a QFG as defined in Definition~\ref{def:QFG}.
Let $\set{G}'=(\set{V}',\set{F}')$ be a subgraph of $\set{G}$ such that if a variable vertex is in $\set{G}'$, so do all of its neighbors (all of which are in $\set{F}$).
(We call such a subgraph a \emph{box} of $\set{G}$.)
The ``closing-the-box'' operation (\wrt $\set{G}'$) is to replace $\set{G}'$ in $\set{G}$ by a factor vertex associated with the \emph{exterior operator} $\rho_{\set{G}'}$ of $\set{G}'$,
where $\rho_{\set{G}'}$ is the resultant operator by taking the partial trace of the $\star$-product of the local operators associated with $\set{F}'$ over the Hilbert spaces associated with $\set{V}'$.
\[
\rho_{\set{G}'} \defeq \tr_{i\in\set{V}'}\left(\bigstar_{a\in\set{F}'} \rho_a \right).\qedhere
\]
\end{definition}
Since the matrix exponential of Hermitian matrices is always PSD, a ``closing-the-box'' operation of a QFG always ends up with another QFG.
As discussed in Corollary~\ref{cor:QFG:chain}, for a chain QFG, its partition sum can be estimated via a sequence of ``closing-the-box'' operations.
This can be further generalized to all acyclic QFGs (see Theorem~\ref{thm:BP:QFG:tree} below).
\begin{theorem}\label{thm:BP:QFG:tree}
Given an acyclic QFG $(\set{G}=(\set{V},\set{F},\set{E}\in\set{V}\times\set{F}), \mathfrak{V}=\{\hilbert_i\}_{i\in\set{V}}, \mathfrak{F}=\{\rho_a\}_{a\in\set{F}})$, there exists a sequence of ``closing-the-box'' operations, tracing out one Hilbert space at each step, that shrinks the QFG to a constant\footnote{More precisely, the word ``constant'' here refers to a trivial QFG representing a constant operator on a 1-dimensional Hilbert space.} $\hat{Z}$.
If all local operators are proportionally close to $I$, \ie, for each $a$, $\rho_a\propto I+t\cdot H_a$ for some Hermitian operator $H_a$ and some small number $t$, we have
\begin{equation}
\hat{Z} = Z(\set{G}) + O(t^4).
\end{equation}
\end{theorem}
\begin{proof}
The first part of the theorem is a direct result of acyclicity:
Pick a vertex from $\set{V}$ as a root of $\set{G}$.
Since $\set{G}$ is a tree, there must exist another vertex $v\in\set{V}$ with no descendent from $\set{V}$ (note that $\set{G}$ is bipartite).
Closing the box encompassing $v$ and all of its neighbors will result in a tree with one less vertex from $\set{V}$.
The process can be repeated until there is only one vertex from $\set{V}$ left in the resultant graph, which can be then ``closed'' into a trivial QFG.
\par
The second part of the theorem is a direct generalization of Corollary~\ref{cor:QFG:chain} and can be justified using mathematical induction similar to that in the corollary's proof.
We omit the details.
\end{proof}
However, due to the approximating nature of the ``closing-the-box'' operations for QFGs, we do not have similar results as in Theorem~\ref{thm:BP:DeFG:tree} or Theorem~\ref{thm:BP:tree} for QFGs.
The process to estimate the partition sum, as mentioned in Theorem~\ref{thm:BP:QFG:tree}, is summarized in Algorithm~\ref{alg:BP:acyclic:QFG}.
Here, without loss of generality, we have assumed all the leaf vertices are from $\set{F}$, since we can always append an identity factor vertex to a leaf vertex from $\set{V}$ without changing the partition sum.
Note that, in Algorithm~\ref{alg:BP:acyclic:QFG}, we describe the ``closing-the-box'' operations as some message-passing rules, \ie,
\begin{align}
\label{eq:msg:acyclic:QFG:update:ia}
m_{i\to a} &\defeq \bigstar_{c\in\nb{i}\xk{a}} m_{c\to i},\\
\label{eq:msg:acyclic:QFG:update:ai}
m_{a\to i} &\defeq \tr_{\nb{a}\xk i}\left( \rho_a \star \Tensor_{k\in\nb{a}\xk{i}} m_{k\to a} \right),
\end{align}
where for each $(i,a)\in\set{E}$, $m_{a\to i}$, $m_{i\to a}$ are some PSD operators acting on $\hilbert_i$.
\begin{algorithm}
\caption{Belief-Propagation Algorithm for Acyclic QFGs}
\label{alg:BP:acyclic:QFG}
\begin{algorithmic}[1]
\Require{An acyclic QFG $\left(\set{G}=(\set{V},\set{F},\set{E}\in\set{V}\times\set{F}), \mathfrak{V}=\{\hilbert_i\}_{i\in\set{V}}, \mathfrak{F}=\{\rho_a\}_{a\in\set{F}}\right)$ with all leaf vertices belonging to $\set{F}$, a root vertex $r\in\mathcal{F}$; and for each $a\in\set{F}$, $\rho_a\propto I + t\cdot H_a$ for some Hermitian operator $H_a$ and some small number $t$}
\Ensure{An estimated partition sum $\hat{Z}=Z(\set{G})+O(t^4)$}
\State Define the bipartite graph $G'=(\set{V}',\set{F}',\set{E}')\gets \set{G}$;
\While{$\set{F}'\neq\{r\}$}
\ForAll{$a\in\set{F}'$ being a leaf and $i$ being its parent in $\set{G}'$}
\State $m_{a\to i} \gets \tr_{\nb{a}\xk i}\left( \rho_a \star \Tensor_{k\in\nb{a}\xk{i}} m_{k\to a} \right)$;
%\Comment{Note that $\Tensor_{k\in\nb{a}\xk{i}} m_{k\to a} \equiv \bigstar_{k\in\nb{a}\xk{i}} m_{k\to a}$}
\State $\set{F}'\gets \set{F}'\xk a$, $\set{E}'\gets \set{E}'\xk (\nb{a}\times a)$;
\Comment{Remove $a$ from $\set{G}'$.}
\EndFor
\ForAll{$i\in\set{V}'$ being a leaf and $a$ being its parent in $\set{G}'$}
\State $m_{i\to a}\gets\bigstar_{c\in\nb{i}\xk{a}} m_{c\to i}$;
\State $\set{V}'\gets \set{V}'\xk i$, $\set{E}'\gets \set{E}'\xk (i\times\nb{j})$;
\Comment{Remove $i$ from $\set{G}'$.}
\EndFor
\EndWhile
\State $\hat{Z}\gets \tr\left(\rho_r \star \Tensor_{i\in\nb{r}}m_{i\to r} \right)$;
\end{algorithmic}
\end{algorithm}
\subsection{Belief-Propagation Algorithms for QFGs}
Similar to factor graphs and DeFGs, for generic QFGs, we define BP algorithms\index{belief-propagation algorithm!for QFGs} as a heuristic generalization of the message-passing rules~\eqref{eq:msg:acyclic:QFG:update:ai} and~\eqref{eq:msg:acyclic:QFG:update:ia}.
Namely, we consider an iterative method with the updating rules
\begin{align}
\label{eq:msg:QFG:update:ia}
m_{i\to a}^{(t)} &\propto \bigstar_{c\in\nb{i}\xk{a}} m_{c\to i}^{(t)},\\
\label{eq:msg:QFG:update:ai}
m_{a\to i}^{(t)} &\propto \tr_{\nb{a}\xk i}\left( \rho_a \star \Tensor_{k\in\nb{a}\xk{i}} m_{k\to a}^{(t-1)} \right),
\end{align}
where the initial messages $\{m_{i\to a}^{(0)}\}_{(i,a)\in\set{E}}$ are proportional to identity operators.
The resultant BP algorithms for QFGs share a similar idea as that of the quantum belief-propagation (QBP) algorithm~\cite{Leifer08}.
However, the latter was derived via a different approach and required the target QFG to be \emph{bifactor}, \ie, each vertex in $\set{F}$ has a degree at most~$2$.
Similar to BP algorithms for factor graphs and DeFGs, different updating sequences of the messages in~\eqref{eq:msg:QFG:update:ia} and~\eqref{eq:msg:QFG:update:ai} (\aka schedules) exist.
However, as usual, we will focus on the synchronous schedule (\aka flooding schedule) in this thesis.
Algorithm~\ref{alg:BP:QFG} lists BP algorithm for QFGs with the flooding schedule.
\begin{algorithm}
\caption{Belief-Propagation Algorithm for QFGs (Flooding Schedule with Timeout)}
\label{alg:BP:QFG}
\begin{algorithmic}[1]
\Require{A QFG $\left(\set{G}=(\set{V},\set{F},\set{E}\in\set{V}\times\set{F}), \mathfrak{V}=\{\hilbert_i\}_{i\in\set{V}}, \mathfrak{F}=\{\rho_a\}_{a\in\set{F}}\right)$ with all leaf vertices belonging to $\set{F}$, a root vertex $r\in\mathcal{F}$; and for each $a\in\set{F}$, $\rho_a \propto I + t\cdot H_a$ for some Hermitian operator $H_a$ and some small number $t$; $\epsilon>0$}
\Ensure{Messages $\{m_{i\to a},m_{a\to i}\in\PositiveOp(\hilbert_i)\}_{(i,a)\in\set{E}}$, $\mathsf{FLAG}\in\{\mathrm{completed},\mathrm{timeout}\}$.}
\ForAll{$(i,a)\in\set{E}$}
\State $m_{i\to a}\gets I$;
%\State $m_{a\to i}\gets I$;
\Comment{$I$ is the identity operator on $\hilbert_i$.}
\EndFor
\State $t\gets 0$;
\Do
\State $t\gets t+1$;
\ForAll{$(i,a)\in\set{E}$}
%\State $m_{i\to a}^{(t)} \defpropto \bigstar_{c\in\nb{i}\xk{a}} m_{c\to i}^{(t-1)}$;
\State $m_{a\to i}^{(t)} \defpropto \tr_{\nb{a}\xk i}\left( \rho_a \star \Tensor_{k\in\nb{a}\xk{i}} m_{k\to a}^{(t-1)} \right)$;
\EndFor
\ForAll{$(i,a)\in\set{E}$}
\State $m_{i\to a}^{(t)} \defpropto \bigstar_{c\in\nb{i}\xk{a}} m_{c\to i}^{(t)} \equiv \Tensor_{c\in\nb{i}\xk{a}} m_{c\to i}^{(t)}$;
\EndFor
\DoWhile{$\left(\neg\mathsf{timeout}\right) \land \left( \exists(i,a)\in\set{E} \text{ s.t. }\norm{m_{i\to a}^{(t)}-m_{i\to a}^{(t-1)}}_2>\varepsilon\text{ or }\norm{m_{a\to i}^{(t)}-m_{a\to i}^{(t-1)}}_2>\varepsilon\right)$}
\Comment{$\mathsf{timeout}=\mathsf{false}$ unless the operating time exceeds a pre-selected waiting time.}
\If{$\mathrm{timeout}$}
\State{$\mathsf{FLAG}\gets\mathrm{timeout}$;}
\Else
\State{$\mathsf{FLAG}\gets\mathrm{completed}$;}
\ForAll{$(i,a)\in\set{E}$}
\State{$m_{i\to a}\gets m_{i\to a}^{(t)}$;}
\State{$m_{a\to i}\gets m_{a\to i}^{(t)}$;}
\EndFor
\EndIf
\end{algorithmic}
\end{algorithm}
\par
We define the BP fixed points of a QFG similarly to those of a factor graph or a DeFG.
\begin{definition}[BP Fixed Points of a QFG]\label{def:QFG:BP:fixed:points} \index{BP fixed points! of QFGs}
Given a QFG as provided to Algorithm~\ref{alg:BP:QFG}, a set of messages $\{m_{i\to a},m_{a\to i}\in\PositiveOp(\hilbert_i)\}_{(i,a)\in\set{E}}$ is said to be a BP fixed point if
\begin{align}
\label{eq:fixed:QFG:ia}
m_{i\to a} &\propto \bigstar_{c\in\nb{i}\xk{a}} m_{c\to i}, \\
\label{eq:fixed:QFG:ai}
m_{a\to i} &\propto \tr_{\nb{a}\xk i}\left( \rho_a \star \Tensor_{k\in\nb{a}\xk{i}} m_{k\to a} \right).
\end{align}
In this case, the set $\{m_{i\to a},m_{a\to i}\}_{(i,a)\in\set{E}}$ is also called a set of fixed-point messages.
\end{definition}
At a BP fixed point, we estimate the partition sum using the induced partition sum (see definition below).
We will discuss an interpretation of the BP fixed points and the corresponding induced partition sums in Section~\ref{sec:QFG:bethe}.
\begin{definition}
Given a set of normalized PSD messages $\{m_{i\to a},m_{a\to i}\}_{(i,a)\in\set{E}}$, not necessarily a BP fixed point, the \emph{induced} partition sum (\wrt the messages) is defined as
\begin{equation}
Z_{\mathsf{induced}}\left(\{m_{i\to a},m_{a\to i}\}_{(i,a)\in\set{E}}\right)=\frac{\prod_{a\in\set{F}}Z_a(\{m_{i\to a}\}_{i\in\nb{a}})\cdot\prod_{i\in\set{V}}Z_i(\{m_{a\to i}\}_{a\in\nb{i}})}{\prod_{(j,a)\in\set{E}}Z_{i,a}(m_{i\to a},m_{a\to i})},
\end{equation}
\begin{align*}
Z_a(\{m_{i\to a}\}_{i\in\nb{a}}) &\defeq \tr\left( \rho_a \star \Tensor_{i\in\nb{a}} m_{i\to a} \right) && \forall a\in\set{F},\\
Z_i(\{m_{a\to i}\}_{a\in\nb{i}}) &\defeq \tr\left( \bigstar_{a\in\nb{i}} m_{a\to i} \right) && \forall i\in\set{V},\\
Z_{i,a}(m_{i\to a},m_{a\to i}) &\defeq \tr\left( m_{i\to a}\star m_{a\to i} \right) && \forall (i,a)\in\set{E}. \qedhere
\end{align*}
\end{definition}
\subsection{Holographic Transformations of QFGs}
The following theorem is a generalization of Theorem~\ref{thm:holant} for QFGs.
The holographic transformations of QFGs is a direct result of this theorem.
\begin{theorem}[Holant Theorem for QFGs]
Let $\set{G}=(\set{V},\set{F},\set{E})$ be a QFG representing the factorization $\rho=\bigstar_{a\in\set{F}} \rho_a$.
Given Hermitian operators $\{\hat{\phi}_{i,a}\in\HermitianOp(\hilbert_{i,a}\tensor\hilbert_i)\}_{i,a}\in\set{E}$ and $\{\phi_{i,a}\in\HermitianOp(\hilbert_i\tensor\hilbert_{i,a})\}_{i,a}\in\set{E}$ such that
\begin{equation}
\tr_{\hilbert_{i,a}}	 \left(\phi_{i,a}\star\hat{\phi}_{i,a}\right) = I_{\hilbert_i}
\end{equation}
for each $(i,a)\in\set{E}$, and supposing $\{\rho_a\}_{a\in\set{F}}$, $\{\hat{\phi}_{i,a},\phi_{i,a}\}_{(i,a)\in\set{E}}$ are proportionally close to the identity operator, the partition sum $Z(\set{G})$ can be approximated as
\begin{equation}
Z(\set{G})\defeq \tr\left( \bigstar_{a\in\set{F}} \rho_a \right) \approx
\tr\left(\Tensor_{a\in\set{F}} \hat{\rho}_a \star \Tensor_{i\in\set{V}}\hat\tau_i \right),
\end{equation}
\begin{align}
\hat{\rho}_a &\defeq \tr_{\nb{a}} \left( \rho_a \star \bigstar_{i\in\nb{a}} \hat{\phi}_{i,a} \right) \in \HermitianOp\left( \Tensor_{i\in\nb{a}} \hilbert_{i,a} \right) = \HermitianOp(\hilbert_{\nb{a},a}),\\
\hat{\tau}_i &= \tr_{i} \left(\bigstar_{a\in\nb{i}} \phi_{i,a} \right) \in \HermitianOp\left( \Tensor_{a\in\nb{i}} \hilbert_{i,a} \right) = \HermitianOp(\hilbert_{i,\nb{i}}).
\end{align}
\end{theorem}
\begin{proof}
The proof is based on the approximated distributivity of $\star$ over trace operation~\eqref{eq:distributive:star}.
\begin{fleqn}\begin{equation*}
\tr\left(\Tensor_{a\in\set{F}} \hat{\rho}_a \star \Tensor_{i\in\set{V}}\hat\tau_i \right)
\overset{\text{(a)}}{=} \tr\left(\bigstar_{a\in\set{F}} \hat{\rho}_a \star \bigstar_{i\in\set{V}}\hat\tau_i \right)
\end{equation*}\end{fleqn}
\begin{fleqn}\begin{equation*}
\phantom{\tr\left(\Tensor_{a\in\set{F}} \hat{\rho}_a \star \Tensor_{i\in\set{V}}\hat\tau_i \right)}
= \tr\left(\bigstar_{a\in\set{F}} \tr_{\nb{a}}\left( \rho_a \star \bigstar_{i\in\nb{a}} \hat{\phi}_{i,a} \right) \star \bigstar_{i\in\set{V}} \tr_{i} \left(\bigstar_{a\in\nb{i}} \phi_{i,a} \right) \right)
\end{equation*}\end{fleqn}
\begin{fleqn}\begin{equation*}
\phantom{\tr\left(\Tensor_{a\in\set{F}} \hat{\rho}_a \star \Tensor_{i\in\set{V}}\hat\tau_i \right)}
\overset{\text{(b)}}{\approx} \tr\left(\bigstar_{(i,a)\in\set{E}}\left( \hat{\phi}_{i,a} \star \phi_{i,a} \right) \star \bigstar_{a\in\set{F}} \rho_a \right)
\end{equation*}\end{fleqn}
\begin{fleqn}\begin{equation*}
\phantom{\tr\left(\Tensor_{a\in\set{F}} \hat{\rho}_a \star \Tensor_{i\in\set{V}}\hat\tau_i \right)}
\overset{\text{(c)}}{\approx} \tr\left(\bigstar_{(i,a)\in\set{E}} \tr_{\hilbert_{i,a}} \left( \hat{\phi}_{i,a} \star \phi_{i,a} \right) \star \bigstar_{a\in\set{F}} \rho_a \right)
\end{equation*}\end{fleqn}
\begin{fleqn}\begin{equation*}
\phantom{\tr\left(\Tensor_{a\in\set{F}} \hat{\rho}_a \star \Tensor_{i\in\set{V}}\hat\tau_i \right)}
= \tr\left(\bigstar_{(i,a)\in\set{E}} I_{\hilbert_i} \star \bigstar_{a\in\set{F}} \rho_a \right)
\end{equation*}\end{fleqn}
\begin{fleqn}\begin{equation*}
\phantom{\tr\left(\Tensor_{a\in\set{F}} \hat{\rho}_a \star \Tensor_{i\in\set{V}}\hat\tau_i \right)}
= \tr\left(I_{\hilbert_\set{V}} \star \bigstar_{a\in\set{F}} \rho_a \right)
= \tr\left(\bigstar_{a\in\set{F}} \rho_a \right)
= Z(\set{G}),
\end{equation*}\end{fleqn}
where step~(a) is due to the convention that $\rho_\system{A}\star \rho_\system{B} \equiv \rho_\system{A}\tensor \rho_\system{B}$ given $\rho_\system{A}$ and $\tau_\system{B}$ acting on isolated Hilbert spaces and where we have used~\eqref{eq:distributive:star} in step~(b) and~(c).
\end{proof}
We define the holographic transform of $\set{G}$ (\wrt $\{\hat{\phi}_{i,a},\phi_{i,a}\}_{(i,a)\in\set{E}}$) to be the QFG $\hat{\set{G}}=(\set{E},\set{F}\cup\set{V},\setdef{(e,e_1),(e,e_2)}{e\in\set{E}})$ representing the factorization
\begin{equation}
\hat{\rho} = \Tensor_{a\in\set{F}} \hat{\rho}_a \star \Tensor_{i\in\set{V}}\hat\tau_i
= \bigstar_{a\in\set{F}} \hat{\rho}_a \star \bigstar_{i\in\set{V}}\hat\tau_i.
\end{equation}
\section{Generalization of Bethe's approximation for QFGs}\label{sec:QFG:bethe}
Bethe's approximation (see Section~\ref{subsec:FG:Bethe}) is a successful approach to interpret BP algorithms for factor graphs.
In this section, we generalize the method to QFGs.
In particular, we prove a generalized version of Theorem~\ref{thm:bethe:BPA} (\ie,~\cite[Theorem 2]{yedidia2005constructing}).
\subsection{From Local Density Operators to Global Density Operators}
An important result following from Theorem~\ref{thm:approx:distri} and Proposition~\ref{prop:approx:distri} is the ability to construct the global density operators from the local operators under suitable conditions.
This is stated in the following lemma.
Notice that this lemma serves as a quantum analog of Lemma 2 in~\cite{mori2015loop}.
\begin{lemma}\label{lemma:QFG:split}
Consider an acyclic QFG $(\set{V},\set{F},\set{E})$.
Given the density operators $\{\sigma_{a}\in \DensOp(\Tensor_{i\in\nb{a}}\hilbert_i)\}_{a\in\set{F}}$ and $\{\sigma_{i}\in\DensOp(\hilbert_i)\}_{i\in\set{V}}$, all of which are proportionally close to the identity operator, such that
\begin{equation}
\sigma_i = \tr_{\partial{a}\xk i}(\sigma_a) \qquad \forall(i,a)\in\set{E},
\end{equation}
there exists a global density operator $\sigma \in \DensOp(\Tensor_{i\in\set{V}}\hilbert_i)$ such that
\begin{align}
\label{eq:QFG:marginal:a}
\tr_{\set{V}\xk \nb{a}}(\sigma) & \approx \sigma_a && \forall a\in\set{F},\\
\label{eq:QFG:marginal:i}
\tr_{\set{V}\xk i}(\sigma) & \approx \sigma_i && \forall i\in\set{V},
\end{align}
where the approximations ``$\:\approx$'' in the above equations are based on~\eqref{eq:distributive:star}.
\end{lemma}
\begin{proof}
Let $\sigma$ be a density operator acting on $\Tensor_{i\in\set{V}}\hilbert_i$ such that
\begin{equation}
\sigma \propto \exp\left( \sum_{a\in\set{F}} \log{\sigma_a} - \sum_{i\in\set{V}}(d_i-1)\log{\sigma_i} \right),
\end{equation}
where $d_i=\deg(i)$ for each $i\in\set{V}$.
We claim that both~\eqref{eq:QFG:marginal:a} and~\eqref{eq:QFG:marginal:i} hold for this $\sigma$.
To verify~\eqref{eq:QFG:marginal:a}, we have
\begin{fleqn}\begin{equation*}
\tr_{\set{V}\xk\nb{a}}(\sigma)
\propto \tr_{\set{V}\xk\nb{a}}\left( \exp\left( \sum_{a\in\set{F}} \log{\sigma_a} - \sum_{i\in\set{V}}(d_i-1)\log{\sigma_i} \right) \right)
\end{equation*}\end{fleqn}
\begin{fleqn}\begin{equation*}\phantom{\tr_{\set{V}\xk\nb{a}}(\sigma)}
\overset{\text{(a)}}{=} \tr_{\set{V}\xk\nb{a}}\left( \exp\left( \log{\sigma_a} + \sum_{n=0}^N \sum_{i\in\nb{^na},\atop c\in\nb{^*_a i}} \left( \log{\sigma_c} - \log{\sigma_i} \right) \right) \right)
\end{equation*}\end{fleqn}
\begin{fleqn}\begin{equation*}\phantom{\tr_{\set{V}\xk\nb{a}}(\sigma)}
= \tr_{\set{V}\xk\nb{a}}\left( \exp\left( \log{\sigma_a} + \sum_{n=0}^{N-1} \sum_{i\in\nb{^na},\atop c\in\nb{^*_a i}} \left( \log{\sigma_c} - \log{\sigma_i} \right) \right)\star \bigstar_{i\in\nb{^Na},\atop c\in\nb{^*_a i}} \left(\sigma_c \star \sigma_i^{-1}\right) \right)
\end{equation*}\end{fleqn}
\begin{fleqn}\begin{equation*}\phantom{\tr_{\set{V}\xk\nb{a}}(\sigma)}
\overset{\text{(b)}}{\approx} \tr_{\set{V}\xk\nb{a}}\left( \exp\left( \log{\sigma_a} + \sum_{n=0}^{N-1} \sum_{i\in\nb{^na},\atop c\in\nb{^*_a i}} \left( \log{\sigma_c} - \log{\sigma_i} \right) \right)\star \bigstar_{i\in\nb{^Na},\atop c\in\nb{^*_a i}} \left(\tr_{\nb{c}\xk{i}}(\sigma_c) \star \sigma_i^{-1}\right) \right)
\end{equation*}\end{fleqn}
\begin{fleqn}\begin{equation*}\phantom{\tr_{\set{V}\xk\nb{a}}(\sigma)}
= \tr_{\set{V}\xk\nb{a}}\left( \exp\left( \log{\sigma_a} + \sum_{n=0}^{N-1} \sum_{i\in\nb{^na},\atop c\in\nb{^*_a i}} \left( \log{\sigma_c} - \log{\sigma_i} \right) \right) \right)
\end{equation*}\end{fleqn}
\begin{fleqn}\begin{equation*}\phantom{\tr_{\set{V}\xk\nb{a}}(\sigma)}
\approx \cdots \approx \tr_{\set{V}\xk\nb{a}}\left( \exp\left( \log{\sigma_a} \right) \right) = \sigma_a,
\end{equation*}\end{fleqn}
where $\nb{^na}$ denotes the set of vertices in $\set{V}$ reachable from $a\in\set{F}$ after walking through $n$ vertices in $\set{F}$ (without backtracking), where $\nb{^*_a i}$ denotes the set of the neighbors of $i$ excluding the vertex through which $a$ reaches $i$, and where $N$ is the largest integer such that $\nb{^Na}$ is nonempty.
Step~(a) is due to the tree structure.
Step~(b) and the ``$\approx$'' on the last line follow directly from Proposition~\ref{prop:approx:distri}.
\par
We omit the verification of~\eqref{eq:QFG:marginal:a} since the process is very similar.
\end{proof}
It is worth noting that if we had defined the global density operator $\tilde\sigma$ as
\begin{equation}
\tilde\sigma \defeq \exp\left( \sum_{a\in\set{F}} \log{\sigma_a} - \sum_{i\in\set{V}} (d_i-1) \log{\sigma_i} \right),
\end{equation}
we would have encountered the problem that $\tr(\tilde\sigma)\neq 1$, despite that a similar result holds for acyclic (classical) factor graphs, \ie,
\begin{equation}
\sum_{\vx} \prod_{a\in\set{F}} \frac{b_a(\vx_\nb{a})} {\prod_{i\in\nb{a}} b_i(x_i)}\prod_{i\in\set{V}} b_i(x_i) = 1,
\end{equation}
given the \pmfs $\{b_a\}_{a\in\set{F}}$, $\{b_i\}_{i\in\set{V}}$ such that $\sum_{\vx_{\nb{a}\xk{i}}} b_a(\vx_\nb{a}) = b_i(x_i)$ for all $(i,a)\in\set{E}$.
However, approximately speaking (using~\eqref{eq:distributive:star}), we have
\begin{equation}\label{eq:tilde:sigma:tr:1}
\tr(\tilde\sigma) = \tr_{\nb{a}}\left( \tr_{\set{V}\xk\nb{a}}\left( \exp\left( \sum_{a\in\set{F}} \log{\sigma_a} - \sum_{i\in\set{V}}(d_i-1) \log{\sigma_i} \right)\! \right)\! \right)
\approx \tr_{\nb{a}}(\sigma_a) = 1.
\end{equation}
Thus, we can treat $\tilde{\sigma}$ as an approximate global density operator.
\subsection{Free Energies of QFGs}
We define quantum analogies of the Helmholtz free energy and the Gibbs free energy function as follows.
\begin{definition} \label{def:QFG:energy} \index{free energy!quantum Helmholtz} \index{free energy!quantum Gibbs}
Given a QFG $\set{G}$ representing the factorization $\rho=\bigstar_{a\in\set{F}} \rho_a$, we define the \emph{quantum Helmholtz free energy} and the \emph{quantum Gibbs free energy function} \wrt the density operator $\sigma\in\DensOp(\hilbert_\set{V})$ as
\begin{align}
\helmholtz &\defeq - \log{Z(\set{G})}, \\
\gibbs(\sigma) &\defeq - \sum_{a \in \set{F}} \tr\left( \sigma \cdot (\log{\rho_a} \tensor I_{\hilbert_{\set{V}\xk\nb{a}}}) \right) - \qEntropy(\sigma),
\end{align}
where $\qEntropy(\sigma)$ is the von Neumann entropy of $\sigma$.
\end{definition}
\begin{theorem}\label{thm:QFG:Gibbs:geq:Helmholtz}
$\gibbs(\sigma)$ is lower bounded by $\helmholtz$.
In particular,
\begin{equation}
\gibbs(\sigma) = \helmholtz + \infdiv{\sigma}{\tilde\rho},
\end{equation}
where $\tilde\rho\defeq\rho/Z(\set{G})\propto \bigstar_{a\in\set{F}}\rho_a$ is a density operator.
\end{theorem}
\begin{proof}
This is a result of the direct computation, \ie,
\begin{fleqn}\begin{equation*}
\gibbs(\sigma) - \helmholtz = - \sum_{a \in \set{F}} \tr\left( \sigma \cdot (\log{\rho_a} \tensor I_{\hilbert_{\set{V}\xk\nb{a}}}) \right) - \qEntropy(\sigma) + \log(Z(\set{G}))
\end{equation*}\end{fleqn}
\begin{fleqn}\begin{equation*}\phantom{\gibbs(\sigma) - \helmholtz}
= - \tr\left( \sigma \cdot \left(\sum_{a\in\set{F}} \log{\rho_a} - \log{Z(\set{G})} \cdot I \right) \right) + \tr\left(\sigma\cdot \log{\sigma} \right)
\end{equation*}\end{fleqn}
\begin{fleqn}\begin{equation*}\phantom{\gibbs(\sigma) - \helmholtz}
= - \tr\left( \sigma \cdot \log\left(\exp{\left(\sum_{a\in\set{F}} \log{\rho_a} - \log{Z(\set{G})} \cdot I \right)} \right) \right) + \tr\left(\sigma\cdot \log{\sigma} \right)
\end{equation*}\end{fleqn}
\begin{fleqn}\begin{equation*}\phantom{\gibbs(\sigma) - \helmholtz}
= - \tr\left( \sigma \cdot \log{\tilde\rho} \right) + \tr\left(\sigma\cdot \log{\sigma} \right)
= \infdiv{\sigma}{\tilde\rho}.
\end{equation*}\end{fleqn}
By the Klein's inequality, we have $\gibbs(\sigma) \geq \helmholtz$, with equality if and only if $\sigma = \tilde\rho$.
\end{proof}
Theorem~\ref{thm:QFG:Gibbs:geq:Helmholtz} allows us to compute $\helmholtz$ via minimizing $\gibbs(\sigma)$ over all possible $\sigma\in\DensOp(\hilbert_\set{V})$.
However, such an optimization problem is, in general, not tractable due to the enormous dimension of the density operator $\sigma$.
In analogy to the Bethe free energy (see Definition~\ref{def:bethe:energy}), we propose the following quantum Bethe free energy as an approximation to $\gibbs$.
\begin{definition}[Quantum Bethe Free Energy]\label{def:quantum:bethe:energy} \index{free energy!quantum Bethe}
Given a QFG $\set{G}$ representing the factorization $\rho=\bigstar_{a\in\set{F}} \rho_a$, the \emph{quantum Bethe free energy function} is the function
\begin{equation}\label{eq:quantum:bethe:energy}
\begin{aligned}
\bethe(\{\sigma_a\}_{a \in \set{F}}, \{\sigma_i\}_{i \in \set{V}})) \defeq
&-\sum_{a\in\set{F}} \tr\left( \sigma_a\cdot \log{\rho_a} \right) +  \sum_{a\in\set{F}} \tr\left( \sigma_a\cdot \log{\sigma_a} \right)\\
&-\sum_{i\in\set{V}} (d_i-1) \cdot \tr\left( \sigma_i\cdot \log{\sigma_i} \right),
\end{aligned}
\end{equation}
where the domain of $\bethe$ is
\[
\set{L}(\set{G}) \defeq \setdef*{\big(\{\sigma_a\}_{a\in\set{F}},\{\sigma_i\}_{i\in\set{V}}\big)}
\sigma_a\in\DensOp(\Tensor_{i\in\nb{a}}\hilbert_i) &\forall a\in\set{F}\\
\sigma_i\in\DensOp(\hilbert_i) &\forall i\in\set{V}\\
\tr_{\nb{a}\xk{i}} \sigma_a = \sigma_i &\forall (i,a)\in\set{E}
\end{array}}.\qedhere
\]
\end{definition}
For acyclic QFGs, the quantum Bethe free energy approximates the Gibbs free energy, as shown in the following theorem.
\begin{theorem}\label{thm:quantum:Bethe:Gibbs}
Consider an acyclic QFG $(\set{V},\set{F},\set{E})$ representing the factorization $\rho = \bigstar_{a\in\set{F}} \rho_a$.
Let $\sigma$ be a global density operator, and for each $a\in\set{F}$, let $\sigma_a \defeq \tr_{\set{V}\xk\nb{a}} (\sigma)$, and for each $i\in\set{V}$, let $\sigma_i \defeq \tr_{\set{V}\xk i}(\sigma)$.
Supposing $\{\rho_a\}_{a\in\set{F}}$ and $\sigma$ are proportionally close to the identity operators, \ie, $\rho_a\propto I + t\cdot H_a$ and $\sigma\propto I + t\cdot H$ for some Hermitian operators $H_a$ and $H$ and some small number $t$, then
\begin{equation}\label{eq:quantum:Bethe:Gibbs}
\gibbs(\sigma) = \bethe(\{\sigma_a\}_{a\in\set{F}}, \{\sigma_i\}_{i\in\set{V}})) + O(t^3).
\end{equation}
\end{theorem}
\begin{proof}
By definition of partial trace, it holds that
\[
\tr\left( \sigma \cdot (\log{\rho_a} \tensor I_{\hilbert_{\set{V}\xk\nb{a}}}) \right) = \tr\left( \sigma_a\cdot \log{\rho_a} \right).
\]
Considering the definitions of $\gibbs$ and $\bethe$, it suffices to show
\[
\sum_{a\in\set{F}} \tr\left( \sigma_a\cdot \log{\sigma_a} \right) -\sum_{i\in\set{V}} (d_i-1) \cdot \tr\left( \sigma_i\cdot \log{\sigma_i} \right) - \tr\left(\sigma\cdot\log{\sigma}\right) = O(t^3).
\]
By letting $\tilde\sigma \defeq \exp\left( \sum_{a\in\set{F}} \log{\sigma_a} - \sum_{i\in\set{V}} (d_i-1) \log{\sigma_i} \right)$, the LHS of above can be rewritten as
\[\begin{aligned}
\tr\left(\sigma\cdot\log{\tilde\sigma}\right) - \tr\left(\sigma\cdot\log{\sigma}\right)
= \tr\left(\sigma\cdot\log{\frac{\tilde\sigma}{\tr\left(\tilde\sigma\right)}}\right) - \tr\left(\sigma\cdot\log{\sigma}\right) + \tr\left(\tilde\sigma\right), \\
= \tr\left(\sigma\cdot\log{\frac{\tilde\sigma}{\tr\left(\tilde\sigma\right)}}\right) - \tr\left(\sigma\cdot\log{\sigma}\right) + O(t^4),
\end{aligned}\]
where we have used~\eqref{eq:tilde:sigma:tr:1} and Theorem~\ref{thm:approx:distri} in the very last step.
\par
Now, consider the quantum exponential family as in Example~\ref{example:QEFwrtG} in Appendix~\ref{app:QEF}.
By Lemma~\ref{lemma:QFG:split}, we know that
\begin{align*}
\tr_{\set{V}\xk\nb{a}} (\sigma) - \tr_{\set{V}\xk\nb{a}}\left( \frac{\tilde\sigma}{\tr\left(\tilde\sigma\right)} \right)
&= \sigma_a - \tr_{\set{V}\xk\nb{a}}\left( \frac{\tilde\sigma}{\tr\left(\tilde\sigma\right)} \right) = O(t^3), \\
\tr_{\set{V}\xk i} (\sigma) - \tr_{\set{V}\xk i}\left( \frac{\tilde\sigma}{\tr\left(\tilde\sigma\right)} \right)
&= \sigma_i - \tr_{\set{V}\xk i}\left( \frac{\tilde\sigma}{\tr\left(\tilde\sigma\right)} \right) =  O(t^3).
\end{align*}
In terms of their dual parameters, this can be written as $\boldeta(\sigma) = \boldeta(\frac{\tilde\sigma}{\tr\left(\tilde\sigma\right)}) + t^3 \cdot \Delta\boldeta + O(t^4)$ for some real vector $\Delta\boldeta$ (see Appendix~\ref{app:QEF}).
Define the function $f(\boldeta): \boldeta \mapsto - \tr\left( \sigma \cdot \log{\sigma(\boldeta)} \right)$.
In this case, we have
\begin{align*}
\lim_{t \to 0} \frac{\tr\left(\sigma\cdot\log{\frac{\tilde\sigma}{\tr\left(\tilde\sigma\right)}}\right) - \tr\left(\sigma\cdot\log{\sigma}\right)}{t^3}
& = \lim_{t \to 0} \frac{f(\boldeta(\frac{\tilde\sigma}{\tr\left(\tilde\sigma\right)})) - f(\boldeta(\sigma))}{t^3}\\
& = \lim_{t \to 0} \frac{f(\boldeta(\frac{\tilde\sigma}{\tr\left(\tilde\sigma\right)})) - f(\boldeta(\frac{\tilde\sigma}{\tr\left(\tilde\sigma\right)}) + t^3 \cdot \Delta\boldeta + O(t^4))}{t^3}\\
& = \grad{f}^\transp \cdot \Delta\boldeta,
\end{align*}
where the differentiability of $f$ is justified in Appendix~\ref{app:differentiability}.
Since $\grad{f}^\transp \cdot \Delta\boldeta$ is a finite number, we conclude that $\tr\left(\sigma\cdot\log{\frac{\tilde\sigma}{\tr\left(\tilde\sigma\right)}}\right) - \tr\left(\sigma\cdot\log{\sigma}\right) = O(t^3)$.
Thus, we have $\tr\left(\sigma\cdot\log{\tilde\sigma}\right) - \tr\left(\sigma\cdot\log{\sigma}\right) = O(t^3)$, which finishes the proof.
\end{proof}
\subsection{Correspondence between the Stationary Points of $\bethe$ and the BP Fixed Points}
Motivated by Theorem~\ref{thm:quantum:Bethe:Gibbs}, which allows us to treat the Bethe free energy $\bethe$ as an approximation to the Gibbs free energy $\gibbs$, we define the following optimization problem as an approximated version of the Gibbs minimization problem.
\begin{definition}[Constrained Quantum Bethe Minimization Problem]
Given a QFG $(\set{V},\set{F},\set{E})$ representing the factorization $\rho=\bigstar_{a\in\set{F}} \rho_a$, the optimization problem
\begin{equation}\begin{aligned}
\min\quad & \bethe(\{\sigma_a\}_{a \in \set{F}}, \{\sigma_i\}_{i \in \set{V}})) \\
\st\quad & \sigma_a\in\DensOp(\Tensor_{i\in\nb{a}}\hilbert_i) &&\forall a\in\set{F}\\
& \sigma_i\in\DensOp(\hilbert_i) &&\forall i\in\set{V}\\
& \tr_{\nb{a}\xk{i}} \sigma_a = \sigma_i &&\forall (i,a)\in\set{E}
\end{aligned}\end{equation}
is called the \emph{constrained Bethe minimization problem}.
\end{definition}
One must note that even for acyclic QFGs, $\bethe$ is merely an approximation to $\gibbs$ under suitable conditions.
Thus, the constrained Bethe minimization problem does not guarantee the recovery of the quantum Helmholtz free energy $\helmholtz$, even for acyclic cases.
In contrast, for acyclic factor graphs, $\bethe$ and $\gibbs$ share the same minimum, which equals the Helmholtz free energy $\helmholtz$.
In other words, the BP algorithm for acyclic factor graphs is exact, but BP algorithms for acyclic QFGs are not.
\par
In the remainder of this section, we show how the quantum BP algorithms, particularly the BP fixed points, are connected to the constrained Bethe minimization problem.
\begin{theorem}\label{thm:bethe:QBPA}
Given a QFG $((\set{V},\set{F},\set{E}),\{\hilbert_i\}_{i\in\set{V}},\{\rho_a\}_{a\in\set{F}})$ with (straightly) PD local operators, $\left(\{\sigma_a\}_{a\in\set{F}},\{\sigma_i\}_{i\in\set{V}}\right)\in\set{L}(\set{G})$ is an interior stationary point of $\bethe$ if