Consider the finite regular language \math. In [3] it was shown 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 \math . 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 \math lower bound for such QFA for Ln , thus also improving the previous bound.The improved bound is obtained from simple entropy arguments based on Holevo's theorem [8]. This method also allows us to obtain an asymptotically optimal (1 - H(p))n bound for the dense quantum codes (random access codes) introduced in [3]. 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.