Compare Similarities Between DNA Sequences Using Permutation-Invariant Quantum Kernel

Abstract

Computing the similarity between two DNA sequences is of vital importance in bioscience, yet it can be computationally expensive on classical hardware. For example, the edit distance with move operations (EDM), a DNA similarity measure of interest in biology, is proven to be NP-Complete to compute exactly on classical hardware. Recently, applied quantum algorithms have been anticipated to offer potential advantages over classical approaches. In this paper, we propose a novel variational quantum kernel model served as a surrogate model for estimating similarity between DNA sequences defined by EDM. Since the EDM metric exhibits a pairwise permutation-insensitive property, we incorporate a permutation-invariant structure into the variational quantum kernel to approximate this symmetry. Furthermore, to encode the four nucleotide bases as quantum states, we introduce a theoretically motivated encoding scheme based on symmetric informationally complete positive operator-valued measure (SIC-POVM) states. This encoding ensures mutual equivalence among bases, as each pair of symbols is mapped to quantum states that are equidistant on the Bloch sphere. We experimentally show that, equipped with the permutation-invariant circuit design and mutual-equivalence encoding, the proposed quantum kernel model achieves strong performance in approximating the similarity defined by EDM. Compared with classical kernel learning methods, our quantum approach achieves significantly higher accuracy while using substantially fewer trainable parameters.