Khóa luận: Nghiên cứu chi tiết thuật toán lượng tử Shor - Huỳnh Phương Anh

Khám phá thuật toán lượng tử Shor: Nguyên lý hoạt động, cách phân tích thừa số nguyên tố và tiềm năng phá vỡ các hệ thống mã hóa RSA phổ biến.

• Tác giả: Huynh Phuong Anh
• Người hướng dẫn: Ts. Dung Van Lu
• Trường học: Đại học Sư phạm, Đại học Đà Nẵng
• Chuyên ngành: Sư phạm vật lí
• Đề tài: Nghiên cứu thuật toán lượng tử Shor
• Loại tài liệu: Khóa luận tốt nghiệp
• Năm xuất bản: 2024
• Địa điểm: Đà Nẵng

Tóm tắt

I. Thuật toán lượng tử Shor là gì

Thuật toán lượng tử Shor là một trong những thuật toán lượng tử quan trọng nhất được phát triển bởi nhà khoa học Peter Shor vào năm 1994. Đây là một thuật toán phân tích thừa số nguyên tố có khả năng phân tích các số nguyên lớn thành các thừa số nguyên tố của chúng một cách hiệu quả trên máy tính lượng tử. Thuật toán này khai thác các nguyên lý cơ bản của cơ học lượng tử như chồng chất lượng tử và vướng víu lượng tử để đạt được tốc độ tính toán vượt trội so với máy tính cổ điển. Sự xuất hiện của thuật toán Shor đã mở ra một kỷ nguyên mới trong lĩnh vực mật mã học và bảo mật thông tin, gây ra những lo ngại về an toàn của các hệ thống mã hóa hiện tại, đặc biệt là mã hóa RSA.

1.1. Định nghĩa và ý nghĩa lịch sử

Thuật toán Shor được coi là bước ngoặt trong lịch sử máy tính lượng tử vì nó chứng minh rằng các thuật toán lượng tử có thể giải quyết những vấn đề cổ điển khó khăn nhanh hơn nhiều. Phát hiện này đã thúc đẩy các nhà khoa học và các tổ chức trên toàn thế giới đầu tư mạnh mẽ vào nghiên cứu và phát triển máy tính lượng tử, với các khoản đầu tư lên tới hàng chục tỷ USD.

1.2. Mối liên hệ với mật mã học

Thuật toán lượng tử Shor trực tiếp đe dọa độ an toàn của mã hóa RSA, hiện đang được sử dụng rộng rãi để bảo vệ dữ liệu nhạy cảm trên internet. Nếu máy tính lượng tử đủ mạnh có thể chạy thuật toán Shor thành công, nó sẽ có thể phá vỡ mã hóa khóa bất đối xứng trong thời gian ngắn, gây ra những rủi ro lớn đối với bảo mật thông tin toàn cầu.

II. Nguyên lý hoạt động của thuật toán Shor

Thuật toán lượng tử Shor hoạt động dựa trên hai phần chính: phần cổ điển và phần lượng tử. Phần cổ điển thực hiện các tính toán số học cơ bản, trong khi phần lượng tử xử lý vấn đề tìm chu kì (order-finding problem). Nguyên lý cốt lõi của thuật toán này là biến đổi bài toán phân tích thừa số nguyên tố thành bài toán tìm chu kỳ của một hàm số. Máy tính lượng tử sử dụng chồng chất lượng tử để kiểm tra nhiều khả năng đồng thời, sau đó sử dụng biến đổi Fourier lượng tử để trích xuất thông tin chu kỳ từ trạng thái chồng chất. Điều này cho phép thuật toán tìm được các thừa số với xác suất cao sau chỉ một số lần chạy.

2.1. Phần cổ điển của thuật toán

Phần cổ điển thực hiện các bước tiền xử lý, như chọn một số ngẫu nhiên a và tính ƯCLN(a, N). Nếu ƯCLN(a, N) > 1, ta đã tìm được một thừa số. Nếu không, phần cổ điển sẽ chuyển sang phần lượng tử để tìm chu kỳ của hàm số f(x) = a^x mod N. Các phép tính này có thể thực hiện hiệu quả trên máy tính cổ điển.

