arxiv: 2605.10682 · v1 · submitted 2026-05-11 · 🪐 quant-ph · cs.FL

Recognition: 2 theorem links

· Lean Theorem

On the Simulation Cost of Quantum Finite Automata

Junde Wu, Zeyu Chen

Pith reviewed 2026-05-12 05:24 UTC · model grok-4.3

classification 🪐 quant-ph cs.FL

keywords quantum finite automatasimulation coststrict cutpointsign-rankprepare-test frameworkquantum advantageone-way automatafinite automata

0 comments

The pith

A one-way finite automaton with c classical states and q-dimensional quantum register has exact probabilistic simulation cost Θ(c q²), while an n-dimensional measure-once one-way quantum finite automaton has worst-case cost Θ(n²).

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes exact probabilistic simulation cost as the natural quantitative measure of quantum advantage for finite automata under strict cutpoints. It proves sharp bounds for two models: hybrid classical-quantum one-way automata require simulation resources that scale as Θ(c q²), and pure measure-once quantum automata require Θ(n²) in the worst case. These results matter because they supply concrete numbers that separate quantum from classical behavior in a simple computational setting. The proofs rely on a prepare-test framework that isolates how input prefixes create operator degrees of freedom and how suffixes turn them into acceptance tests, then recast the same obstruction via the sign-rank of finite matrices.

Core claim

Under strict cutpoints the exact probabilistic simulation cost of a one-way finite automaton with c classical states and a q-dimensional quantum register is Θ(c q²), while the worst-case cost for an n-dimensional measure-once one-way quantum finite automaton is Θ(n²). The argument proceeds by constructing a prepare-test framework in which prefixes generate the relevant real operator degrees of freedom and suffixes convert them into strict-cutpoint tests; the same separation is then expressed as a finite sign-rank problem, to which Forster’s spectral method applies directly.

What carries the argument

The prepare-test framework, which assigns real operator degrees of freedom to input prefixes and converts them via suffixes into strict-cutpoint tests, together with its equivalent reduction to the sign-rank of finite matrices.

If this is right

Quantum advantage for one-way automata under strict cutpoints is quadratic in the quantum dimension.
The same quadratic obstruction appears for both hybrid classical-quantum and pure quantum models.
These one-way bounds sit beside known two-way separations to produce a clean hierarchy of finite-automata quantum advantage.
Exact probabilistic simulation cost is the appropriate figure of merit for comparing classical and quantum automata when acceptance thresholds are strict.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The quadratic scaling may constrain how much practical speedup quantum automata can deliver on resource-limited hardware.
Similar prepare-test and sign-rank techniques could be applied to other quantum models whose acceptance is decided by cutpoints.
Small explicit automata could be enumerated to test whether the Θ(n²) bound is already visible at low dimension.
The hierarchy suggests that moving from one-way to two-way models changes the nature of the quantum advantage rather than merely its magnitude.

Load-bearing premise

The prepare-test framework together with the reduction to finite sign-rank matrices fully captures every degree of freedom required for strict-cutpoint simulation, with no hidden restrictions on automaton form or input alphabet.

What would settle it

An explicit n-dimensional measure-once one-way quantum finite automaton whose strict-cutpoint language cannot be simulated by any probabilistic automaton with o(n²) states, or conversely an automaton whose language admits simulation with only O(n) states.

read the original abstract

This paper identifies exact probabilistic simulation cost as the natural quantitative measure of quantum advantage for finite automata under strict cutpoints. It gives sharp simulation laws for two representative models. A one-way finite automaton with $c$ classical states and a $q$-dimensional quantum register has exact probabilistic simulation cost $\Theta(cq^2)$, while an $n$-dimensional measure-once one-way quantum finite automaton has worst-case cost $\Theta(n^2)$. The proofs develop a prepare--test framework, in which prefixes generate the relevant real operator degrees of freedom and suffixes convert them into strict-cutpoint tests. The same obstruction is recast through finite sign-rank matrices, clarifying the role of Forster's spectral method. Placed beside the surrounding two-way separations, these results give a clean hierarchy of finite-automata quantum advantage.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper pins down exact probabilistic simulation costs for one-way quantum automata with matching Θ bounds via a prepare-test framework.

