Solution (source code)

= Solution

The average of $z_jz_k^*z_{j'}^*z_{k'}$ vanishes unless the exponent of every independent fourth root is balanced modulo four. The surviving index patterns are $j=k,\ j'=k'$ and $j=j',\ k=k'$. Their intersection $j=k=j'=k'$ has been counted twice. Hence, writing
$$
D=\sum_{j=1}^d|j\rangle\langle j|\otimes|j\rangle\langle j|,
$$
the phase average is
$$
\sigma=\frac1{d^2}\left(I\otimes I
+d|\Phi^+\rangle\langle\Phi^+|-D\right).
$$
Solving for the projector onto the <maximally entangled state> gives
$$
\boxed{
|\Phi^+\rangle\langle\Phi^+|
=d\sigma-\frac1dI\otimes I+\frac1dD}.
$$