2.2. Phần lượng tử và tìm chu kỳ

Phần lượng tử sử dụng biến đổi Fourier lượng tử (Quantum Fourier Transform) để tìm chu kỳ của hàm số. Qubit được khởi tạo ở trạng thái chồng chất, tạo ra một siêu vị trí của tất cả các giá trị có thể. Sau khi áp dụng các cổng lượng tử và thực hiện biến đổi Fourier lượng tử, trạng thái lượng tử sẽ tập trung vào những giá trị liên quan đến chu kỳ.

III. Ứng dụng của thuật toán Shor

Thuật toán lượng tử Shor có nhiều ứng dụng thực tiễn quan trọng, ngoài việc phá vỡ mã hóa RSA. Nó có thể được sử dụng để tấn công các hệ thống bảo mật thông tin dựa trên mã hóa khóa bất đối xứng khác. Bên cạnh đó, nghiên cứu thuật toán Shor giúp các nhà khoa học hiểu rõ hơn về cơ học lượng tử và khả năng của máy tính lượng tử. Các ứng dụng của nó cũng thúc đẩy sự phát triển của mật mã lượng tử - một phương thức bảo mật mới dựa trên các nguyên lý lượng tử, an toàn hơn so với các phương pháp mã hóa truyền thống.

3.1. Tác động đến bảo mật mật mã hiện tại

Thuật toán Shor đã tạo ra những thách thức lớn cho bảo mật thông tin toàn cầu. Các tổ chức như NIST đang phát triển các thuật toán mật mã chống lại máy tính lượng tử (post-quantum cryptography). Hầu hết các nhà cung cấp dịch vụ bảo mật đều chuẩn bị kế hoạch để chuyển đổi sang các hệ thống mã hóa mới trước khi máy tính lượng tử trở nên đủ mạnh.

3.2. Phát triển mật mã lượng tử

Sự xuất hiện của thuật toán Shor đã tạo động lực cho sự phát triển của mật mã lượng tử (quantum cryptography), sử dụng các nguyên lý như vướng víu lượng tử để đảm bảo an toàn tuyệt đối của thông tin. Các hệ thống như phân phối khóa lượng tử (QKD) đang được triển khai thực tế và hứa hẹn cung cấp bảo mật mã hóa không thể phá vỡ.

IV. Triển khai và tương lai của thuật toán Shor

Hiện tại, máy tính lượng tử vẫn ở giai đoạn sơ khai, với số lượng qubit còn hạn chế (IBM vừa phát triển máy 433 qubit vào năm 2022). Để chạy thuật toán Shor hiệu quả trên các số lớn, cần hàng triệu qubit ổn định. Tuy nhiên, các nhà khoa học đã thành công trong việc triển khai thuật toán Shor trên máy tính lượng tử nhỏ bằng các nền tảng như Qiskit của IBM. Các kế hoạch phát triển máy tính lượng tử đang tiếp tục với mục tiêu đạt 100.000 qubit vào năm 2033. Khi đó, thuật toán Shor sẽ có khả năng phân tích các số nguyên lớn trong thực tế, đòi hỏi phải chuẩn bị trước các giải pháp mật mã mới.

4.1. Những thách thức kỹ thuật hiện tại

Các thách thức chính bao gồm độ lỗi cao của qubit, khó khăn trong việc duy trì vướng víu lượng tử và chồng chất lượng tử trong thời gian dài, cũng như chi phí sản xuất máy tính lượng tử rất cao. Nghiên cứu về sửa lỗi lượng tử đang tiếp tục để cải thiện độ tin cậy của các tính toán trên máy tính lượng tử.

4.2. Hướng phát triển trong tương lai

Tương lai của thuật toán Shor và máy tính lượng tử phụ thuộc vào khả năng xây dựng các máy tính lượng tử có số lượng qubit lớn và ổn định. Các nhà đầu tư toàn cầu, từ các công ty công nghệ lớn đến chính phủ các quốc gia, đang đẩy mạnh các khoản đầu tư vào lĩnh vực này với mục tiêu đạt được ưu thế lượng tử trong các ứng dụng thực tiễn.