read the letter

The key thing to know is that this paper establishes sharp simulation costs for one-way quantum finite automata. A classical one-way automaton with c states and a q-dimensional quantum register has exact probabilistic simulation cost Θ(c q²). An n-dimensional measure-once one-way quantum finite automaton has worst-case cost Θ(n²). These bounds come from a prepare-test framework where prefixes generate operator degrees of freedom and suffixes create strict-cutpoint tests, with the lower bound via sign-rank and Forster's spectral method. This is new. The framework and the exact Θ results do not appear in the cited prior work. It does well by giving a quantitative measure of quantum advantage and fitting it into a larger hierarchy with two-way results. The argument looks consistent. The stress-test finds no internal gaps or unstated restrictions on the input alphabet or automaton form. The reduction seems to capture the necessary degrees of freedom. A possible soft spot is that everything is for one-way models and strict cutpoints. Extending to other variants might require more work, but that is not a flaw in what is claimed. This is for researchers in quantum automata and related areas like communication complexity. A reader looking for precise bounds rather than existence proofs will find value here. It deserves peer review. The results are specific enough and the method is clear enough that referees can check the details and see if the bounds hold in full generality.

Referee Report

2 major / 2 minor

Summary. The paper defines exact probabilistic simulation cost as a quantitative measure of quantum advantage for finite automata under strict cutpoints. It establishes two sharp results: a one-way finite automaton with c classical states and a q-dimensional quantum register has simulation cost Θ(c q²), while an n-dimensional measure-once one-way quantum finite automaton has worst-case simulation cost Θ(n²). The proofs rely on a prepare-test framework that generates operator degrees of freedom from prefixes and converts them to strict-cutpoint tests via suffixes, together with a reduction to finite sign-rank matrices that invokes Forster's spectral method for the matching lower bounds.

Significance. If the derivations hold, the results supply a clean hierarchy of quantum advantage for one-way models that complements existing two-way separations. The prepare-test framework and sign-rank reduction are presented as parameter-free and directly capture the relevant degrees of freedom, providing falsifiable Θ statements rather than asymptotic upper or lower bounds alone.

major comments (2)

[§3] §3, Definition 3.2 and Theorem 3.4: the prepare-test reduction claims to capture all operator degrees of freedom for strict-cutpoint simulation, but the argument appears to restrict the input alphabet to a fixed finite size without explicit justification that the Θ(c q²) bound remains invariant under alphabet extension.
[§4] §4, Eq. (17) and the application of Forster's theorem: the lower-bound construction via finite sign-rank matrices assumes that the matrix entries are exactly the acceptance probabilities under the strict cutpoint; it is unclear whether the spectral gap remains positive when the cutpoint is allowed to approach 1/2 from above, which would be needed for the worst-case claim.

minor comments (2)

The notation for the quantum register dimension q versus the MO-1QFA dimension n is introduced without a consolidated table; a small comparison table would improve readability.
Several citations to prior work on two-way automata (e.g., the surrounding separations mentioned in the abstract) are referenced only by author-year; full bibliographic details should be added.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the detailed and constructive report. The two major comments are addressed point by point below. We will incorporate clarifications into the revised manuscript.

read point-by-point responses

Referee: [§3] §3, Definition 3.2 and Theorem 3.4: the prepare-test reduction claims to capture all operator degrees of freedom for strict-cutpoint simulation, but the argument appears to restrict the input alphabet to a fixed finite size without explicit justification that the Θ(c q²) bound remains invariant under alphabet extension.

Authors: We agree that the invariance under alphabet extension merits explicit justification. The prepare-test framework in Definition 3.2 is formulated for an arbitrary finite alphabet Σ. The operator degrees of freedom generated by prefixes are spanned by the action of the transition operators on the q-dimensional register; this yields a real vector space of dimension at most q² irrespective of |Σ|. Additional symbols simply enlarge the set of available operators without increasing the dimension of the relevant subspace beyond this bound. Consequently the simulation-cost upper and lower bounds of Theorem 3.4 remain unchanged. We will insert a short clarifying paragraph immediately after the statement of Theorem 3.4. revision: yes
Referee: [§4] §4, Eq. (17) and the application of Forster's theorem: the lower-bound construction via finite sign-rank matrices assumes that the matrix entries are exactly the acceptance probabilities under the strict cutpoint; it is unclear whether the spectral gap remains positive when the cutpoint is allowed to approach 1/2 from above, which would be needed for the worst-case claim.

