Mirrors and Memory in Quantum Automata

In this paper we start from the simplest form of Quantum Finite Automata (QFAs), namely Measure-Once QFAs with cut-point. First we elaborate on a variant of their semantics that can be obtained through a shift from the Schrödinger to the Heisenberg picture of Quantum Mechanics. In the Schrödinger picture states evolve in time while observables remain constant, while in the Heisenberg one states are constant and observables evolve. Interestingly, in the case of a QFA such shift reverts time-evolution. However, the equivalence of the two pictures over the class of QFAs holds thanks to the closure of the class with respect to language mirroring. Since the expressive power of such class of automata remains limited to infinite languages, we then consider their extension with bounded (multi-letter QFAs) and unbounded memory. Unfortunately, while bounded memory enhances the expressive power, the unbounded memory approach does not behave as one would expect.