Quadratic sum of Gauss integers

If $a$ is odd we need at most two, because $$ a+2bi=1\cdot(a+2bi)=u_1u_2 $$ is a factorization into parts $u_1=1$ and $u_2=a+2bi$ such that $u_1\pm u_2$ have even real and imaginary parts. This means that we can solve for $z_1$ and $z_2$ from $$ u_1u_2=z=z_1^2+z_2^2=(z_1+iz_2)(z_1-iz_2) $$ (using the ansatz $u_1=z_1+iz_2$, $u_2=z_1-iz_2$) as $$ z_1=\frac{u_1+u_2}2=\frac{a+1}2+bi,\qquad z_2=\frac{u_1-u_2}{2i}=-b+i\frac{a-1}2. $$

And if $a$ is even we need at most one more, because $a-1$ is then odd.

So at this point we have $n\le3$.

It seems to me $z=2+2i$ cannot be written as a sum of two squares (study real and imaginary parts modulo four and check all the cases), meaning that $n=3$ is the answer.

---

Edit: Alternatively we can verify that no factorization of $2+2i=-i(1+i)^3$ leads to a factorization with both factors having the same parity in their real and imaginary parts. Working the above trick backwards then shows that it cannot be written as a sum of two squares. My testing suggests that $z=a+2bi$ is a sum of two Gaussian squares unless its real and imaginary parts are both congruent to $2$ modulo $4$.

---

See Gerry Myerson's answer to a newer question for more.

(This is not a full answer, but too long for a comment)

Claim: $n\leq 8$.

Given $a+2bi\in\mathbb Z[i]$ for some $a,b\in\mathbb Z$. By Langrange's theorem, we have: $$|a|=x_1^2+x_2^2+x_3^2+x_4^2$$ $$|b|=y_1^2+y_2^2+y_3^2+y_4^2$$ for some $x_i,y_i\in\mathbb Z$. Now, define $$c_a=\begin{cases}1&a\geq 0\\i&a<0\end{cases}\qquad c_b=\begin{cases}1+i&b\geq 0\\1-i&b<0\end{cases}$$ Then $$\begin{align} &\quad (c_ax_1)^2+(c_ax_2)^2+(c_ax_3)^2+(c_ax_4)^2+(c_by_1)^2+(c_by_2)^2+(c_by_3)^2+(c_by_4)^2 \\ &=c_a^2\left(x_1^2+x_2^2+x_3^2+x_4^2\right) + c_b^2\cdot\left(y_1^2+y_2^2+y_3^2+y_4^2\right) \\ &=c_a^2\cdot |a| + c_b^2\cdot |b| \\ &=a+2bi \end{align}$$ (Check, that the last equation holds for all four cases of $(c_a,c_b)$.)