Two-way affine automata can verify every language

Zeyu Chen, Abuzer Yakaryılmaz

TL;DR

This paper proves that two-way affine finite automata (2ADfA) are surprisingly powerful verifiers: they can verify membership in any language with bounded error. Crucially, they achieve this in single-exponential expected time, a significant leap over the double-exponential time required by their quantum counterparts.

What Problem Does This Paper Address?

In the world of computational complexity, we often ask what a machine with very limited memory can accomplish. A "finite automaton" is the poster child for limited memory—it has a constant number of states regardless of how long the input string is.

When these automata act as verifiers in an Arthur-Merlin (AM) system, the stakes change. Merlin (an all-powerful but untrustworthy prover) tries to convince Arthur (the limited-memory verifier) that a string belongs to a specific language. While classical finite automata are quite restricted in what they can verify, quantum finite automata (2QCFAs) were previously shown to be able to verify any language. However, the quantum approach is incredibly slow, requiring "double-exponential" time ($2^{2^n}$).

The authors investigate whether affine automata—which use a different mathematical framework for interference than quantum systems—can bridge this gap and provide more efficient verification.

Methods

The authors define and utilize Two-way Affine Finite Automata (2ADfA). Unlike quantum states that use the $\ell_2$-norm (where the squares of amplitudes sum to 1), affine states use the $\ell_1$-norm (where the absolute values of entries sum to 1).

The core of their method involves:

  1. Real Number Encoding: They encode the entire membership information of a language $L$ into a single real number, $\alpha_L$.
  2. Nondeterministic Guessing: They use a nondeterministic version of the automaton (2ANfA). Merlin provides a sequence of "guesses" for the digits of $\alpha_L$ corresponding to the input string.
  3. The "Weak" Protocol: Using a single affine register, the verifier reads the input once. If Merlin lies about a digit, the affine state amplifies this error, leading to a high probability of rejection.
  4. The "Strong" Protocol: To ensure the machine doesn't run forever on non-member strings, they add a second affine register. This register acts as a "probabilistic timer," executing a procedure that rejects the input with an exponentially small probability in each iteration, forcing the computation to terminate in expected exponential time.

Datasets

Not discussed in the paper. As a theoretical work in automata theory, the results are proven mathematically rather than through empirical testing on datasets.

Key Insights and Ideas

  • Affine vs. Quantum Power: The "aha moment" is that the $\ell_1$-norm constraint of affine systems allows for a specific type of "weighting" and interference that is more efficient for this verification task than quantum interference.
  • Arithmetic in the Register: The verifier essentially performs iterative arithmetic ($6 \cdot \beta_{i-1} - g_{i-1}$) within the affine register to track the validity of Merlin's claims.
  • Error Amplification: If Merlin provides even one incorrect digit for the language's characteristic real number, the absolute value of the register's state grows significantly, eventually dominating the "correct" branch and leading to rejection.
  • Exponential Speedup: By moving from quantum to affine, the expected running time drops from double-exponential ($2^{2^n}$) to single-exponential ($2^n$).

Key Results

  • Verification of All Languages: The paper proves that for any binary or $r$-ary language, there exists a 2ANfA that can verify it with an error bound arbitrarily close to zero.
  • Time Complexity: For member strings, the verification takes $O(2^{|w|})$ time. For the "strong" protocol, the expected running time for any input is also $O(2^{|w|})$.
  • Register Efficiency: "Weak" verification requires only one affine register; "Strong" verification (ensuring termination) requires only two.

Limitations and Future Work

  • Real-Valued Transitions: The current proofs rely on the ability of the automaton to use any real number in its transition matrices. In practical computing, we are limited to rational numbers. The authors suggest that investigating the power of 2ADfAs restricted to rational-valued transitions is a vital next step.
  • Expected vs. Worst-Case Time: While the expected time is single-exponential, the paper notes that some branches of the computation could still technically run for a very long time, though with vanishingly small probability.

Summary updated

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 the same result for affine automata with single-exponential expected time. We show that every binary (and r-ary) language is verified by some two-way affine finite automata verifiers by presenting two protocols: A weak verification protocol uses a single affine register and the input is read once; and, a strong verification protocol uses two affine registers. These results reflects the remarkable verification capabilities of affine finite automata.
BibTeX
@misc{chen2025two,
  author = {Zeyu Chen and Abuzer Yakaryılmaz},
  title = {{Two-way affine automata can verify every language}},
  year = {2025},
  eprint = {2502.12879},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2502.12879},
}
Figure