Five-Layer Circuits Need n^{√n/400} Gates for Iterated Matrix Multiplication

The top-left entry of a product of (n) matrices is straightforward to define. The harder question is how large a circuit must be if it is restricted to five alternating layers of sums and products. An OpenAI manuscript claims that, in the balanced case—(n) matrices, each (n\times n)—every such circuit needs at least $n^{\sqrt{n}/400}$ gates for sufficiently large (n), over any field of characteristic zero.

The restriction is specific. Read from output toward inputs, the layers are sum, product, sum, product, sum. The circuit must be syntactically homogeneous: at each product gate, input degrees add; at each sum gate, all inputs have the same formal degree. Even if terms cancel and a gate computes zero, it retains its assigned degree. This is stronger than requiring only that the final polynomial be homogeneous.

But the model still permits flexibility that could make lower bounds harder. A bottom linear form may involve all variables, and gates may be shared, with any finite number of inputs or outputs. The size counts gates, including leaves—not wires. The claimed bound concerns this model, not unrestricted-depth circuits: the manuscript notes that unrestricted depth can compute the polynomial with polynomially many gates.

The theorem’s scale is $n^{\sqrt{n}/400}$, not an exact gate count. Its threshold for “sufficiently large” (n) is absolute and independent of the field. The stated advance is obtaining this square-root exponent in the balanced width-equals-degree setting without restricting bottom support or disallowing shared gates.

The top-left entry of a matrix product expands as a sum over paths through the matrices. For three (2\times2) matrices (A,B,C), a path starts at row 1, chooses intermediate indices (i) and (j), then ends at column 1. Its monomial is $A_{1i}{B}_{ij}{C}_{j1}$. Since each intermediate index can be 1 or 2, there are four paths and four degree-three monomials; their sum is the top-left entry of (ABC).

In the balanced (n)-matrix case, there are (n-1) internal choices, each with (n) possibilities, giving $n^{n-1}$ paths in the expansion. Every path contributes one variable from each matrix, so every monomial has degree (n). This expansion clarifies the target polynomial, but it does not by itself prove that a five-layer circuit needs many gates.

The manuscript also gives a construction, which explains why a square root appears in the exponent. Divide the chain into blocks of about $\sqrt{n}$ matrices. For nine matrices, for example, use three blocks of three. An entry of each block product is itself a sum over internal paths; in this example, each block entry sums over two internal indices, giving (9^2) paths.

The full product then sums over indices at the block boundaries. With block products (Y^1,Y^2,Y^3), the target entry has terms of the form $Y_{1a}^{(1)}{Y}_{ab}^{(2)}{Y}_{b1}^{(3)}$, summed over (a) and (b). Crucially, the same computed block entry can be reused across many such terms. Choosing block length and block count on the square-root scale balances the work. The manuscript proves an upper bound of $n^{\sqrt{n}+4}$ gates, for (n\ge2), over every field.

For the lower bound, the manuscript assigns a rank to a polynomial using a mixed differentiation-and-multiplication operator. It splits whole matrix layers into two disjoint variable groups, (V) and (U), and keeps a slice with specified degrees in each group. It then substitutes differentiation for the (V) variables and multiplication for the (U) variables. In the example, (v^2u) determines the operator $u\partial /\partial v$; applying it to (v^2u) gives (2vu^2).

On spaces with fixed starting degrees, the construction gives a finite linear map whose rank counts independent output directions. The degree projection is essential: the full substitution respects products, but the projected map need not. Differentiation and multiplication commute here because they act on disjoint variable groups.

The circuit-side argument seeks a bottleneck for this map: once input directions pass through a smaller intermediate space, later linear operations cannot restore the lost dimensions. The manuscript’s proof roadmap resolves homogeneous factors by their degree in (V), then applies derivative-heavy factors first. Choosing starting degrees can shrink intermediate spaces; because actual degrees are integers, they may not match their ideal proportional shares. The resulting discrepancies contribute to a rank saving.

For an oversized factor, the proof expands one occurrence into products of linear forms, at a cost of at most one additional factor of circuit size, even when gates are shared. These steps lead to the stated technical estimate, rather than a full derivation here:

Here (S) is circuit size, (D) is the dimension of the operator’s source space, and (C) is an absolute constant.

The other side of the argument is to show that the matrix-product polynomial has large rank under the same operator. For a map (F), form $H=F^{\ast }F$. This matrix is positive semidefinite and has the same rank as (F). If its nonzero eigenvalues are ${\lambda }_1,\dots ,{\lambda }_r$, Cauchy–Schwarz gives

and therefore

For eigenvalues (3,3,0), this ratio is (36/18=2).

The inequality is simple; estimating the two traces for the manuscript’s operator is the hard part. The manuscript interprets them as weighted path counts: the first involves individual paths, the second quadruples of paths. Its counting argument considers two pairing patterns at each internal matrix layer. Equal neighboring patterns leave two vertex labels free, or (n^2) choices; when the pattern changes, the constraints force all four labels to agree, leaving (n) choices—a local factor of (1/n). The full estimates also handle weights, repeated coordinates, isolated patterns, endpoints, and the order of (V)- and (U)-layers. These are proof mechanics summarized here, not a derivation of the estimates.

The resulting bound is $R(\mathrm{IMM})\ge D\exp (-C^{\prime }\sqrt{n})$. Comparing it with the circuit-side estimate cancels the common source-space dimension (D), forcing $S\ge n^{\sqrt{n}/400}$ for sufficiently large (n). Although the trace argument uses complex inner products, the operator has integer entries in ordinary monomial bases. Its nonzero integer minors remain nonzero over every characteristic-zero field, so the rank bound transfers.

Together with the block construction, the result places the minimum gate count between $n^{\sqrt{n}/400}$ and $n^{\sqrt{n}+4}$. The constants differ, so this is not an exact count: it establishes a $\sqrt{n}$ scale in the exponent for five syntactically homogeneous layers.