Quantum‐based exact pattern matching algorithms for biological sequences

摘要

In computational biology, desired patterns are searched in large text databases, and an exact match is preferable. Classical benchmark algorithms obtain competent solutions for pattern matching in O N time, whereas quantum algorithm design is based on Grover's method, which completes the search in O N time. This paper briefly explains existing quantum algorithms and defines their processing limitations. Our initial work overcomes existing algorithmic constraints by proposing the quantum‐based combined exact (QBCE) algorithm for the pattern‐matching problem to process exact patterns. Next, quantum random access memory (QRAM) processing is discussed, and based on it, we propose the QRAM processing‐based exact (QPBE) pattern‐matching algorithm. We show that to find all t occurrences of a pattern, the best case time complexities of the QBCE and QPBE algorithms are O t and O N , and the exceptional worst case is bounded by O t and O N . Thus, the proposed quantum algorithms achieve computational speedup. Our work is proved mathematically and validated with simulation, and complexity analysis demonstrates that our quantum algorithms are better than existing pattern‐matching methods.