I was trying to find a solution for calculating this faster than the naive method, but I couldn't make any bigger steps.
Namely, for each sequence $V$ of length $8$, such that $1 \leq V_i \leq D, 0 \leq i \leq 7$ We need to find the sum $$\sum f(V_0, V_1) f(V_0, V_3) f(V_0, V_4) f(V_1, V_5) f(V_1, V_2) f(V_2, V_3) f(V_2, V_6) f(V_6, V_5) f(V_6, V_7) f(V_7, V_4) f(V_4, V_5) f(V_7, V_3)$$
Where $f(i, j)$ is value given in input matrix. I coded program to calculate this but it seems that as $D$ is becoming larger than $6$ the program is very slow, so I was thinking if there is some mathematical method to optimize this sum.
I tried rewriting each element of the sum separately but it didn't really work.
Let $\mathcal{S}$ be the sum at hand. It can be computed by constructing several helper rank-3 tensors. Each rank-3 tensor takes $O(D^3)$ storage and about $O(D^4)$ steps of summations.
The procedure is given below:
Sum over $V_0$, construct the rank-3 tensor $$A(V_1,V_3,V_4) = \sum_{V_0} f(V_0,V_1)f(V_0,V_3) f(V_0,V_4)$$
Sum over $V_2$, construct the rank-3 tensor $$B(V_1,V_3,V_6) = \sum_{V_2} f(V_1,V_2) f(V_2,V_3) f(V_2, V_6)$$
Sum over $V_5$, construct the rank-3 tensor $$C(V_1,V_4,V_6) = \sum_{V_5} f(V_1,V_5)f(V_4,V_5)f(V_6,V_5)$$
Sum over $V_7$, construct the rank-3 tensor $$D(V_3,V_4,V_6) = \sum_{V_7} f(V_6,V_7) f(V_7,V_3) f(V_7,V_4)$$ Notice $D(u,v,w) = B(w,u,v)$, we can reuse the rank-3 tensor $B$ without actually compute $D$.
Sum over $V_1$, construct the rank-3 tensor $$E(V_3,V_4,V_6) = \sum_{V_1} A(V_1,V_3,V_4) B(V_1,V_3,V_6) C(V_1,V_4,V_6)$$
The desired sum will be the contraction of $D$ and $E$. i.e
$$\mathcal{S} = \sum_{V_3,V_4,V_6} D(V_3,V_4,V_6) E(V_3,V_4,V_6)$$
Side note
In case someone wonder how do I construct such an algorithm. I use a software to render the dependence among the variables into a directed graph. I then stare at the graph long enough until the "building blocks" of the graph is identified. Since the degree of all the nodes is $3$, it is not a big surprise that we can "unwind" the dependence using rank-3 tensors.