RESEARCH ON APPLICATION OF GROVER'S QUANTUM ALGORITHM  TO DNA SEQUENCING

Dụng Văn Lữ; Huỳnh Phương Anh; Huỳnh Bảo Nguyên; Nguyễn Ngọc Minh Trí; Cao Thị Mỹ Hảo; Nguyễn Thị Hồng

doi:10.34238/tnu-jst.9932

RESEARCH ON APPLICATION OF GROVER'S QUANTUM ALGORITHM TO DNA SEQUENCING

About this article

Received: 20/03/24 Revised: 23/05/24 Published: 24/05/24

Authors

1. Dung Van Lu, The University of Danang - University of Science and Education
2. Huynh Phuong Anh , The University of Danang - University of Science and Education
3. Huynh Bao Nguyen, The University of Danang - University of Science and Education
4. Nguyen Ngoc Minh Tri, The University of Danang - University of Science and Education
5. Cao Thi My Hao, The University of Danang - University of Science and Education
6. Nguyen Thi Hong, The University of Danang - University of Science and Education

Abstract

In order to search through an unstructured database of N elements, Grover's quantum search algorithm has O (√N) time complexity and uses O (log N) storage space thanks to the application of quantum mechanical properties (such as, superposition, entanglement,...) in each step of this algorithm. In this article, we studied the Grover quantum algorithm and clarified the quantum supremacy of the algorithm by analyzing the "behavior" of quantum mechanical properties in each step of this algorithm. In addition, we calculated and implemented on IBM quantum computers through the Qiskit platform in applicating for the problem of DNA sequencing with a string of length N = 8. The results showed that the Grover’s quantum search algorithm has superior search capabilities compared to existing algorithms as the quantum computer has a sufficient number of qubits, which helps to reduce the time and resources needed to determine the gene sequence and provides more effective methods for molecular biology.

Keywords

Quantum Algorithm; Quantum computing; Grover's algorithm; Unstructured search; DNA sequencing

Full Text:

PDF (Tiếng Việt)

References

[1] L. K. Grover, “A fast quantum mechanical algorithm for database search,” Proceedings of the 28th Annual ACM Symposium on the Theory of Computing (STOC), May 1996, pp. 212-219, doi: 10.48550/arXiv.quant-ph/9605043.

[2] G. Nannicini, “An introduction to quantum computing, without the physics,” SIAM Review, vol. 62, no. 4, pp. 936-981, 2020, doi: 10.48550/arXiv.1708.03684.

[3] Z. Zhang, et al., “Grover-QAOA for 3-SAT: Quadratic speedup, fair-sampling, and parameter clustering,” arXiv preprint, 2024, doi: 10.48550/arXiv.2402.02585.

[4] S. Aaronson, D. Grier, and L. Schaeffer, “A quantum query complexity trichotomy for regular languages,” 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), Baltimore, MD, USA, 2019, pp. 942-965, doi: 10.48550/arXiv.1812.04219.

[5] M. R. Habibi, S. Golestan, A. Soltanmanesh, J. M. Guerrero, and J. C. Vasquez, “Power energy applications based on quantum computing: The possible potentials of grover’s algorithm,” Electronics, vol. 11, no. 18, 2022, doi: 10.3390/electronics11182919.

[6] B. Khanal, P. Rivas, J. Orduz, and A. Zhakubayev, “Quantum machine learning: A case study of grover’s algorithm,” 2021 International Conference on Computational Science and Computational Intelligence (CSCI), Las Vegas, NV, USA, 2021, pp. 79-84, doi: 10.1109/CSCI54926.2021.00088.

[7] D. Qiu, L.Luo, and L. Xiao, “Distributed Grover's algorithm,” Theoretical Computer Science, vol. 993, p. 114461, 2024, doi: 10.48550/arXiv.2204.10487.

[8] R. H. Preston, “Applying Grover's algorithm to hash functions: a software perspective,” IEEE Transactions on Quantum Engineering, vol. 3, no. 2500710, pp. 1-10, 2022, doi: 10.1109/TQE.2022.3233526.

[9] S. Jaques, M. Naehrig, M. Roetteler, and F. Virdia, “Implementing Grover oracles for quantum key search on AES and LowMC,” Proc. 39th Annu. Int. Conf. Theory Appl. Cryptographic Techn., 2020, pp. 280–310, doi: 10.48550/arXiv.1910.01700.

[10] J. M. Heather and B. Chain, “The sequence of sequencers: The history of sequencing DNA,” Genomics, vol. 107, no.1, pp. 1-8, 2016, doi: 10.1016/j.ygeno.2015.11.003.

[11] R. Marina and C. Baldo III, “Quantum DNA sequencing using Gaussian amplitude amplification,” arXiv preprint, 31 Oct. 2023, doi: 10.48550/arXiv.2310.20466.

[12] A. Sarkar, Z. Al-Ars, C. G. Almudever, and K. L. Bertels, “QiBAM: approximate sub-string index search on quantum accelerators applied to DNA read alignment,” Electronics, vol. 10, no. 19, p. 2433, 2021, doi: 10.3390/electronics10192433.

[13] J. Leng, F. Yang, and X.B. Wang, “Quantum advantage of noisy Grover's algorithm,” arXiv preprint, 19 Jun. 2023, doi: 10.48550/arXiv.2306.10855.

[14] J. Barberà, “Quantum string matching,” github.com, May 26, 2022. [Online]. Available: https://github.com/juliabarbera/TFG-quantum-string-matching-/blob/main/Quantum_string_matching. Ipynb. [Accessed January 15, 2023].

DOI: https://doi.org/10.34238/tnu-jst.9932

Refbacks

There are currently no refbacks.



Remember me