Simulation of finite state machines in a quantum computer
arXiv:quant-ph/9807026
Abstract
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.
Plain TEX, 6 pages, 3 GIF figures, includes C program