Tổng quan nghiên cứu

Sự bùng nổ của dữ liệu toàn cầu với tốc độ tăng trưởng ước tính trên 40% mỗi năm đang đặt ra những thách thức chưa từng có đối với hệ thống lưu trữ và bảo mật thông tin cổ điển. Các hệ mã hóa khóa công khai hiện đại như RSA-2048 đang bảo vệ hàng triệu giao dịch tài chính mỗi giây dựa trên giả định về độ khó của bài toán phân tích một số nguyên lớn thành tích các thừa số nguyên tố. Tuy nhiên, các siêu máy tính cổ điển mạnh nhất hiện nay phải mất hàng tỷ năm để giải quyết bài toán này do độ phức tạp thời gian tăng theo hàm siêu đa thức hoặc hàm mũ $O(2^n)$.

Trước giới hạn vật lý và lý thuyết của mô hình thông tin Shannon cổ điển, nghiên cứu này được thực hiện nhằm mục tiêu giải quyết bài toán tính toán hiệu năng cao thông qua lý thuyết thông tin lượng tử. Luận văn tập trung khảo sát toàn diện cơ sở toán học của tính toán lượng tử, phân tích chi tiết cơ chế hoạt động của thuật toán Peter Shor, đồng thời xây dựng mô hình mô phỏng thuật toán trên phần mềm tính toán chuyên dụng Wolfram Mathematica.

Được hoàn thành tại Trường Đại học Bách Khoa – Đại học Quốc gia TP. Hồ Chí Minh trong khoảng thời gian 6 tháng từ ngày 11/01/2016 đến ngày 17/06/2016, công trình có quy mô toàn văn gồm 84 trang được cấu trúc thành 3 chương chuyên sâu. Nghiên cứu mang ý nghĩa học thuật và ứng dụng to lớn khi chứng minh rằng thuật toán Shor lượng tử có thể giải quyết bài toán phân tích thừa số nguyên tố trong thời gian đa thức cấp $O((\log N)^2 (\log \log N) (\log \log \log N))$, thuộc lớp độ phức tạp BQP. Kết quả này mở ra bước đột phá trong việc rút ngắn thời gian xử lý các bài toán NP-khó từ hàng triệu năm xuống còn vài phút, đồng thời tạo tiền đề cho việc xây dựng các chuẩn mật mã hậu lượng tử tại Việt Nam.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Nghiên cứu xây dựng trên nền tảng giao thoa giữa ba hệ thống lý thuyết cốt lõi:

Thứ nhất là Lý thuyết thông tin cổ điển của Claude Shannon, tập trung vào hai trụ cột toán học gồm Định lý mã hóa nguồn thứ nhất khẳng định độ dài trung bình từ mã $\bar{n}$ không thể nhỏ hơn entropy nguồn tin $H(A)$ ($\bar{n} \ge H(A)$), và Định lý mã hóa kênh thứ hai giới hạn khả năng truyền tin không lỗi bởi dung lượng thông qua của kênh $C'$ ($H'(A) < C'$).

Thứ hai là Cơ học lượng tử và Lý thuyết thông tin lượng tử. Khung lý thuyết này vận dụng các tiên đề không gian Hilbert phức, trong đó đơn vị thông tin cơ bản là qubit với trạng thái chồng chất tuyến tính $|\psi\rangle = \alpha_0|0\rangle + \alpha_1|1\rangle$ thỏa mãn điều kiện chuẩn hóa $|\alpha_0|^2 + |\alpha_1|^2 = 1$. Trạng thái của hệ $n$-qubit biểu diễn đồng thời $2^n$ trạng thái cơ sở trực chuẩn trong không gian trạng thái $2^n$ chiều, kết hợp hiện tượng vướng víu lượng tử thông qua các trạng thái Bell như $|\psi\rangle = \frac{1}{\sqrt{2}}|00\rangle + \frac{1}{\sqrt{2}}|11\rangle$.

Thứ ba là Lý thuyết độ phức tạp tính toán, phân loại các bài toán theo các lớp P, NP, NP-đầy đủ, NP-khó và lớp thời gian lượng tử đa thức có sai số bị chặn BQP.

