Computation in Finitary Quantum Processes

We introduce quantum finite-state generators as a first step toward completing a computational description of observing individual quantum systems over time. We develop the mathematical foundations of quantum finite-state machines and compare nondeterministic and deterministic versions to stochastic generators and recognizers, summarizing their relative computational power via a hierarchy of finitary process languages. Quantum finite-state generators are explored via several physical examples, including the iterated beam splitter, the quantum kicked top, and atoms in an ion trap—a special case of which implements the Deutsch quantum algorithm. We show that the behavior of these systems, and so their information processing capacity, depends sensitively on measurement protocol.