Small size quantum automata recognizing some regular languages

Given a class {pα|α∈I} of stochastic events induced by M-state 1-way quantum finite automata (1qfa) on alphabet Σ, we investigate the size (number of states) of 1qfa's that δ-approximate a convex linear combination of {pα|α∈I}, and we apply the results to the synthesis of small size 1qfa's. We obtain:An O((Md/δ3)log2(d/δ2)) general size bound, where d is the Vapnik dimension of {pα(w) |w∈Σ*}.For commutative n-periodic events p on Σ with |Σ|=H, we prove an O((Hlogn/δ2)) size bound for inducing a δ-approximation of 12+12p whenever ∥F(p̂)∥1≤nH, where F(p̂) is the discrete Fourier transform of (the vector p̂ associated with) p.If the characteristic function χL of an n-periodic unary language L satisfies ∥F(χL̂))∥1≤n, then L is recognized with isolated cut-point by a 1qfa with O(logn) states. Vice versa, if L is recognized with isolated cut-point by a 1qfa with O(logn) state, then ∥F(χL̂)) ∥1=O(nlogn).