Mô hình nghiên cứu được xây dựng trên hệ thống mạch logic lượng tử với các cổng toán tử Unita cơ bản gồm cổng Hadamard ($H$), cổng đảo bit NOT, cổng điều khiển CNOT, cổng hoán vị SWAP và cổng xoay pha. Trọng tâm của mô hình là Biến đổi Fourier lượng tử (QFT), cho phép chuyển đổi trạng thái cơ sở $|x\rangle$ thành tổ hợp các trạng thái $|y\rangle$ với trọng số pha $\omega = e^{2\pi i / 2^n}$, phục vụ trực tiếp cho quá trình trích xuất chu kỳ trong thuật toán Shor.

Phương pháp nghiên cứu

Nghiên cứu sử dụng nguồn dữ liệu thứ cấp từ 19 công trình khoa học tiêu chuẩn quốc tế và trong nước về lý thuyết thông tin và cơ học lượng tử, bao gồm các giáo trình kinh điển của Nielsen & Chuang, công trình nền tảng của Peter Shor, cùng các bài báo nghiên cứu cấu trúc đại số của Đỗ Ngọc Diệp và Huỳnh Văn Đức giai đoạn 2008-2013.

Cỡ mẫu nghiên cứu thực nghiệm bao gồm 15 trường hợp kiểm thử cấu hình mạch lượng tử khác nhau, được phân bổ từ các hệ mạch 1-qubit, 2-qubit, 3-qubit đến hệ mạch 7-qubit. Phương pháp chọn mẫu là chọn mẫu có chủ đích dựa trên sự gia tăng lũy tiến của cấp độ phức tạp trạng thái, đi từ việc đo đạc dự đoán pha lượng tử 2-bit và 3-bit đến quy trình phân tích hợp số $N = 15$ và $N = 91$.

Phương pháp phân tích được lựa chọn là phân tích giải tích toán học kết hợp phương pháp mô phỏng số trên phần mềm Wolfram Mathematica. Lý do lựa chọn kết hợp này là vì các phép toán ma trận trong không gian Hilbert với kích thước $2^n \times 2^n$ đòi hỏi tính toán giải tích chuẩn xác tuyệt đối các toán tử Unita. Wolfram Mathematica cung cấp môi trường lập trình đại số ký hiệu hoàn hảo, giúp trực quan hóa xác suất đo lường và theo dõi chính xác từng bước biến đổi trạng thái của thuật toán mà không gặp phải sai số làm tròn số học. Toàn bộ quy trình nghiên cứu được triển khai liên tục qua 158 ngày làm việc từ tháng 01/2016 đến tháng 06/2016.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Nghiên cứu đã ghi nhận 4 phát hiện cốt lõi với các chỉ số định lượng rõ ràng:

Thứ nhất, Biến đổi Fourier lượng tử (QFT) tạo ra sự cắt giảm vượt bậc về số lượng phép tính so với xử lý cổ điển. Trong khi thuật toán Biến đổi Fourier nhanh cổ điển (FFT) của Cooley-Tukey đòi hỏi $O(M \log_2 M)$ bước tính toán cho dữ liệu kích thước $M$, QFT chỉ tiêu tốn $O(\log_2^2 M)$ bước bằng cách mã hóa đầu vào thành trạng thái chồng chất trên $n = \log_2 M$ qubits. Cấu trúc mạch QFT chỉ sử dụng $n(n+1)/2$ cổng logic (gồm cổng Hadamard và các cổng xoay pha có điều khiển), giúp giảm hơn 85% tổng số thao tác cổng khi $n$ tăng lên từ 3 qubit đến 10 qubit.

Thứ hai, thuật toán Shor đạt bước nhảy vọt về tốc độ xử lý bài toán phân tích thừa số nguyên tố. Đối với một số tự nhiên $N$, các thuật toán cổ điển tối ưu nhất như Sàng trường số tổng quát (GNFS) đòi hỏi thời gian siêu đa thức $O(\exp(c(\log_2 N)^{1/3} (\log_2 \log_2 N)^{2/3}))$. Ngược lại, thuật toán Shor giải quyết bài toán này trong thời gian đa thức $O((\log_2 N)^2 (\log_2 \log_2 N) (\log_2 \log_2 \log_2 N))$. Sự chuyển dịch này giúp giảm thời gian phân tích khóa mật mã hơn 99,99% trên lý thuyết khi kích thước bit vượt quá 1024-bit.

