  We consider the multiplicative complexity of Boolean functions with multiple
bits of output, studying how large a multiplicative complexity is necessary and
sufficient to provide a desired nonlinearity. For so-called $\Sigma\Pi\Sigma$
circuits, we show that there is a tight connection between error correcting
codes and circuits computing functions with high nonlinearity. Combining this
with known coding theory results, we show that functions with $n$ inputs and
$n$ outputs with the highest possible nonlinearity must have at least $2.32n$
AND gates. We further show that one cannot prove stronger lower bounds by only
appealing to the nonlinearity of a function; we show a bilinear circuit
computing a function with almost optimal nonlinearity with the number of AND
gates being exactly the length of such a shortest code.
  Additionally we provide a function which, for general circuits, has
multiplicative complexity at least $2n-3$.
  Finally we study the multiplicative complexity of "almost all" functions. We
show that every function with $n$ bits of input and $m$ bits of output can be
computed using at most $2.5(1+o(1))\sqrt{m2^n}$ AND gates.
