Non-commutative circuits and the sum-of-squares problem
Authors: Hrubeš Pavel , Wigderson Avi , Yehudayoff Amir 
Published: February 2011

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
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="left-parenthesis 0.1 right-parenthesis left-parenthesis x 1 squared plus x 2 squared plus midline-horizontal-ellipsis plus x Subscript k Superscript 2 Baseline right-parenthesis dot left-parenthesis y 1 squared plus y 2 squared plus midline-horizontal-ellipsis plus y Subscript k Superscript 2 Baseline right-parenthesis equals f 1 squared plus f 2 squared plus midline-horizontal-ellipsis plus f Subscript n Superscript 2 Baseline comma">

(
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.