1998/07/09 by M. R. Dunlavey, Dunlavey, M. R.
Physics and Astronomy · #FOS: Physical sciences #Quantum Physics (quant-ph) #quant-ph
paper · pdf · doi:10.48550/arxiv.quant-ph/9807026
Plain TEX, 6 pages, 3 GIF figures, includes C program
arxiv created 1998/07/09 · arxiv updated 2009/12/01
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.