We study the algebraic complexity of the Hamiltonian polynomials $HC_n$ (and of some of its generalizations) over finite fields $\frak k$ of characteristic $2$. We show that when restricted to {\em unitary matrices}, $HC_n$ is in $\bP$ (can be computed in polynomial time) and is also in Valiant's $\bVP$. We show that this result is best possible in the following sense: $HC_n$ restricted to $1$-semi-unitary matrices $M$ with rank $rg(M\cdot M^T - {\mathbf{1}}_n) =1$ is $\bVNP$-complete for $\bVP$-reductions allowing subroutines.