Natural Computing Computer Science Applications
Two-way affine automata can verify every language
Abstract
When used as verifiers in Arthur-Merlin systems, two-way quantum finite automata can verify membership in all languages with bounded error with double-exponential expected running time, which cannot be achieved by their classical counterparts. We obtain an analogous result for affine automata with single-exponential expected time. Using the equivalent nondeterministic formulation adopted throughout the paper, we investigate the language recognition power of two-way affine nondeterministic automata under weak and strong bounded-error criteria. We show that every language over every fixed finite alphabet can be weakly or strongly recognized with bounded error by suitable two-way affine nondeterministic automata, via two protocols: a weak protocol uses a single affine register and reads the input once, and a strong protocol uses two affine registers. These results reflect the remarkable capabilities of affine finite automata in this setting.