4 papers · 1 filter
Exact Separation of Words via Trace Geometry
Zeyu Chen, Junde Wu
A basic question in the study of measure-once quantum finite automata is whether two distinct input words can be separated with certainty. The exact separation problem reduces to a…
Rational-Valued Affine Verifiers in Arthur--Merlin Proof Systems
Zeyu Chen, Junde Wu
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…
The Quadratic State Cost of Classical Simulation of One-Way Quantum Finite Automata
Zeyu Chen, Junde Wu
Generalized finite automata (GFAs), probabilistic finite automata (PFAs), and one-way general quantum finite automata (1gQFA) recognize the same strict-cutpoint languages, but the…
Two-way affine automata can verify every language
Zeyu Chen, Abuzer Yakaryılmaz
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…