  A construction is given for simulating any deterministic finite state machine
(FSM) on a quantum computer in a space-efficient manner. By constructing a
superposition of input strings of lengths K or less, questions can be asked
about the FSM, such as the inputs that reach particular nodes, and the answers
can be found using a search algorithm such as Grover's. This has implications
for the eventual utility of quantum computers for software validation.
