NGHIÊN CỨU ỨNG DỤNG THUẬT TOÁN LƯỢNG TỬ GROVER TRONG GIẢI TRÌNH TỰ DNA
Thông tin bài báo
Ngày nhận bài: 20/03/24                Ngày hoàn thiện: 23/05/24                Ngày đăng: 24/05/24Tóm tắt
Để tìm kiếm trên một cơ sở dữ liệu phi cấu trúc gồm N phần tử, thuật toán lượng tử Grover có độ phức tạp về thời gian O(√N) và sử dụng O(log N) không gian lưu trữ nhờ ứng dụng của các tính chất cơ học lượng tử. Trong bài báo này, chúng tôi nghiên cứu thuật toán lượng tử Grover và làm rõ tính ưu việt của thuật toán bằng cách phân tích các “hành xử” của tính chất cơ học lượng tử (như chồng chất, vướng víu,...) trong từng bước của thuật toán. Đồng thời, chúng tôi tính toán và triển khai trên máy tính lượng tử IBM thông qua nền tảng Qiskit trong bài toán giải trình tự DNA với chuỗi có độ dài N = 8. Kết quả cho thấy thuật toán lượng tử Grover có khả năng tìm kiếm ưu việt hơn các thuật toán hiện có khi máy tính lượng tử có số qubit đủ dùng, điều này giúp giảm thời gian và nguồn lực cần thiết để xác định chuỗi gen và đồng thời cung cấp phương pháp hiệu quả hơn cho nghiên cứu sinh học phân tử.
Từ khóa
Toàn văn:
PDFTài liệu tham khảo
[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
Các bài báo tham chiếu
- Hiện tại không có bài báo tham chiếu