Trích đoạn nội dung tài liệu

CHƯƠNG 1: SƠ LƯỢC VỀ MÁY TÍNH LƯỢNG TỬ VÀ THUẬT TOÁN LƯỢNG TỬ 1. Nguyên lý hoạt động của máy tính lượng tử Vào những năm cuối thế kỷ 19 đầu thế kỷ 20, trong vật lí học đã xuất hiện những hiện tượng không thể giải thích được trong khuôn khổ của vật lí cổ điển như: hiện tượng bức xạ vật đen, hiện tượng quang điện và sự sụp đổ mô hình quỹ đạo hành tinh của nguyên tử. Những cố gắng không mệt mỏi của các nhà vật lí trong việc giải thích các hiện tượng trên đã dẫn đến sự ra đời của môn vật lí lượng tử, là ngành khoa học nghiên cứu thế giới vật chất ở cấp độ vi mô: các hạt vật chất có kích thước nguyên tử và hạt nguyên tử như photon, electron và các hạt cơ bản khác. Vật lí lượng tử không chỉ là chìa khóa mở ra các bí mật của thế giới vi mô mà còn là cơ sở cho những đột phá công nghệ mới, đặc biệt là công nghệ thông tin lượng tử, bao gồm máy tính lượng tử, mật mã lượng tử và truyền thông lượng tử.

Máy tính lượng tử nếu chế tạo thành công, chắc chắn sẽ là đột phá công nghệ lớn nhất của thế kỷ 21. Và cũng tương tự như những gì kỷ nguyên máy tính điện tử đã mang đến trong những thập kỷ qua, máy tính lượng tử cũng sẽ đưa lại những thay đổi và cơ hội chưa từng có cho con người. Ý tưởng sử dụng các hạt vi mô, máy tính lượng tử được chế tạo hoạt động dựa trên các nguyên lý của cơ học lượng tử bao gồm lưỡng tính sóng hạt, nguyên lý chồng chập trạng thái, tính vướng víu lượng tử. Lưỡng tính sóng hạt Thí nghiệm khe kép của Young là một minh họa tuyệt vời cho tính chất lưỡng tính sóng – hạt của ánh sáng trong cơ học lượng [11].

Trong thí nghiệm này, một nguồn sáng phát ra ánh sáng đi qua một khe hẹp và tiếp xúc với một màn chắn, tạo ra các dải sáng và tối trên màn chắn sau đó. Cụ thể, khi hai sóng từ hai khe hẹp khác nhau gặp nhau trên màn chắn, các điểm nơi các đỉnh sóng đến cùng pha sẽ tạo ra các dải sáng, trong khi các điểm nơi các đỉnh và hõm sóng đến ngược pha sẽ tạo ra các vùng tối. Khi cường độ cúa các sóng được cộng hưởng, màn chắn sẽ chiếu sáng lên nhiều hơn; khi cường độ của chúng bị triệt tiêu nhau, màn chắn sẽ trở nên tối đi. Sự chồng chập lên nhau của các sóng ánh sáng có các tần số bằng nhau được gọi là giao thoa (Hình 1.1) và các dải sáng và tối xen kẽ nhau tạo thành từ sự giao thoa này được gọi là các vân giao thoa.

Hiện tượng này minh họa một cách rõ ràng tính chất sóng của ánh sáng. Giản đồ của thí nghiệm giao thoa giữa hai khe Young. Trong thế kỉ 19, sau khi Maxwell tổng hợp các phương trình điện từ, người ta hiểu rằng ánh sáng là sóng điện từ. Tuy nhiên, sự phân bố năng lượng của bức xạ từ vật đen không thể được giải thích hoàn toàn bằng lí thuyết điện từ.

