arxiv: 2604.07058 · v1 · submitted 2026-04-08 · 💻 cs.FL

Recognition: 2 theorem links

· Lean Theorem

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

Junde Wu, Zeyu Chen

Authors on Pith no claims yet

Pith reviewed 2026-05-10 18:00 UTC · model grok-4.3

classification 💻 cs.FL

keywords one-way quantum finite automataprobabilistic finite automatastate complexitystrict-cutpoint languagessimulationVC-dimension

0 comments

The pith

The worst-case state complexity for exact strict-cutpoint simulation of n-state one-way general quantum finite automata by one-way probabilistic finite automata is exactly Θ(n²).

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

The paper establishes the precise state overhead required when converting one-way general quantum finite automata into equivalent classical probabilistic finite automata while preserving exact acceptance probabilities under a strict cutpoint. It gives a constructive upper bound showing that O(n²) probabilistic states always suffice, obtained by converting the quantum mixed-state evolution into a classical transition matrix and then mapping the resulting generalized automaton into a probabilistic one. It also supplies a matching lower bound by exhibiting specific n-state quantum automata that force any simulating probabilistic automaton to use at least n²-1 states, proved via a prepare-and-test scheme combined with a dimension argument. This settles an open question on the simulation cost between these two models. A reader would care because the result quantifies exactly how much extra classical memory is needed to replicate the computational power of these restricted quantum devices.

Core claim

Every n-state 1gQFA admits exact strict-cutpoint simulation by a one-way PFA with O(n²) states via the standard n²-dimensional mixed-state linearization together with an explicit alphabet-preserving construction that converts each k-state GFA into a one-way PFA with at most 2k+6 states; conversely, for every n≥2 there exists an n-state 1gQFA for which every equivalent one-way PFA requires at least n²-1 states, obtained from a prepare-test construction and a Vapnik-Chervonenkis dimension argument. Hence the worst-case probabilistic state cost of exact strict-cutpoint simulation is Θ(n²).

What carries the argument

The n²-dimensional mixed-state linearization of the quantum transition operators, combined with a GFA-to-PFA conversion of linear size and a prepare-test lower-bound instance whose VC-dimension forces quadratic state blowup.

If this is right

Every language recognized by an n-state 1gQFA with strict cutpoint is also recognized by some one-way PFA with O(n²) states.
There exist languages requiring a quadratic blowup when moving from the quantum to the classical probabilistic one-way model.
The three models (GFAs, PFAs, and 1gQFAs) recognize exactly the same strict-cutpoint languages, but the conversion from quantum to probabilistic is tight at quadratic cost.
The upper-bound construction is effective and alphabet-preserving.

Where Pith is reading between the lines

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

Similar quadratic overheads may appear when simulating other restricted quantum automata variants by classical ones under comparable acceptance conditions.
The result supplies a concrete benchmark for comparing state-efficient implementations of quantum versus probabilistic automata in theoretical computer science.
It raises the question of whether approximate or bounded-error versions of the same simulation would still require quadratic states.

Load-bearing premise

The mixed-state linearization exactly preserves strict-cutpoint acceptance probabilities and the VC-dimension argument correctly produces hard instances for the lower bound in the one-way model.

What would settle it

An explicit n-state 1gQFA whose minimal equivalent one-way PFA uses strictly fewer than n²-1 states, or a proof that every n-state 1gQFA can be simulated by a PFA with o(n²) states.

read the original abstract

Generalized finite automata (GFAs), probabilistic finite automata (PFAs), and one-way general quantum finite automata (1gQFA) recognize the same strict-cutpoint languages, but the state complexity of exact probabilistic simulation has remained unclear. This paper determines that worst-case cost exactly: every \(n\)-state 1gQFA admits exact strict-cutpoint simulation by a one-way PFA with \(O(n^2)\) states, via the standard \(n^2\)-dimensional mixed-state linearization together with an explicit alphabet-preserving construction that converts each \(k\)-state GFA into a one-way PFA with at most \(2k+6\) states; conversely, for every \(n\ge 2\), there exists an \(n\)-state 1gQFA for which every equivalent one-way PFA requires at least \(n^2-1\) states, obtained from a prepare--test construction and a Vapnik--Chervonenkis dimension argument. Hence the worst-case probabilistic state cost of exact strict-cutpoint simulation is \(\Theta(n^2)\).

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 the exact worst-case quadratic blowup when simulating n-state 1gQFA with one-way PFAs via matching upper and lower bounds.

