Let $pleft(z_i mid x_iright)$ for $i=1, cdots, m$ be some probabilities, where $x_i, z_i in{0,1}$. I want to efficiently compute the following:

begin{align*}
nuleft(z_1, cdots, z_mright)=sum_{x_1, cdots x_m} prod_{i=1}^m pleft(z_i mid x_iright) muleft(x_1, cdots, x_mright)
end{align*}
for all $(z_1, cdots, z_m).$
I know that convolutions can be computed efficiently with FFT in $Oleft(m 2^mright)$. Is there a way to compute $nuleft(z_1, cdots, z_mright)$ with similar computational complexity?

Specifically, $pleft(z_i|x_iright)$ does not depend on $i$ and is given as follows: $p(z|x)=left{begin{array}{ll}1-q, & (z, x)=(0,0) q, & (z, x)=(1,0) 1 / 2, & (z, x)=(0,1) 1 / 2, & (z, x)=(1,1)end{array}right.$

I tried to speed up the computation using a similar approach to how convolutions are calculated with FFT, but I couldn’t make it work successfully.