Điều này đã dẫn đến giả thuyết của Planck vào năm 1900, đề xuất rằng ánh sáng chỉ được phát ra hoặc hấp thụ theo bội số nguyên của một năng lượng cơ bản, được biểu diễn bằng công thức: 𝐸 = ℎ𝜈 (1.1) trong đó 𝜈 là tần số ánh sáng và ℎ là hằng số Planck. Eisntein tiếp tục ý tưởng này khi ông đưa ra thuyết photon vào năm 1905, góp phần giải thích hiệu ứng quang điện và đề xuất rằng ánh sáng được hình thành từ các “hạt” gọi là photon. Các thí nghiệm của Compton vào thập niên 1920 đã cũng cố thuyết lượng tử của Einstein, chứng minh rằng photon có động lượng và xung lượng, xác nhận tính chất hạt của ánh sáng. Cùng khoảng thời gian nghiên cứu của Compton, một nhà khoa học người Pháp Louis Victor – de Broglie đưa ra ý tưởng rằng tất cả các vật chất và bức xạ có tính chất vừa giống sóng vừa giống hạt.

Ông đã liên kết các khái niệm về năng lượng, khối lượng và tần số trong một công thức 𝐸 = 𝑚𝑐 2 = ℎ𝜈 (1.2) mở ra cánh cửa cho sự hiểu biết về tính chất lưỡng tính sóng-hạt của ánh sáng và các vật chất. Qua đó ta thấy, vấn đề đặt ra ở thế kỉ XX khi tìm hiểu về ánh sáng không phải là sự tranh chấp giữa hai quan điểm để xác định quan điểm nào đúng mà lại là sự thống nhất chúng lại trong một lí thuyết mới. Ngày nay chúng ta công nhận ánh sáng có lưỡng 6 tính sóng – hạt. Hai tính chất này cùng tồn tại trong một thể thống nhất là ánh sáng và tùy điều kiện của hiện tượng khảo sát, bản chất này hay bản chất kia của ánh sáng được hiện ra.

Ta có thể coi “sóng và hạt là hai tính phụ nhau của ánh sáng. Giữa hai mặt sóng và hạt của ánh sáng có những liên hệ, có tính thống nhất, chứ không hoàn toàn là hai mặt độc lập với nhau. Cho đến đầu thế kỉ XX, việc thừa nhận sự kết hợp hai bản chất sóng và hạt đã giúp con người hiểu được một cách bao quát các đặc tính của ánh sáng. Ánh sáng không là sóng và cũng chẳng là hạt, nói ánh sáng là lưỡng tính sóng – hạt thực chất các nhà khoa học muốn đề cập đến ánh sáng như một đối tượng mới trong vật lí học mà bản chất của nó vừa giống sóng vừa giống hạt.

Quan điểm này đã thực sự khép lại những cuộc tranh luận về bản chất ánh sáng là sóng hay hạt. Nhiệm vụ của vật lí học về ánh sáng là tìm hiểu về bản chất vô cùng đặc biệt này và hơn thế nữa, đối tượng “lưỡng tính sóng – hạt” không chỉ tồn tại ở ánh sáng mà còn được suy rộng ra cho các hạt vật chất, như ta đã biết trong lí thuyết của De Broglie. Tính chồng chất lượng tử Một đơn vị nhỏ nhất biểu diễn thông tin gọi là bit, viết tắt của binary digit (chữ số nhị phân). Một bit tương ứng với một trong hai trạng thái của hệ xử lí, thông tin được biểu diễn dưới dạng các chữ số nhị phân 0 hoặc 1.

Trạng thái hệ vật lí được mô tả bằng một chuỗi nhị phân. Ví dụ, số 1 trong biểu diễn nhị phân 8 bit được viết là 00000001, số 2 được biểu thị là 00000010. Trên thực tế, mọi máy tính cổ điển đều dịch những bit này thành thông tin mà con người có thể đọc được trên thiết bị điện tử của bạn. Tài liệu bạn đọc hoặc video bạn xem được mã hóa bằng ngôn ngữ nhị phân của máy tính theo các số 1 và 0 này.