read the letter

The key point is that the worst-case state cost for exact strict-cutpoint simulation of n-state one-way generalized quantum finite automata by one-way probabilistic finite automata is Θ(n²). The paper supplies both an O(n²) upper bound and an n²-1 lower bound for n ≥ 2, which had been left open before. The upper bound rests on the standard vectorization of the mixed state to produce an equivalent n²-state GFA, followed by an explicit alphabet-preserving conversion from any k-state GFA to a PFA using at most 2k+6 states. The lower bound comes from a prepare-test family whose languages are shown to require nearly n² PFA states via a VC-dimension argument. These are standard techniques in the area, and the argument avoids circularity or free parameters. The constructions appear to preserve acceptance probabilities exactly, which is what matters for strict cutpoints. The main soft spot is that the abstract only sketches the GFA-to-PFA conversion and the precise application of VC-dimension in the one-way model; without the full proofs it is impossible to verify whether any hidden overhead or edge cases arise in the alphabet-preserving step. The lower-bound instances also need checking to confirm they really force the quadratic cost without extra assumptions on the probability weights. This work is aimed at researchers in automata theory who care about precise state-complexity comparisons between quantum and classical models. It gives a clean, tight answer to a concrete open question rather than a loose or one-sided result. I would send it to peer review; the central claim is important enough and the outline is coherent enough that referees can usefully check the details.

Referee Report

0 major / 1 minor

Summary. The paper claims that the worst-case probabilistic state cost of exact strict-cutpoint simulation of n-state one-way general quantum finite automata (1gQFA) by one-way probabilistic finite automata (PFAs) is Θ(n²). It provides an upper bound of O(n²) states using the standard mixed-state linearization to obtain an equivalent generalized finite automaton (GFA) and an alphabet-preserving GFA-to-PFA conversion with at most 2k+6 states. For the lower bound, it constructs a prepare-test family of n-state 1gQFAs where any equivalent PFA requires at least n²-1 states, using a Vapnik-Chervonenkis dimension argument.

Significance. If the result holds, it is significant for automata theory as it exactly determines the simulation overhead from quantum to classical models under strict-cutpoint acceptance, showing a quadratic blow-up is both necessary and sufficient in the worst case. The paper's strengths include the explicit constructions for the upper bound and the use of VC-dimension for the lower bound, providing a tight characterization without reliance on fitted parameters or ad-hoc assumptions.

minor comments (1)

[Abstract] The abstract refers to 'O(n^2)' for the upper bound construction but concludes with Θ(n²); it would be helpful to specify the leading constants or the exact bound from the 2k+6 conversion in the main text for clarity.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary of our results and the recommendation for minor revision. The referee correctly identifies the main contributions: the O(n²) upper bound via mixed-state linearization and GFA-to-PFA conversion, and the n²-1 lower bound via the prepare-test family and VC-dimension argument. We are pleased that the significance for automata theory is recognized.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The derivation relies on two explicit, independent constructions: (1) the standard vectorization of the density operator to produce an equivalent n²-state GFA whose acceptance probabilities match the 1gQFA exactly for every input word, and (2) an alphabet-preserving conversion from any k-state GFA to a one-way PFA using at most 2k+6 states that preserves the strict-cutpoint language. The matching lower bound is obtained from an explicit prepare-test family whose languages are shown, via the standard VC-dimension argument, to require at least n²-1 PFA states. None of these steps reduce by definition or by self-citation to the target result; they are self-contained mathematical constructions and standard dimension arguments that stand outside the paper's fitted values or prior self-referential claims.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work relies on standard linear algebra for quantum states and VC-dimension facts from learning theory; no free parameters, ad-hoc axioms, or new entities are introduced.

axioms (2)

standard math Properties of density operators and the standard n²-dimensional vectorization of mixed states preserve acceptance probabilities
Invoked in the upper-bound construction for exact simulation.
standard math VC-dimension bounds apply to the concept class of languages recognized by the constructed automata
Used to obtain the n²-1 lower bound.

pith-pipeline@v0.9.0 · 5490 in / 1296 out tokens · 50698 ms · 2026-05-10T18:00:39.560045+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/Foundation/AlexanderDuality.lean alexander_duality_circle_linking unclear
every n-state 1gQFA admits exact strict-cutpoint simulation by a one-way PFA with O(n²) states ... conversely ... at least n²-1 states
IndisputableMonolith/Foundation/ArithmeticFromLogic.lean embed_injective unclear
mixed-state linearization ... n²-dimensional ... traceless Hermitian subspace has dimension n²-1

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

