What does the first sentence mean? Does it mean that $m_j \equiv y_i \pmod{i}$ for all i,j?

Also you write $\mathbb{Z}_q$ in one place and $\mathbb{F}_q$ in another. These are not the same when $q$ is not prime. I assume you mean the latter?

How do we define the "number of collisions" of a function? $\sup_A |f^{-1}(\{A\})| - 1$? $\left|\bigcup_A f^{-1}(\{A\})\right|$? $|\{A \; | \; |f^{-1}(\{A\})| > 1|$? Something else? Obviously that will have a big effect on what the expected value is.

I don't understand "since a random matrix is almost a full rank matrix, I expect the number of collisions to be very high." Seems like the lower the rank of the $S_i$, the more collisions.

Okay, looks like I did miss that the OP is willing to consider multiplications the same as additions. However, Horner's method is not the correct answer either. For instance it would use 256 multiplications to evaluate x^256, which is very suboptimal.

Aside from the n=1 case, do you have any evidence that this is ever possible?

I can confirm that the non-primes up to 20 together with 24, 30, 34, 36, 42, and 60 are the only examples up to $10^8$.