Quantum circuits from non-unitary sparse binary matrices

Quantum computing leverages unitary matrices to perform reversible computations while preserving probability norms. However, many real-world applications involve non-unitary sparse matrices, posing a challenge for quantum implementation. This paper introduces a novel method for transforming a class of non-unitary sparse binary matrices into higher-dimensional permutation matrices, ensuring unitarity. Our approach is efficient in both space and time, ensuring practical applicability to large-scale problems. We demonstrate the utility of this transformation in constructing quantum gates and apply the method to model quantum finite state machines (QFSMs) derived from classical deterministic finite automata (DFAs). This work offers a practical pathway for integrating non-unitary transformations into quantum systems, with implications for the many applications that are based on sparse, non-unitary matrices. The significance of this work for automata theory and quantum computation is outlined.