文章基本信息

标题：Quantum‐based exact pattern matching algorithms for biological sequences
本地全文：下载
作者：Kapil Kumar Soni ; Akhtar Rasool
期刊名称：ETRI Journal
印刷版ISSN：1225-6463
电子版ISSN：2233-7326
出版年度：2021
卷号：43
期号：3
页码：483-510
DOI：10.4218/etrij.2019-0589
语种：English
出版社：Electronics and Telecommunications Research Institute
摘要：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 ON time, whereas quantum algorithm design is based on Grover's method, which completes the search in ON 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 OtandON, and the exceptional worst case is bounded by OtandON. 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.