Hankel Submatrices with Bounded Word Length: Dimension Tradeoffs in Probabilistic and Quantum Automata

We characterize the largest admissible side length of fixed-margin square Hankel submatrices generated by probabilistic realizations on a $d$-point carrier and quantum linear realizations on a $d$-dimensional Hilbert space, when prefix and suffix word lengths are bounded by $T$. Using a four-symbol transition alphabet shared by all selected rows and columns, we show that, for fixed margins ${\lambda }_2>0$ and ${\lambda }_1+{\lambda }_2<1$, the corresponding side lengths satisfy $\ln N_{\mathsf{Q},4}={\mathrm{\Theta }}_{{\lambda }_1,{\lambda }_2}(\min \{d^2,T\})$ for completely positive trace-preserving (CPTP) quantum realizations and $\ln N_{\mathsf{S},4}={\mathrm{\Theta }}_{{\lambda }_1,{\lambda }_2}(\min \{d,T\})$ for probabilistic automata. Four unitary and four permutation transition maps attain the corresponding orders. At zero false-acceptance tolerance (${\lambda }_2=0$ with $0\le {\lambda }_1<1$), all four model classes satisfy $\ln N=\mathrm{\Theta }(\min \{\ln d,T\})$. The upper bounds follow from state-space packing and word counting, while the lower bounds combine explicit transition tuples with Grassmannian and positive-rate codebooks whose existence follows from the probabilistic method. These results establish sharp dimension–word-length tradeoffs for bounded-word Hankel tables.