Phần cứng máy tính hiểu 1 bit là dòng điện chạy qua một dây dẫn (trong bóng bán dẫn), trong khi bit 0 thể hiện không có dòng điện chạy qua trong dây dẫn. Các tín hiệu điện này về mặt vật lí có thể được hiểu bật (ứng số 1) và tắt (ứng với số 0) của các bóng bán dẫn riêng lẻ. Nếu hệ có 𝑛 bóng bán dẫn thì chỉ có thể biểu diễn cho 2𝑛 trạng thái khác nhau. Sau đó, máy tính của bạn sẽ giải mã các bit 1 hoặc 0 cổ điển thành các từ hoặc video,… Ngoài ra, trạng thái cổ điển bóng bán dẫn chỉ có thể một trong hai trạng thái (bật-1/tắt-0) nên nó không thể thực hiện song song như tính chất lượng tử mà sẽ xét tiếp theo ở đây.

Điện toán lượng tử sử dụng các vector cơ sở trong không gian vector tuyến tính ℋ ứng với trạng thái lượng tử chuẩn hóa và trực giao lẫn nhau để biểu diễn các giá trị 1 và 7 0 của bit cổ điển. Trạng thái cơ bản trong hệ một qubit là vector cơ sở trong không gian vector tuyến tính ℋ hai chiều, ứng với hai trạng thái lượng tử cơ bản |1⟩ và |0⟩ làm đơn vị thông tin gọi là các bit lượng tử (quantum bit), gọi tắt là qubit. Một trong những đặc tính đặt một qubit khác với một bit cổ điển là nó có thể nằm ở vị trí chồng chất. Trong vật lí cổ điển, khái niệm chồng chất được sử dụng để mô tả khi hai đại lượng vật lí được cộng lại với nhau để tạo ra một đại lượng vật lí thứ ba khác hoàn toàn với hai đại lượng ban đầu.

Một ví dụ về “nguyên lý chồng chất” trong vật lí cổ điển là sự giao thoa của hai sóng. Hai xung trên một sợi dây truyền qua nhau sẽ giao thoa theo nguyên lý chồng chất như Hình 1. Nếu hai xung cùng pha thì chúng được tăng cường và ta nghe to hơn (Hình 1. Tai nghe chống ồn sử dụng sự chồng chất bằng cách tạo ra các sóng âm có cùng cường độ với sóng tới nhưng hoàn toàn lệch pha, từ đó triệt tiêu sóng âm.

Sự giao thoa mang tính triệt tiêu này được minh họa trong hình thứ hai của Hình 1. Ví dụ về sự giao thoa tăng cường (a) và triệt tiêu (b) do nguyên lý chồng chất cổ điển Tương tự trong vật lí lượng tử, một trạng thái lượng tử ở trạng thái chồng chất có thể được coi là sự kết hợp tuyến tính của các trạng thái lượng tử riêng biệt khác. Trạng thái lượng tử này ở trạng thái chồng chất tạo thành một trạng thái lượng tử hợp lệ mới. Sự chồng chất lượng tử là một hiện tượng gắn liền với các hệ lượng tử.

Các hệ lượng tử bao gồm các vật thể nhỏ như hạt nhân, electron, hạt cơ bản và photon, trong đó quan sát được lưỡng tính sóng-hạt và các hiệu ứng phi cổ điển khác. Một khía cạnh của sự chồng chất lượng tử có thể được giải thích bằng cách sử dụng sự tương tự về đồng xu. Một đồng xu có xác suất xuất hiện mặt ngửa hoặc mặt sấp là 50/50, như trong Hình 1. Tung đồng xu có 50% cơ hội rơi vào mặt ngửa hoặc mặt sấp Chúng ta có thể nói rằng đồng xu đang ở trạng thái chồng chất của cả mặt ngửa và mặt sấp.

Khi nó tiếp đất, nó có một trạng thái nhất định, là ngửa hoặc sấp. Nói chung, từ “trạng thái” có nghĩa là bất kỳ cách cụ thể nào mà hệ có thể được mô tả. Ví dụ: đồng xu có thể là mặt ngửa hoặc mặt sấp hoặc sự kết hợp của mặt ngửa hoặc mặt sấp khi tung lên trên không. Tất cả những trường hợp này được gọi là trạng thái của hệ thống đồng xu.

Trong khi đồng xu đang được lật nó ở trạng thái chồng chất.