Hamiltonian Formulation of a Finite-State Automaton

A Finite–state Automaton (FA) is a simple model that has long been used to capture the behaviors of various systems. In our previous work, we have developed a translation technique for a FA to a quantum circuit to utilize efficient quantum algorithms for the problems described in a FA [19]. While we generate a quantum circuit composed of quantum logic gates in our earlier work, in this paper, we develop another translation technique that synthesizes a Hamiltonian from a FA so that accepted strings can be found using quantum optimization techniques such as QAOA. As a first step, we develop a set of Hamiltonian construction rules for a Binary Decision Diagram (BDD), which can represent Boolean functions compactly. Applying the rules, we translate the state transition function of a FA into a Hamiltonian. We further combine those Hamiltonians to generate a Hamiltonian for the acceptance of a string. Finally, a quantum circuit that simulates the evolution of quantum states under the Hamiltonian is synthesized such that quantum optimization techniques such as QAOA can be utilized to find accepted strings efficiently from the superposition of all strings. The technique is experimentally validated by solving a model validation problem. The work has applications to model checking, programming language models based on FAs, DNA sequencing, and so on.