Thứ ba, năng lực lưu trữ và tính toán song song của hệ lượng tử thể hiện sự vượt trội mang tính đột biến. Một thanh ghi gồm $n = 500$ qubit có thể duy trì đồng thời $2^{500}$ trạng thái lượng tử chồng chất, một con số lớn hơn rất nhiều so với tổng số khoảng $10^{80}$ hạt cơ bản trong toàn bộ vũ trụ quan sát được. Điều này khẳng định tính toán lượng tử không đơn thuần là tăng tốc phần cứng mà là cuộc cách mạng toàn diện về không gian trạng thái.

Thứ tư, nghiên cứu đã mô phỏng thành công thuật toán Shor phân tích số $N = 15$ thành $3 \times 5$ trên hệ thống 7 qubit và xây dựng thuật toán phân tích số $N = 91$ thành $7 \times 13$. Tỷ lệ đo lường pha chính xác và tìm đúng chu kỳ $r$ qua khai triển phân số liên tục đạt xấp xỉ 100% trong môi trường mô phỏng không nhiễu.

Thảo luận kết quả

Nguyên nhân cốt lõi tạo nên sự vượt trội của thuật toán lượng tử bắt nguồn từ bản chất vật lý của nguyên lý chồng chất và hiện tượng vướng víu lượng tử. Khác với máy tính cổ điển xử lý tuần tự từng chuỗi bit 0 hoặc 1 theo kênh nhị phân Shannon, máy tính lượng tử thao tác đồng thời trên tất cả các nhánh trạng thái của thanh ghi, biến bài toán tìm ước số thành bài toán giao thoa lượng tử để triệt tiêu các nghiệm sai và khuếch đại xác suất của nghiệm đúng.

Khi so sánh với các nghiên cứu tiền nhiệm, kết quả của luận văn hoàn toàn tương thích với thực nghiệm năm 2001 của nhóm nghiên cứu IBM khi phân tích số 15 bằng kỹ thuật cộng hưởng từ hạt nhân 7 qubit, đồng thời mở rộng và cụ thể hóa các công trình lý thuyết tại Việt Nam của Đỗ Ngọc Diệp và Huỳnh Văn Đức giai đoạn 2008-2013 về mô hình mạch lượng tử.

Dữ liệu so sánh độ phức tạp tính toán giữa các thuật toán có thể được trực quan hóa thông qua biểu đồ hàm mũ đối lập hàm đa thức, cũng như bảng đối sánh số lượng cổng logic cần thiết theo từng bậc độ dài bit đầu vào:

  • Biểu đồ đường biểu diễn sự chênh lệch thời gian thực thi: Khi kích thước đầu vào $n$ tăng từ 64 đến 2048 bit, đường biểu diễn của thuật toán cổ điển vọt lên tiệm cận vô cùng theo đường cong hàm mũ, trong khi đường biểu diễn của thuật toán Shor duy trì độ dốc đa thức thoai thoải.
  • Bảng đối sánh cấu hình mạch logic: Thể hiện số lượng cổng Hadamard và cổng xoay pha $R_k$ tăng tuyến tính theo công thức $n(n+1)/2$, minh chứng tính khả thi kỹ thuật vượt trội.

Ý nghĩa học thuật của phát hiện này khẳng định nguy cơ hiện hữu đối với an toàn thông tin toàn cầu, đặt ra yêu cầu cấp bách phải tái cấu trúc toàn bộ nền tảng mật mã học trước khi máy tính lượng tử thực dụng ra đời.

Đề xuất và khuyến nghị

Dựa trên các kết quả nghiên cứu lý thuyết và mô phỏng số, 4 nhóm giải pháp và khuyến nghị chiến lược được đề xuất:

Thứ nhất, nâng cấp mô hình mô phỏng và công cụ tính toán lượng tử. Các viện nghiên cứu toán học và khoa học máy tính cần chủ động phát triển các gói thư viện thuật toán lượng tử nâng cao trên nền tảng máy tính hiệu năng cao (HPC), hướng tới mục tiêu mô phỏng các mạch lượng tử từ 30 đến 50 qubit trong giai đoạn 2026-2028, cho phép kiểm thử thuật toán Shor với các số nguyên lớn hơn $N > 10^6$.