Authors: The construction underlying Eq. (17) employs a fixed strict cutpoint λ = 2/3 for every automaton in the family. Acceptance probabilities are therefore required to lie in [0,1/3] ∪ [2/3,1], producing a uniform spectral gap of 1/3 that is independent of any limiting process toward 1/2. Forster’s theorem is applied directly to the resulting sign matrix whose entries are bounded away from the cutpoint; the spectral gap therefore stays positive. The worst-case statement is taken over all measure-once QFAs that admit some strict cutpoint (including the fixed λ = 2/3 used here), which is the standard setting for such results. We will add a sentence after Eq. (17) emphasizing that the cutpoint is held constant and the gap is uniform. revision: yes

Circularity Check

0 steps flagged

No circularity: bounds derived from independent prepare-test framework and external spectral methods

full rationale

The paper constructs the simulation cost bounds via a prepare-test framework that explicitly generates operator degrees of freedom from input prefixes and converts them to strict-cutpoint tests via suffixes, then reduces the obstruction to finite sign-rank matrices using Forster's spectral method. These steps are presented as first-principles constructions without any reduction to fitted parameters, self-definitions, or load-bearing self-citations. The Θ(c q²) and Θ(n²) results follow directly from counting the real degrees of freedom and applying the external matrix-rank lower bound, with no evidence that the claimed costs are equivalent to the inputs by construction. The derivation is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on standard linear-algebra facts about operator degrees of freedom and on the applicability of sign-rank techniques; no new free parameters, ad-hoc axioms, or invented entities are introduced in the abstract.

axioms (2)

standard math The space of real linear operators on a q-dimensional Hilbert space has dimension q², and prefixes of the input can independently prepare any such operator.
Invoked to count the degrees of freedom that the classical simulator must track.
domain assumption Strict cutpoints convert operator equality into a yes-no test that forces the simulator to distinguish all independent real parameters.
Central to the prepare-test reduction; stated as part of the model definition.

pith-pipeline@v0.9.0 · 5424 in / 1547 out tokens · 55451 ms · 2026-05-12T05:24:29.867925+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear
A one-way finite automaton with c classical states and a q-dimensional quantum register has exact probabilistic simulation cost Θ(c q²)
IndisputableMonolith/Foundation/AbsoluteFloorClosure.lean absolute_floor_iff_bare_distinguishability unclear
prepare–test framework, in which prefixes generate the relevant real operator degrees of freedom and suffixes convert them into strict-cutpoint tests

Reference graph

Works this paper leans on

26 extracted references · 26 canonical work pages · 1 internal anchor

[1]

The Quadratic State Cost of Classical Simulation of One-Way Quantum Finite Automata

Z. Chen and J. Wu.The Quadratic State Cost of Classical Simulation of One-Way Quantum Finite Automata. arXiv:2604.07058, 2026

work page internal anchor Pith review Pith/arXiv arXiv 2026
[2]

Moore and J

C. Moore and J. P. Crutchfield. Quantum automata and quantum grammars.Theoretical Computer Science, 237(1–2):275–306, 2000

work page 2000
[3]

Kondacs and J

A. Kondacs and J. Watrous. On the power of quantum finite state automata. InProceedings of the 38th Annual Symposium on Foundations of Computer Science, pages 66–75, 1997

work page 1997
[4]

Ambainis and R

A. Ambainis and R. Freivalds. 1-way quantum finite automata: strengths, weaknesses and generalizations. InProceedings of the 39th Annual Symposium on Foundations of Computer Science, pages 332–341, 1998

work page 1998
[5]

Ambainis and J

A. Ambainis and J. Watrous. Two-way finite automata with quantum and classical states. Theoretical Computer Science, 287(1):299–311, 2002

work page 2002
[6]