On the Simulation Cost of Quantum Finite Automata
quant-ph 2026-05 unverdicted novelty 7.0

Quantum finite automata require Θ(c q²) classical states to simulate exactly in the hybrid case and Θ(n²) in the measure-once case under strict cutpoints.

Reference graph

Works this paper leans on

15 extracted references · 5 canonical work pages · cited by 1 Pith paper

[1]

Probabilistic Automata

Michael O. Rabin. “Probabilistic Automata”. In:Information and Control6.3 (1963), pp. 230–245

1963
[2]

Academic Press, 1971

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

1971
[3]

Generalized Automata and Stochastic Languages

Paavo Turakainen. “Generalized Automata and Stochastic Languages”. In:Proceedings of the American Mathematical Society21.2 (1969), pp. 303–309.doi:10.1090/S0002-9939- 1969-0242596-1

work page doi:10.1090/s0002-9939- 1969
[4]

Quantum Automata and Quantum Gram- mars

Cristopher Moore and James P. Crutchfield. “Quantum Automata and Quantum Gram- mars”. In:Theoretical Computer Science237.1–2 (2000), pp. 275–306

2000
[5]

On the Power of Quantum Finite State Automata

Attila Kondacs and John Watrous. “On the Power of Quantum Finite State Automata”. In:Proceedings of the 38th Annual Symposium on Foundations of Computer Science. 1997, pp. 66–75

1997
[6]

1-Way Quantum Finite Automata: Strengths, Weaknesses and Generalizations

Andris Ambainis and R¯ usin,š Freivalds. “1-Way Quantum Finite Automata: Strengths, Weaknesses and Generalizations”. In:Proceedings of the 39th Annual Symposium on Foundations of Computer Science. 1998, pp. 332–341

1998
[7]

Characterizations of 1-Way Quantum Finite Automata

Alex Brodsky and Nicholas Pippenger. “Characterizations of 1-Way Quantum Finite Automata”. In:SIAM Journal on Computing31.5 (2002), pp. 1456–1478

2002
[8]

Characterizations of One-Way General Quantum Finite Automata

Lvzhou Li et al. “Characterizations of One-Way General Quantum Finite Automata”. In: Theoretical Computer Science419 (2012), pp. 73–91.doi:10.1016/j.tcs.2011.10.021

work page doi:10.1016/j.tcs.2011.10.021 2012
[9]

Abuzer Yakaryilmaz and A. C. Cem Say.Language Recognition by Generalized Quantum Finite Automata with Unbounded Error. Poster presentation at TQC 2009; arXiv:0901.2703. 2009. 11

work page arXiv 2009
[10]

Languages Recognized with Unbounded Error by Quantum Finite Automata

Abuzer Yakaryilmaz and A. C. Cem Say. “Languages Recognized with Unbounded Error by Quantum Finite Automata”. In:Computer Science Symposium in Russia (CSR 2009). Vol. 5675. Lecture Notes in Computer Science. Springer, 2009, pp. 356–367

2009
[11]

Unbounded-Error Quantum Computation with Small Space Bounds

Abuzer Yakaryılmaz and A. C. Cem Say. “Unbounded-Error Quantum Computation with Small Space Bounds”. In:Information and Computation209.6 (2011), pp. 873–892.doi: 10.1016/j.ic.2011.01.008

work page doi:10.1016/j.ic.2011.01.008 2011
[12]

Quantum Automata with Open Time Evolution

Mika Hirvensalo. “Quantum Automata with Open Time Evolution”. In:International Journal of Natural Computing Research1.1 (2010), pp. 70–85.doi: 10 . 4018 / jncr . 2010010104

2010
[13]

Decision Questions for Probabilistic Automata on Small Alphabets

Paul C. Bell and Pavel Semukhin. “Decision Questions for Probabilistic Automata on Small Alphabets”. In:Logical Methods in Computer Science19.4 (2023), 36:1–36:22.doi: 10.46298/LMCS-19(4:36)2023

work page doi:10.46298/lmcs-19(4:36)2023 2023
[14]

Vapnik.Statistical Learning Theory

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

1998
[15]

Bartlett.Neural Network Learning: Theoretical Foundations

Martin Anthony and Peter L. Bartlett.Neural Network Learning: Theoretical Foundations. Cambridge University Press, 1999. 12

1999