5 papers
On the Simulation Cost of Quantum Finite Automata
Zeyu Chen, Junde Wu
This paper identifies exact probabilistic simulation cost as the natural quantitative measure of quantum advantage for finite automata under strict cutpoints. It gives sharp simula…
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…