Quantum Implementation of Finite State Automata
摘要
Quantum computing based on quantum mechanics principles has reached a level of development that is now considered a viable computing platform. Researchers have proposed quantum computing models inspired by classical computing models and have devised quantum algorithms analogous to classical algorithms. This includes finite state automaton (FA) which is a computing model with many applications. The analogous quantum models, quantum finite automata (QFA), proposed by researchers are new models close to the probabilistic finite state automaton models with transitions defined by unitary matrices. The action of the input alphabet of the automaton is modeled as unitary matrix acting on states modeled as vectors in a Hilbert space. This paper presents a new method that differs from traditional approaches by using classical finite automata (FA) as the basic structure. It introduces new techniques to create a quantum computing system, specifically a Quantum Finite Automaton (QFA) that behaves similarly to classical transition systems. The main idea is to convert classical transition functions into quantum circuit representations. This conversion uses quantum gate operations, which are effective at mimicking the transitions found in classical systems. As a result, this method keeps the structure of classical computations of Finite state Machines.