Could one build a symmetric encryption system that is competitive with the AES by randomly applying Toffoli-like gates?
It seems plausible that one builds a symmetric encryption system competitive with AES by randomly applying Toffoli(-like) gates as restricted in the question. I do not know that it has been studied.

Paraphrasing the question, it constructs a block cipher with 128-bit block and 128-bit key similar in function to AES-128 as follows:


number inputs as $b_i$ with $0\le i&lt;128$ for block bits and $128\le i&lt;256$ for key bits
repeat $r$ times


pick random distinct indices $i,j,k$ with $(k\ge128)\implies(i\ge128)\wedge(j\ge128)$
apply a random Toffoli-like gate to $(b_i,b_j,b_k)$



In the end, the result is the 128-bit $x_i$ with $0\le i&lt;128$. The rule $(k\ge128)\implies(i\ge128)\wedge(j\ge128)$ insures that for any fixed key, the block cipher is reversible.

Seen from far away with blurry vision, there are similarities between this construction and AES-128: both are iterated permutation-substitution ciphers with reversible key transformation along the rounds, and 256 variables.  If we chose $i$, $j$, $k$ randomly until acceptable, a key bit is chosen as $z$ (the potentially changed bit) with odds about $1/5$, which grossly mimics AES spending significantly less computational effort on key scheduling than on data encryption.

I do not know the number of rounds $r$ making the block cipher secure; nor a technique to derive this. But I would not be astonished if it was markedly lower than $100000$.