Optimal lower bounds for quantum automata and random access codes

Consider the finite regular language L_n={w0|w∈{0,1}*,|w|⩽n}. A. Ambainis et al. (1999) showed that while this language is accepted by a deterministic finite automaton of size O(n), any one-way quantum finite automaton (QFA) for it has size 2^Ω(n/logn). This was based on the fact that the evolution of a QFA is required to be reversible. When arbitrary intermediate measurements are allowed, this intuition breaks down. Nonetheless, we show a 2^Ω(n) lower bound for such QFA for L_n, thus also improving the previous bound. The improved bound is obtained from simple entropy arguments based on A.S. Holevo´s (1973) theorem. This method also allows us to obtain an asymptotically optimal (1-H(p))n bound for the dense quantum codes (random access codes) introduced by A. Ambainis et al. We then turn to Holevo´s theorem, and show that in typical situations, it may be replaced by a tighter and more transparent in-probability bound