Thứ hai, tái cấu trúc chuẩn mực an ninh mạng và chuyển đổi hệ thống mã hóa quốc gia. Cơ quan quản lý an toàn thông tin, các ngân hàng và tổ chức tài chính cần xây dựng lộ trình thay thế 100% các hệ mật mã khóa công khai truyền thống (RSA, ECC) sang hệ thống mật mã hậu lượng tử (PQC) dựa trên mạng tinh thể (lattice-based cryptography) trong thời gian 3 đến 5 năm tới, đảm bảo hoàn tất trước năm 2030.

Thứ ba, phát triển chương trình đào tạo chuyên sâu về Tính toán lượng tử. Bộ Giáo dục và Đào tạo phối hợp với các trường đại học khối công nghệ triển khai các môn học chuyên đề về đại số lượng tử, lý thuyết thông tin lượng tử và thuật toán lượng tử ở bậc đại học và sau đại học, đặt mục tiêu đào tạo trên 500 thạc sĩ và kỹ sư chuyên ngành tính toán lượng tử trước năm 2030.

Thứ tư, đẩy mạnh hợp tác quốc tế tiếp cận nền tảng phần cứng lượng tử thực tế. Các nhóm nghiên cứu tại Việt Nam cần thiết lập quan hệ đối tác với các trung tâm công nghệ hàng đầu như IBM Quantum Network hoặc Google Quantum AI để truy cập hệ thống máy tính lượng tử từ 100 đến 1.000 qubit thông qua điện toán đám mây trong giai đoạn 2026-2027, rút ngắn khoảng cách giữa lý thuyết toán học và thực nghiệm vật lý.

Đối tượng nên tham khảo luận văn

Luận văn là tài liệu tham khảo học thuật giá trị cao cho 4 nhóm đối tượng trọng tâm:

Thứ nhất, học viên cao học và nghiên cứu sinh chuyên ngành Toán ứng dụng và Toán tin. Công trình cung cấp nền tảng toán học giải tích chặt chẽ trong không gian Hilbert, đại số ma trận Unita và các chứng minh giải tích về biến đổi Fourier lượng tử, làm tài liệu tham khảo chuẩn mực để phát triển các đề tài luận án chuyên sâu.

Thứ hai, kỹ sư phần mềm và nhà khoa học máy tính. Luận văn cung cấp hướng dẫn chi tiết về cấu trúc mạch logic lượng tử (Hadamard, CNOT, SWAP) cùng mã nguồn mô phỏng thuật toán Shor trên Wolfram Mathematica, hỗ trợ trực tiếp cho các dự án lập trình mô phỏng lượng tử trên máy tính cổ điển.

Thứ ba, chuyên gia an toàn thông tin và kiến trúc sư hệ thống mạng. Tài liệu mang lại cái nhìn định lượng chính xác về nguy cơ phá vỡ mã hóa RSA của thuật toán Shor, hỗ trợ xây dựng báo cáo đánh giá rủi ro an ninh mạng và lập kế hoạch di trú hệ thống sang các chuẩn bảo mật hậu lượng tử.

Thứ tư, giảng viên đại học và nhà nghiên cứu công nghệ thông tin. Với kết cấu 84 trang hoàn chỉnh, chứa đựng 19 tài liệu tham khảo chuẩn mực và các ví dụ minh họa từng bước cho các trường hợp $N = 15$ và $N = 91$, công trình là giáo trình tham khảo lý tưởng cho các môn học Tính toán lượng tử và Mật mã học nâng cao.

Câu hỏi thường gặp

Thuật toán Shor lượng tử giải quyết bài toán gì và vì sao lại vượt trội hơn máy tính cổ điển? Thuật toán Shor giải quyết bài toán phân tích một số hợp số $N$ thành tích các thừa số nguyên tố với độ phức tạp đa thức $O((\log N)^2 (\log \log N) (\log \log \log N))$. Trong khi thuật toán cổ điển đòi hỏi thời gian siêu đa thức hàng tỷ năm với số lớn, thuật toán Shor tận dụng phép biến đổi Fourier lượng tử để tìm chu kỳ hàm số, rút ngắn thời gian xử lý xuống còn vài phút trên phần cứng lượng tử.

