NGHIÊN CỨU ỨNG DỤNG THUẬT TOÁN LƯỢNG TỬ GROVER TRONG GIẢI TRÌNH TỰ DNA | Lữ | TNU Journal of Science and Technology

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/24

Các tác giả

1. Dụng Văn Lữ, Trường Đại học Sư phạm – Đại học Đà Nẵng
2. Huỳnh Phương Anh Email to author, Trường Đại học Sư phạm – Đại học Đà Nẵng
3. Huỳnh Bảo Nguyên, Trường Đại học Sư phạm – Đại học Đà Nẵng
4. Nguyễn Ngọc Minh Trí, Trường Đại học Sư phạm – Đại học Đà Nẵng
5. Cao Thị Mỹ Hảo, Trường Đại học Sư phạm - Đại học Đà Nẵng
6. Nguyễn Thị Hồng, Trường Đại học Sư phạm - Đại học Đà Nẵng

Tó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


Thuật toán lượng tử; Máy tính lượng tử; Thuật toán Grover; Tìm kiếm phi cấu trúc; Giải trình tự DNA

Toàn văn:

PDF

Tà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
Tạp chí Khoa học và Công nghệ - Đại học Thái Nguyên
Phòng 408, 409 - Tòa nhà Điều hành - Đại học Thái Nguyên
Phường Tân Thịnh - Thành phố Thái Nguyên
Điện thoại: 0208 3840 288 - E-mail: jst@tnu.edu.vn
Phát triển trên nền tảng Open Journal Systems
©2018 All Rights Reserved