Rational-Valued Affine Verifiers in Arthur--Merlin Proof Systems

Affine automata provide a finite-state computational model that preserves the linear-algebraic structure of quantum computation while operating entirely over the reals. Recent work has shown that affine automata can far surpass classical probabilistic finite-state verifiers. However, prior constructions relied on arbitrary real-valued transition matrices, leaving open whether the observed power stems from the affine mechanism itself or from computational resources implicitly encoded in irrational or infinite-precision parameters. This paper studies one-way and two-way automata with deterministic and affine states as verifiers in Arthur–Merlin proof systems under the restriction that every affine transition matrix has rational entries, and shows that the resulting rational model still supports the main verification advantages of affine finite-state verification. At the one-way level, we verify benchmark nonregular languages that are provably hard or impossible for classical two-way probabilistic verifiers. At the two-way level, we achieve weak verification of every Turing-recognizable language, strong bounded-error verification for every language in $\mathbf{A}\mathbf{T}\mathbf{I}\mathbf{M}\mathbf{E}(2^{O(n)})$, and perfect-completeness strong verification for every language in $\mathbf{P}\mathbf{S}\mathbf{P}\mathbf{A}\mathbf{C}\mathbf{E}$. These results establish that the remarkable verification power of affine finite-state automata is structural.