On injectivity of quantum finite automata

Abstract

<div><p>We consider notions of freeness and ambiguity for the <a href="https://www.sciencedirect.com/topics/computer-science/acceptance-probability" title="Learn more about acceptance probability from ScienceDirect's AI-generated Topic Pages">acceptance probability</a> of Moore-Crutchfield Measure Once Quantum <a href="https://www.sciencedirect.com/topics/computer-science/finite-automata" title="Learn more about Finite Automata from ScienceDirect's AI-generated Topic Pages">Finite Automata</a> (MO-QFA). We study the <em>injectivity</em> problem of determining if the acceptance probability function of a MO-QFA is injective over all input words, i.e., giving a distinct probability for each input word. We show that the injectivity problem is undecidable for 8 state MO-QFA, even when all <a href="https://www.sciencedirect.com/topics/computer-science/unitary-matrix" title="Learn more about unitary matrices from ScienceDirect's AI-generated Topic Pages">unitary matrices</a> and the <a href="https://www.sciencedirect.com/topics/computer-science/projection-matrix" title="Learn more about projection matrix from ScienceDirect's AI-generated Topic Pages">projection matrix</a> are rational and the initial state vector is real algebraic. We also show undecidability of this problem when the initial vector is rational, although with a huge increase in the number of states. We utilize properties of quaternions, free rotation groups, representations of tuples of rationals as linear sums of radicals and a reduction of the mixed modification of Post's correspondence problem, as well as a new result on rational polynomial packing functions which may be of independent interest.</p></div>