We initiate a direction for proving lower bounds on the size of non-commutative arithmetic circuits. This direction is based on a connection between lower bounds on the size of \emph{non-commutative} arithmetic circuits and a problem about \emph{commutative} degree four polynomials, the classical sum-of-squares problem: find the smallest $n$ such that there exists an identity
\begin{equation}
\label{eqn:hwy def}
(x_1^2+x_2^2+\cdots + x_k^2)\cdot (y_1^2+y_2^2+\cdots + y_k^2)= f_{1}^{2}+f_{2}^{2}+\dots +f_{n}^{2} ,
\end{equation}
where each $f_{i} = f_i(X,Y)$ is a bilinear form in $X=\{x_{1},\dots ,x_{k}\}$ and $Y=\{y_{1},\dots, y_{k}\}$. Over the complex numbers, we show that a sufficiently strong \emph{super-linear} lower bound on $n$ in \eqref{eqn:hwy def}, namely, $n\geq k^{1+\epsilon}$ with $\eps >0$, implies an \emph{exponential} lower bound on the size of arithmetic circuits computing the non-commutative permanent.

More generally, we consider such sum-of-squares identities for any \biq\m polynomial $h(X,Y)$, namely
\begin{equation}
\label{eqn:hwy def2}
h(X,Y) = f_{1}^{2}+f_{2}^{2}+\dots +f_{n}^{2} .
\end{equation}
Again, proving $n\geq k^{1+\epsilon}$ in \eqref{eqn:hwy def2} for {\em any} explicit $h$ over the complex numbers
gives an \emph{exponential} lower bound for the non-commutative permanent.
Our proofs relies on several new structure theorems for non-commutative circuits,
as well as a non-commutative analog of Valiant's completeness of the permanent.

We proceed to prove such super-linear bounds in some restricted cases.
We prove that $n \geq \Omega(k^{6/5})$ in \eqref{eqn:hwy def},
if $f_{1 },\dots, f_{n}$ are required to have {\em integer} coefficients.
Over the {\em real} numbers, we construct an explicit \biq\m polynomial $h$ such that $n$ in (\ref{eqn:hwy def2}) must be at least $\Omega(k^{2})$. Unfortunately, these results do not imply circuit lower bounds.

We also present other structural results about non-commutative arithmetic circuits.
We show that any non-commutative circuit computing an \emph{ordered} non-commutative polynomial
can be efficiently transformed to a syntactically multilinear circuit computing that polynomial.
The permanent, for example, is ordered.
Hence, lower bounds on the size of syntactically multilinear circuits computing the permanent imply unrestricted non-commutative lower bounds.
We also prove an exponential lower bound on the size of non-commutative syntactically multilinear circuit computing an explicit polynomial. This polynomial is, however, not ordered and an unrestricted circuit lower bound does not follow.