Ambainis and A

A. Ambainis and A. Yakaryılmaz. Automata and quantum computing. In J.- ´E. Pin, editor, Handbook of Automata Theory, volume 2, chapter 39, pages 1457–1493. EMS Press, 2021

work page 2021
[7]

Ambainis, A

A. Ambainis, A. Nayak, A. Ta-Shma, and U. Vazirani. Dense quantum coding and quantum finite automata.Journal of the ACM, 49(4):496–511, 2002

work page 2002
[8]

Brodsky and N

A. Brodsky and N. Pippenger. Characterizations of 1-way quantum finite automata.SIAM Journal on Computing, 31(5):1456–1478, 2002

work page 2002
[9]

Bertoni, C

A. Bertoni, C. Mereghetti, and B. Palano. Quantum computing: 1-way quantum automata. InDevelopments in Language Theory, volume 2710 ofLecture Notes in Computer Science, pages 1–20. Springer, 2003

work page 2003
[10]

L. Li, D. Qiu, X. Zou, L. Li, L. Wu, and P. Mateus. Characterizations of one-way general quantum finite automata.Theoretical Computer Science, 419:73–91, 2012

work page 2012
[11]

D. Qiu, L. Li, P. Mateus, and A. Sernadas. Exponentially more concise quantum recognition of non-RMM regular languages.Journal of Computer and System Sciences, 81(2):359–375, 2015

work page 2015
[12]

Zheng, J

S. Zheng, J. Gruska, and D. Qiu. On the state complexity of semi-quantum finite automata. RAIRO – Theoretical Informatics and Applications, 48(2):187–207, 2014

work page 2014
[13]

G. Ludwig. Versuch einer axiomatischen Grundlegung der Quantenmechanik und allge- meinerer physikalischer Theorien.Zeitschrift f¨ ur Physik, 181(3):233–260, 1964

work page 1964
[14]

Turakainen

P. Turakainen. Generalized automata and stochastic languages.Proceedings of the Amer- ican Mathematical Society, 21(2):303–309, 1969

work page 1969
[15]

Dwork and L

C. Dwork and L. Stockmeyer. A time-complexity gap for two-way probabilistic finite-state automata.SIAM Journal on Computing, 19(6):1011–1023, 1990

work page 1990
[16]

Yakaryılmaz and A

A. Yakaryılmaz and A. C. C. Say. Languages recognized with unbounded error by quantum finite automata. InComputer Science Symposium in Russia, volume 5675 ofLecture Notes in Computer Science, pages 356–367. Springer, 2009

work page 2009
[17]

J. Forster. A linear lower bound on the unbounded error probabilistic communication complexity.Journal of Computer and System Sciences, 65(4):612–625, 2002

work page 2002
[18]

M. O. Rabin. Probabilistic automata.Information and Control, 6(3):230–245, 1963. 18

work page 1963
[19]

Paz.Introduction to Probabilistic Automata

A. Paz.Introduction to Probabilistic Automata. Academic Press, 1971

work page 1971
[20]

Watrous.The Theory of Quantum Information

J. Watrous.The Theory of Quantum Information. Cambridge University Press, 2018

work page 2018
[21]

Bengtsson and K

I. Bengtsson and K. ˙Zyczkowski.Geometry of Quantum States: An Introduction to Quan- tum Entanglement. Cambridge University Press, second edition, 2017

work page 2017
[22]

J. M. Lee.Introduction to Smooth Manifolds. Springer, second edition, 2012

work page 2012
[23]

V. N. Vapnik.Statistical Learning Theory. Wiley, 1998

work page 1998
[24]

Anthony and P

M. Anthony and P. L. Bartlett.Neural Network Learning: Theoretical Foundations. Cam- bridge University Press, 1999

work page 1999
[25]

Paturi and J

R. Paturi and J. Simon. Probabilistic communication complexity.Journal of Computer and System Sciences, 33(1):106–123, 1986

work page 1986
[26]

Linial, S

N. Linial, S. Mendelson, G. Schechtman, and A. Shraibman. Complexity measures of sign matrices.Combinatorica, 27(4):439–463, 2007. 19

work page 2007