Non-commutative circuits and the sum-of-squares problem

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 non-commutative arithmetic circuits and a problem about commutative degree-four polynomials, the classical sum-of-squares problem: find the smallest n n such that there exists an identity ( 0.1 ) ( x 1 2 + x 2 2 + ⋯ + x k 2 ) ⋅ ( y 1 2 + y 2 2 + ⋯ + y k 2 ) = f 1 2 + f 2 2 + ⋯ + f n 2 , \begin{equation*} (0.1)\quad \quad (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} , \quad \quad \end{equation*} where each f i = f i ( X , Y ) f_{i} = f_i(X,Y) is a bilinear form in X = { x 1 , … , x k } X=\{x_{1},\dots ,x_{k}\} and Y = { y 1 , … , y k } Y=\{y_{1},\dots , y_{k}\} . Over the complex numbers, we show that a sufficiently strong superlinear lower bound on n n in (0.1), namely, n ≥ k 1 + ϵ n\geq k^{1+\epsilon } with ϵ > 0 \epsilon >0 , implies an 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 biqua- dratic polynomial h ( X , Y ) h(X,Y) , namely ( 0.2 ) h ( X , Y ) = f 1 2 + f 2 2 + ⋯ + f n 2 . \begin{equation*} (0.2) \quad \quad \qquad \quad \quad \quad \quad h(X,Y) = f_{1}^{2}+f_{2}^{2}+\dots +f_{n}^{2} . \quad \quad \qquad \quad \quad \quad \quad \end{equation*} Again, proving n ≥ k 1 + ϵ n\geq k^{1+\epsilon } in (0.2) for any explicit h h over the complex numbers gives an exponential lower bound for the non-commutative permanent. Our proofs rely on several new structure theorems for non-commutative circuits, as well as a non-commutative analog of Valiant’s completeness of the permanent.

We prove such a superlinear bound in one special case. Over the real numbers, we construct an explicit biquadratic polynomial h h such that n n in (0.2) must be at least Ω ( k 2 ) \Omega (k^{2}) . Unfortunately, this result does 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 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 a non-commutative syntactically multilinear circuit computing an explicit polynomial. This polynomial is, however, not ordered and an unrestricted circuit lower bound does not follow.