Simulation of finite state machines in a quantum computer

M. R. Dunlavey

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 stri…