Thực thi thuật toán Shor phân tích thừa số của số nguyên trên IBM quantum Lab

Chia sẻ: Phó Cửu Vân | Ngày: | Loại File: PDF | Số trang:5

Thêm vào BST

Báo xấu

8
lượt xem 1
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài viết "Thực thi thuật toán Shor phân tích thừa số của số nguyên trên IBM quantum Lab" trình bày về việc áp dụng thực thi thuật toán Shor dựa trên nền tảng công nghệ đã góp phần thúc đẩy sự phát triển lý thuyết về tính toán toán điện tử, đồng thời mở ra một tương lai tiềm năng cho các ứng dụng của tính toán toán lượng tử trong lĩnh vực mật mã khóa công khai, tối ưu hóa tìm kiếm và phân tích dữ liệu, cũng như nhiều thách thức mới. Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Thực thi thuật toán Shor phân tích thừa số của số nguyên trên IBM quantum Lab

Hội nghị Quốc gia lần thứ 26 về Điện tử, Truyền thông và Công nghệ Thông tin (REV-ECIT2023) Thực thi thuật toán Shor phân tích thừa số của số nguyên trên IBM quantum Lab Nguyễn Đức Công, Hoàng Mạnh Toàn, Nguyễn Đình Đồng Học viện kỹ thuật mật mã, 141 Chiến Thắng, Tân Triều, Thanh Trì, Hà Nội Email: congechipvn@gmail.com, manhtoan2100@gmail.com, dongbeng35@gmail.com Abstract— Thuật toán do Peter Shor đề xuất, được lượng tử để cải thiện hiệu quả tính toán [5]. Trước khi đặt theo tên của nhà toán học, là một thuật toán lượng tử phân tích về thuật toán Shor thám hệ mật RSA, chúng để phân tích số nguyên N trong thời gian đa thức. Thuật ta cần trình bày về biến đổi Fourier lượng tử được dùng toán này đặt ra thách thức lớn đối với sự an toàn của các trong thuật toán. Mục đích của phép biến đổi Fourier hệ thống an toàn giao dịch sử dụng mật mã khóa công trong điện toán cổ điển để chuyển đổi bài toán rất khai RSA, bởi thuật toán Shor cho phép chạy trên một phong phú, từ chuyển miền tín hiệu cần xử lý nhằm nén máy tính lượng tử có số qubit phù hợp sẽ phân tích nhanh dữ liệu đến các giải thuật đánh giá độ phức tạp tính số nguyên modulo thành tích của các thừa số nguyên tố. toán. Trong tính toán lượng tử, phép biến đổi Fourier là Trong khi, độ an toàn của thuật toán RSA phụ thuộc vào sự triển khai của biến đổi Fourier rời rạc đối với các giá thời gian phân tích số nguyên công khai N bằng tích của hai số nguyên tố lớn, do đó cách thức chung để phá vỡ hệ trị biên độ của trạng thái lượng tử. Biến đổi Fourier mật RSA nằm ở biên tính toán: với các thuật toán cổ điển lượng tử QFT (quantum Fourier transform) đóng vai thì biên này trở nên rất tốn thời gian khi số modulo N trò quan trọng của nhiều thuật toán lượng tử, nhất là ngày càng lớn, cụ thể hơn, hiện chưa có thuật toán cổ điển khi ước lượng pha trong thuật toán Shor. Biến đổi nào để phân tích số nguyên lớn N trong thời gian O(n3(log Fourier lượng tử QFT theo các trạng thái cơ sở của đầu N)). Tuy nhiên, thuật toán của Shor có thể cho phép phân tích số lớn N trong thời gian đa thức. Giống như các thuật vào j sang cơ sở mới k được thể hiện bằng ánh toán lượng tử khác, thuật toán Shor mang tính xác suất: xạ: nó đưa ra câu trả lời đúng với xác suất cao và xác suất 1 N 1 2ijk thất bại có thể giảm xuống nhờ thủ tục gọi lại nằm trong j  e N k thuật toán. N k 0 Do đó, biến đổi QFT còn được gọi là toán tử đơn vị Keywords- RSA, Shor Algorithm, Quantum Fourier (unitary) trong hệ tính toán n-qubit [1]. Transform, Quantumn Gates Thực hiện biến đổi QFT của số nguyên lớn N  2 , ký n I. GIỚI THIỆU hiệu là QFTN , để chuyển từ trạng thái lượng tử Năm 1978, thuật toán RSA được tác giả Ron x  x1...xn , ( x1 là bit có trọng số cao), sang trạng Rivest, Adi Shamir và Leonard Adleman lần đầu tiên mô tả công khai về cách mã hóa và giải mã thông tin thái lượng tử y  y1... yn sẽ có dạng như sau: theo giải pháp mới [3]. Thuật toán này mô tả một quy 1 N 1 2ixy 2 n trình mã hóa cho phép truyền thông tin một chiều với QFTN x  e y độ bảo mật cao. Phương pháp mã hóa này được sử N y 0 dụng rộng rãi trong nhiều dịch vụ ngày nay [5]. Do đó, Và khi biểu diễn giá trị trạng thái y dưới dạng phân các hệ thống sử dụng thuật toán RSA này sẽ phản ứng số nhị phân: đáng báo động, nếu ai đó xuất hiện và tuyên bố rằng họ yk yk 1 y1 n có cách bẻ khóa mã hóa. Không cố tỏ ra quá kịch tính, y   2  ...  k   yk 2k song đó thực chất là những gì mà Peter Shor đã làm khi 21 2 2 k 1 đưa ra thuật toán của mình. Và như đã đề cập, đây 1 N 1 2ixy 2n Do đó: QFTN x  e y chính là lý do tại sao thuật toán Shor thu hút sự quan N y 0 tâm rất lớn trong lĩnh vực điện toán lượng tử. Shor đã N 1 n 1   e2 ixy /2 k chỉ ra rằng, thông qua việc ứng dụng một máy tính  k y1... yn , sau khi khai triển lượng tử kiểm soát đầy đủ mọi trạng thái, thuật toán N y 0 k 1 hoàn toàn cho phép tìm ra được các giá trị khóa dùng lũy thừa dạng tổng thành tích theo các cấp số nhân sẽ trong hệ mật RSA nhanh hơn theo cấp số nhân so với được: 1  ( 0  e2 ix /2 1 ) k bất cứ thuật toán cổ điển nào [1].  N II. NỘI DUNG Tính toán lượng tử là một lĩnh vực mới, lĩnh vực này được coi là điểm giao thoa của toán học, khoa học máy tính và vật lý, nó liên quan đến việc sử dụng cơ học ISBN 978-604-80-8932-0 468
Hội nghị Quốc gia lần thứ 26 về Điện tử, Truyền thông và Công nghệ Thông tin (REV-ECIT2023) 2 ix 2 ix 2 i 2 i 1 1   0  e 22 x2  x1   ( 0 e 2 1 )( 0 e 2 2 1 ) 2 1   x2 x3...xn 2  N   2 ix 2 ix 3. Tiếp đến, áp dụng trạng thái này đi qua cổng ...  ( 0  e 2 1 n 1 )( 0 e 2 n 1) UROTn cuối cùng đối với qubit 1 và được kiểm Vì vậy, mạch thực hiện QFT để biểu diễn trạng thái soát bởi qubit xn , trạng thái của nó sẽ trở thành: lượng tử y sẽ phải sử dụng 2 cổng lượng tử: cổng 2 i 2 i 2 i 2 i thứ 1 ứng với trạng thái cơ sở 0 (có biên độ không 1   0  e 2n xn  x ... 2 x2  n 1 n 1 x1  2 2 2 1 đổi) gọi là cổng H (Hadamard) 1-qubit; và cổng thứ 2 2  ứng với trạng thái cơ sở 1 (có biên độ biến đổi) gọi là   cổng kiểm soát góc quay CROTk (Controlled Rotate)  x2 x3 ...xn Trong đó: Biểu diễn nhị phân giá trị 2-qubit với ma trận tương ứng là: x  2n1 x1  2n2 x2  ...  21 xn1  20 xn CROTk   I 0  0 UROT  , trong đó: có thể được viết thành:  k  2 i  1 0  1  x  0 e 2n 1   x2 x3 ...xn UROTk  2 i  2   k    0 e 2  4. Sau khi áp dụng một chuỗi cổng đối với n -qubit, Cổng CROTk kiểm soát góc quay sẽ xử lý các trạng thì trạng thái QFT cuối cùng là: 2 i 2 i 1   1  x  thái 2-qubit xl x j , trong đó: qubit thứ 1 thực hiện x điều khiển và qubit thứ 2 nhận trạng thái kết quả, được  0  e 2n 1   0 e 2n 1 1   2  2  thể hiện tương ứng:     CROTk 0 x j  0 x j ; 2 i 2 i 1   0  e 22 x  1  x  2 i ...  1   0  e 21 1  xj 2  2  CROTk 1x j e2 k 1x j     Đây chính xác là phép biến đổi QFT của trạng thái đầu Với 2 cổng này, phép biến đổi QFT n-qubit được khái quát thành mạch dạng vào/ra sau: vào x1 , như được dẫn xuất ở trên theo thứ tự của các 1 2 3 4 qubit bị đảo ngược ở trạng thái đầu ra. x1 H UROT2 UROTn 1 UROTn Để ứng dụng phép biến đổi QFT vào trong thuật toán x2 H UROTn  2 UROTn 1 Shor, trước tiên cần minh họa về tính chu kỳ biểu đạt các giá trị trung gian giữa các điểm đánh dấu (x). xn1 H UROT2 xn H Hình 1: Mạch biến đổi QFT n-qubit Mạch trên Hình 1 được khởi tạo hoạt động với thanh ghi trạng thái đầu vào n-qubit: 1. Sau cổng H đầu tiên trên hàng qubit thứ 1, trạng thái x1 được chuyển thành:aaaaaaaaaaaaaaaa 2 i 1  x1   0 e 2 1  H1 x1x2 ...xn  2    Hình 2: Biểu diễn chu kỳ của hàm f ( x)  a x mod N  x2 x3 ...xn Trong Hình 2, trục tung thể hiện giá trị của hàm f  x  , 2. Sau khi tới cổng UROT2 , qubit x1 này được còn trục hoành là các giá trị biến x gia tăng theo r , điều khiển bởi qubit x2 , và trạng thái của nó khởi tạo r  0 và tăng dần r  r  1 cho đến khi tìm chuyển thành: được chu kỳ của hàm f x  . ISBN 978-604-80-8932-0 469
Hội nghị Quốc gia lần thứ 26 về Điện tử, Truyền thông và Công nghệ Thông tin (REV-ECIT2023) Mạch lượng tử QFT thực hiện ước lượng chu kỳ pha QFT 1 được hiển thị trong Hình 3, thanh ghi trên cùng đếm số + Bước 4: Biến đổi Fourier nghịch đảo . Do t -qubit và thanh ghi dưới cùng chứa các qubit ở trạng QFT ánh xạ trạng thái đầu vào n -qubit thành trạng thái | . thái đầu ra dưới dạng x nên: 2 i 2 i 1 x x QFT x  e 2 1 )( 0 e 2 1 ) 2 (0 2n /2 2 i 2 i x x  ( 0 e 2n 1 1 )( 0 e 2 n 1) Thay x  2  , vào biểu thức trên thì nhận được n chính xác biểu thức tính trong bước 2 của thuật toán Shor. Vì vậy, để phục hồi trạng thái 2n  cần áp dụng Hình 3: Ước lượng pha lượng tử 1 biến đổi QFT trên một thanh ghi phụ: n 1 Dùng toán tử đơn vị Unitary, thuật toán ước lượng chu 1 2 1  e2 i k k     QFT 3  n kỳ pha  nhận được: N k 0 2 i 22 U |  e | . 2 ik 2 1 2 1  n n ( x2  ) n 1 2i  e x  n 2 Ở đây |ψ⟩ được gọi là một véc tơ riêng và e là giá 2n x 0 k 0 trị riêng tương ứng. + Bước 5: Biểu thức trên đạt giá trị cực đại xấp xỉ * Thuật toán Peter Shor: x  2 n  . Trường hợp x  Z n nhận giá trị nguyên, + Bước 1: Thiết lập  nằm trong một tập hợp các thì phép đo theo các trạng thái cơ sở tính toán đối với thanh ghi qubit. Một bộ bổ sung n -qubit tạo thành thành phần pha của thanh ghi phụ đạt được xác suất thanh ghi đếm lưu trữ giá trị 2n  : cực đại là:  4  2n    . Khi x  Z n không n | 0  | 0 | phải là một số nguyên, có thể thấy rằng biến đổi QFT-1 + Bước 2: Áp dụng n -bit hoạt động thông qua cổng vẫn đạt giá trị gần cực đại với xác suất cao hơn Hadamard trên thanh ghi đếm: 4 /  2  40% . 1 n * Thuật toán tìm chu kỳ của hàm modulo: |  1  n (| 0  | 1 ) | 1 Áp dụng thuật toán ước lượng pha lượng tử vào thực tế 22 để tìm ra chu kỳ của hàm modulo trong phép biến đổi + Bước 3: Dùng đơn vị được kiểm soát CU, áp dụng đơn vị (unitary) có dạng: toán tử đơn vị U trên thanh ghi đích khi bit điều khiển U y  ay mod N . 2 i tương ứng của nó là 1 , như U |   e |  , điều Phép biến đổi unitary U , có giá trị riêng là: này có nghĩa là 2is 2j U |  U 2 j 1 U |  U 2 j 1 2 i e |  e 2 i 2 j | U us  e r us Trong đó, véc tơ riêng tương ứng: 2j Áp dụng tất cả n hoạt động được kiểm soát, CU 2 isk 1  r với 0  j  n  1 và sử dụng quan hệ: us  e a k mod N r 0    1  e2 i   ( 0  e2 i 1 )   Vì phép biến đổi U có chứa vectơ riêng, nên trong Sẽ nhận được trạng thái mới: thành phần pha lượng tử có thông số: s , với 1 n 1 r  2  n /2 ( 0  e 2 i 2 1 )  r 1 s  Z 0 là một số nguyên thuộc khoảng từ 0 đến 2 ( 0  e 2 i 2 e 2 i 2 1 ) 1 1 r  1 , và mỗi véc tơ riêng tương ứng với một giá trị khác nhau của s . Tuy nhiên, để xác định giá trị riêng (| 0  e 2 i 2 e 2 i 2 1 )   1 0 thì cần phải biết véc tơ riêng mà không biết chu kỳ r , 2n 1 tức là, không biết các vectơ riêng. Ngược lại trong tính 1  2n /2  e2 i k k  toán lượng tử thì một chồng chất đối với tất cả các véc tơ riêng có thể biểu đạt dưới dạng: k 0 trong đó k biểu diễn số nguyên có số nhị phân n -bit. r 1 r 1 r 1 2 ikt 1 1 1 r  us  r  r  e r a k mod N t 0 t 0 k 0 ISBN 978-604-80-8932-0 470
Hội nghị Quốc gia lần thứ 26 về Điện tử, Truyền thông và Công nghệ Thông tin (REV-ECIT2023) r 1 Các tiến trình cụ thể diễn ra như sau: Và: 1  u  1 chính là thể hiện của hiện tượng + Khởi tạo các thanh ghi lượng tử: s r s 0 chồng chất lượng tử để cho phép tính toán song song các đầu ra của 1 hàm modulo, khi áp dụng thuật toán ước lượng tính các pha song song của tất cả các vectơ riêng. Tức là khi thực hiện phép đo tại các trạng thái s 2t , trong đó t là số kết quả để trả về giá trị có dạng: r r 1 qubit của thanh ghi đầu vào, s  Z 0 là số nguyên chạy 0 đến r  1 . Để xác định nhanh giá trị s , trước Thực hiện thuật toán ước lượng pha lượng tử: tiên, loại bỏ giá trị s  0 , tiếp đến, gán giá trị ngẫu nhiên để thu được số s nhỏ nhất dưới dạng: 2t 1 , do r vậy, có thể tính được chu kỳ r , bằng cách, lấy 2t chia cho giá trị s vừa tìm được. Thực hiện đo các giá trị và lưu lại kết quả: * Tìm chu kỳ theo thuật toán Shor chạy bằng công cụ Qiskit của IBM quantum Lab + Bước 1: Chọn ngẫu nhiên một số nguyên dương In ra kết quả vừa đo được: a  Z  . Sử dụng thuật toán Euclid theo thời gian đa thức để tính ước số chung lớn nhất của a và n . Nếu: gcd a, n   1 , thì xác định ngay được một thừa số không tầm thường của n . Nếu gcd a, n   1 thì chuyển sang Bước 2. Mã nguồn Python 3.11 (64-bit) Tính toán các giá trị trung bình, độ lệch và ngưỡng thực thi bước 1 như sau: (avg, stdDev, treshold) và để in ra các kết quả tìm kiếm. Trong đó: avg là trung bình số lần xuất hiện của mỗi giá trị đo được; treshold là giá trị ngưỡng trung gian được sử dụng để quyết định giá trị đo được là đủ lớn hay không nhằm loại bỏ các giá trị có xác suất thấp, chi phí thời gian tìm ra chu kỳ lớn; stdDev là độ lệch chuẩn theo phương sai của các giá trị tìm kiếm: Ví dụ, nhập liệu N=15, a=11. + Bước 2 [4]: Sử dụng máy tính lượng tử IBM quantum Lab, để xác định chu kỳ r của hàm: f x   a x mod N . Mã nguồn Python thực thi trong bước tính thứ 2 như sau: Xử lý loại bỏ các giá trị không đủ tin cậy so với ngưỡng và in ra các giá trị thỏa mãn: Trong bước này, thuật toán cần kiểm tra: -Nếu: r là số nguyên lẻ, quay lại Bước 1; -Nếu: a r 2   1  0 mod N , thì trở về Bước 1. ISBN 978-604-80-8932-0 471
Hội nghị Quốc gia lần thứ 26 về Điện tử, Truyền thông và Công nghệ Thông tin (REV-ECIT2023) Trả về giá trị chu kỳ r tìm được: nghiên cứng ứng dụng quan tâm và được đánh giá là một trong những thuật toán lượng tử quan trọng nhất cho đến hiện nay. Thuật toán này đã có những minh chứng về lời giải của bài toán RSA với thời gian tính toán đa thức, trong khi các thuật toán cổ điển cần thời gian tính toán lũy thừa. Việc áp dụng thực thi thuật toán Shor dựa trên nền tảng công nghệ đã góp phần Thời gian tìm chu kỳ r của hàm modulo ứng với thúc đẩy sự phát triển lý thuyết về tính toán toán điện N=15 và a=11 như sau: tử, đồng thời mở ra một tương lai tiềm năng cho các ứng dụng của tính toán toán lượng tử trong lĩnh vực mật mã khóa công khai, tối ưu hóa tìm kiếm và phân tích dữ liệu, cũng như nhiều thách thức mới. Do đó, tiếp theo các tác giả sẽ định hướng thực thi thuật toán này với năng lực xử lý số qubit lớn hơn và kiểm chứng hiệu năng khi phân tích các số nguyên lớn dùng trong RSA, ECDSA. TÀI LIỆU THAM KHẢO [1]. Daniel Koch, Saahil Patel, Laura Wessing1, Paul M. Alsin, “Fundamentals In Quantum Algorithms: A Tutorial Series Using Qiskit Continued”, Air Force Research Lab, Information Directorate, Rome, NY; + Bước 3: Sử dụng thuật toán Euclid để tính:     [2]. P. W. Shor, "Polynomial-Time Algorithms for Prime p  gcd a r 2  1, N . Do a r 2  1  0 mod N , nên Factorization and Discrete Logarithms on a Quantum Computer", SIAM JSC. 26 (1997); dễ dàng thấy rằng, p là một thừa số không tầm thường [3]. R. Rivest, R. Shamir, L. Adleman, "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems", n của N , do đó, nhận được thừa số kia là: q  . Mã Communications of the ACM. (2): p 120–126 (1978); [4]. S. Beauregard, "Circuit for Shor's algorithm using 2n+3 qubits", nguồn thực thi bước 3 như sau: Quantum Information and Computation (2): 175-185 (2003); [5]. P. Kaye, R. Laflamme, M. Mosca, "An Introduction to Quantum Computing", Oxford, Oxford University Press (2007). Và kết quả chương trình xác định được các thừa số nguyên tố ứng với số N=15 là: Bảng thống kê thời gian tìm chu kỳ r khi chạy thuật toán Shor ứng với các số N=15 ( r  2 ): Chọn giá Chu kỳ Thời gian chạy (giây) trị a r 2 4 3.2227866649627686 3 # 0.0 4 2 3.0794670581817627 5 # 0.001134634017944336 6 # 0.0 7 4 3.0896317958831787 8 # 3.0557498931884766 9 # 0.0 10 # 0.0 11 2 3.0271942615509033 12 # 0.0 13 4 3.175997257232666 14 2 # III. KẾT LUẬN Kể từ khi được xuất bản lần đầu tiên vào năm 1995 [2], thuật toán Peter Shor đã được nhiều nhà ISBN 978-604-80-8932-0 472