Điểm khác biệt căn bản giữa một qubit lượng tử và một bit cổ điển là gì? Bit cổ điển chỉ nhận một trong hai trạng thái rời rạc là 0 hoặc 1 theo lý thuyết Shannon. Ngược lại, một qubit có thể tồn tại ở trạng thái chồng chất tuyến tính $|\psi\rangle = \alpha_0|0\rangle + \alpha_1|1\rangle$ với $|\alpha_0|^2 + |\alpha_1|^2 = 1$. Nhờ đó, hệ $n$-qubit xử lý đồng thời $2^n$ trạng thái trong không gian Hilbert $2^n$ chiều, tạo ra năng lực tính toán song song vượt bậc.

Biến đổi Fourier lượng tử (QFT) đóng vai trò gì trong thuật toán Shor? QFT là thành phần lượng tử cốt lõi giúp chuyển đổi trạng thái từ miền thời gian sang miền tần số để trích xuất chu kỳ $r$ của hàm số $f(x) = a^x \pmod N$. Nhờ kiến trúc mạch tối ưu chỉ gồm $n(n+1)/2$ cổng logic, QFT thực thi phép biến đổi chỉ với $O(\log_2^2 M)$ bước, tiết kiệm hơn 85% thao tác so với thuật toán FFT cổ điển đòi hỏi $O(M \log_2 M)$ bước.

Tại sao thuật toán Shor lại đe dọa trực tiếp đến hệ thống mật mã RSA hiện nay? Hệ mật mã khóa công khai RSA dựa trên độ khó của việc phân tích các số nguyên lớn 2048-bit hoặc 4096-bit thành thừa số nguyên tố trên máy tính cổ điển. Khi thuật toán Shor vận hành trên máy tính lượng tử đủ số qubit, khóa mã hóa RSA sẽ bị giải mã trong thời gian thực, vô hiệu hóa toàn bộ hạ tầng bảo mật giao dịch ngân hàng và thông tin toàn cầu.

Luận văn đã tiến hành mô phỏng thuật toán trên công cụ nào và đạt kết quả ra sao? Tác giả đã lập trình mô phỏng toàn bộ mạch lượng tử và thuật toán Shor trên phần mềm Wolfram Mathematica. Nghiên cứu đã mô hình hóa thành công hệ mạch 7-qubit để phân tích số $N = 15$ ra hai thừa số 3 và 5, đồng thời xây dựng quy trình phân tích số $N = 91$, chứng minh tính đúng đắn và khả thi tuyệt đối của thuật toán về mặt đại số.

Kết luận

  • Luận văn đã hệ thống hóa toàn diện cơ sở toán học của lý thuyết thông tin lượng tử, làm rõ các giới hạn vật lý và định lý nén/truyền tin của Shannon trong lý thuyết thông tin cổ điển.
  • Phân tích chuyên sâu cơ chế đại số của Biến đổi Fourier lượng tử (QFT), chứng minh khả năng tối ưu hóa số phép tính từ $O(M \log_2 M)$ xuống $O(\log_2^2 M)$.
  • Làm rõ cấu trúc toán học của thuật toán Shor, chứng minh việc hạ độ phức tạp phân tích số nguyên từ hàm siêu đa thức xuống thời gian đa thức cấp $O((\log_2 N)^2 (\log_2 \log_2 N) (\log_2 \log_2 \log_2 N))$ thuộc lớp BQP.
  • Triển khai mô phỏng số thành công trên phần mềm Wolfram Mathematica, kiểm chứng chính xác quá trình phân tích thừa số nguyên tố cho các trường hợp $N = 15$ và $N = 91$.
  • Đóng góp một công trình học thuật 84 trang với 19 tài liệu tham khảo chất lượng cao, cung cấp nguồn tư liệu chuẩn mực cho nghiên cứu toán lượng tử và mật mã học tại Việt Nam.

Đóng góp chính của luận văn là thiết lập cầu nối lý thuyết vững chắc giữa giải tích toán học trong không gian Hilbert và ứng dụng thuật toán lượng tử giải quyết bài toán NP-khó. Trong giai đoạn 2026-2028, các hướng nghiên cứu tiếp theo cần tập trung mở rộng sang thuật toán tìm kiếm Grover và các mô hình mật mã kháng lượng tử. Hãy chủ động nắm bắt công nghệ lượng tử và cập nhật các tiêu chuẩn an toàn thông tin mới ngay hôm nay để đón đầu cuộc cách mạng công nghệ tiếp theo.