ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ĐẶNG ĐÌNH SƠN PHÂN TÍCH CARTAN TRONG ĐẠI SỐ LIE VÀ CÀI ĐẶT MỘT SỐ THUẬT TOÁN LƯỢNG TỬ Chuyên ngành: Đại số lí thuyết số Mã số: 60.46.01.04 LUẬN VĂN THẠC SĨ KHOA HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC GS.TSKH ĐỖ NGỌC DIỆP Hà Nội - 2014 LỜI CẢM ƠN Tác giả xin chân thành gửi lời cảm ơn sâu sắc tới GS TSKH Đỗ Ngọc Diệp, Viện Toán học, Viện Hàn lâm Khoa học Cơng nghệ Việt Nam Người thầy đáng kính, tạo điều kiện giúp đỡ, dày công hướng dẫn để tác giả hoàn thành luận văn Tác giả xin chân thành cảm ơn thầy cô khoa Toán - Tin - Cơ học, trường Đại học Khoa Học Tự Nhiên Hà Nội nói chung thầy mơn Đại số - Hình học - Tô Pô Các thầy cô truyền đạt cho chúng tơi nhiều kiến thức khoa học bổ ích tạo điều kiện tốt cho trình học tập nghiên cứu Xin chân thành cảm ơn bạn bè, đồng nghiệp, người thân động viên giúp đỡ suốt trình học tập thực luận văn Hà Nội, tháng 11 năm 2014 Đặng Đình Sơn MỤC LỤC Lời cảm ơn Mục lục Danh mục ký hiệu, chữ viết tắt MỞ ĐẦU Chương - TỔNG QUAN Tổng quan thuật toán lượng tử 1.1 Các khái niệm tính tốn lượng tử 1.1.1 Thanh ghi lượng tử 1.1.2 Đo lượng tử 10 1.1.3 Cổng lượng tử 12 1.2 Thuật toán lượng tử .15 1.2.1 Thuật toán lượng tử mức tổng quát 16 1.2.2 Mơ hình dây 17 Một số kiến thức chuẩn bị 21 2.1 Giới thiệu nhóm Lie Đại số Lie nhóm Lie 21 2.2 Cấu trúc su(N ) so(N ) .27 2.2.1 Hệ nghiệm nhóm Lie 27 2.2.2 Cấu trúc su(N ) .29 2.2.3 Cấu trúc so(2N ) .31 Kết luận .33 Chương - PHÂN TÍCH CARTAN .34 Mở đầu .34 Phân tích Cartan chuẩn 37 2.1 Phân tích khơng gian nghiệm 37 2.2 Phân tích Cartan chuẩn 40 Phân tích su(N ) 42 Phân tích so(2N ) 46 Kết luận 50 Chương - CÀI ĐẶT MỘT SỐ THUẬT TOÁN LƯỢNG TỬ 51 Phép biến đổi hoán vị 51 Cài đặt phép chuyển đổi dịch bít 53 Cài đặt phép biến đổi Fourier .57 Kết luận 58 KẾT LUẬN .59 TÀI LIỆU THAM KHẢO .60 Danh mục ký hiệu, chữ viết tắt Trong luận văn này, dùng thống sử dụng kí hiệu viết tắt sau: Ký hiệu U (n): nhóm unita cấp n; SU (n): nhóm unita cấp n có định thức đơn vị; SO(n): nhóm trực giao cấp n có định thức đơn vị; u(n): đại số Lie U (n); su(n): đại số Lie SU (n); so(n): đại số Lie SO(n) ; P r(A): xác suất xảy biến cố A; G g : nhóm Lie đại số Lie tương ứng; T t : xuyến tối đại chuẩn đại số Lie tương ứng; H :phép biến đổi Hadamard; F : phép biến đổi Fourier lượng tử ; Uf : hộp đen lượng giá hàm mẫu f ; Viết tắt Qubit: Bit lượng tử MỞ ĐẦU Lí chọn đề tài Lí thuyết Lie đời tương tự liên tục cho lí thuyết nhóm Galois Nó ứng dụng trước hết vào lí thuyết phương trình vi phân Mỗi biểu thức bất biến tác động nhóm Lie cho tích phân đầu hệ phương trình vi phân cho ta phép hạ bậc hệ Nói cách khác hệ mô tả chuyển động học hay vật lí tích phân đầu cho ta định luật bảo tồn Tìm nhiều định luật hệ dễ dàng giải triệt để Một ứng dụng khác lí thuyết Lie lí thuyết đối xứng học vật lí Các hệ học vật lí có đối xứng đóng vai trò quan trọng việc nghiên cứu hệ học vật lí nói chung Mỗi hệ học có nhóm đối xứng tương ứng với đa tạp symplectic có đối xứng, khơng gian Mỗi hệ lượng tử có đối xứng, tương ứng với biểu diễn unita nhóm đối xứng Lí thuyết nhóm lượng tử đời ứng dụng nhóm Lie Năm 1982, Feynman khẳng định “một hệ học lượng tử khơng thể mơ hình hệ cổ điển, mà mơ hình hệ học lượng tử khác” lần đề xuất sử dụng hệ lượng tử thực việc tính tốn, khai sinh ý tưởng sử dụng hiệu ứng học lượng tử để làm tính tốn Khả lưu trữ theo cấp số nhân, kết hợp với số hiệu ứng rối lượng tử (quantum entanglement), dẫn nhà nghiên cứu thăm dị sâu vào sức mạnh máy tính lượng tử Tính tốn lượng tử có khả có khả cách mạng hóa lĩnh vực khoa học máy tính nhiên, tính tốn lượng tử giai đoạn phơi thai, khả đạt bao xa câu hỏi mở Có ba hoạt động diễn ba ngành khoa học khác Các nhà vật lý tìm cách chế tạo máy tính lượng tử; nhà tốn học xây dựng mơ hình tính tốn lượng tử; nhà tin học tìm kiếm thuật tốn lượng tử xây dựng ngơn ngữ mơ tính tốn lượng tử Trong lúc chờ đợi nhà vật lý khắc phục rào cản công nghệ để xây dựng máy tính lượng tử, nghiên cứu thuật toán phải tiến hành Ở Việt Nam, xem việc nghiên cứu tính tốn lượng tử khởi đầu vào năm 2004 với số báo tổng quan Tạp chí Ứng dụng Toán học Đỗ Ngọc Diệp (2004), Cao Long Vân (2005, 2006); số báo cáo hội thảo thành viên nhóm Phan Trung Huy (2004, 2005, 2006); Luận văn Tiến sĩ Công nghệ thông tin Huỳnh Văn Đức (2012) Như vậy, xây dựng thuật toán lượng tử lĩnh vực mẻ có sức hút, hội tầm quan trọng Mục đích nghiên cứu Từ cấu trúc số đại số Lie đặc biệt nhóm biến đổi unita, phân tích Cartan đại số Lie nửa đơn, hữu hạn chiều xây dựng số thuật tốn phân tích phép biến đổi Từ cài đặt số thuật tốn lượng tử (Phần thuật tốn lượng tử phép biến đổi unita) Đối tượng, phạm vi nghiên cứu Đối tượng nghiên cứu luận văn phép biến đổi unita Phạm vi nghiên cứu luận văn giới hạn hộp đen phép biến đổi trực giao Phương pháp nghiên cứu Nghiên cứu thông qua tài liệu, sách báo, internet Trình bày hệ thống lại kiến thức tường minh chứng minh Trao đổi nghiên cứu với giáo viên hướng dẫn Ý nghĩa khoa học Áp dụng thành công công cụ lý thuyết nhóm cho thấy sử dụng kết toán học đại xây dựng thuật toán lượng tử Cấu trúc luận văn Luận văn gồm chương - Chương Tổng quan - Chương Phân tích Cartan - Chương Cài đặt số thuật toán lượng tử CHƯƠNG - TỔNG QUAN Có thể xem khác biệt máy tính lượng tử so với máy tính cổ điển nằm điểm chính: qubit so với bit, cổng lượng tử so với phép toán logic Trong lúc bit lưu giá trị 1, qubit lưu đồng thời hai giá trị dạng chồng chất trạng thái mà kết hợp lại thành ghi, ghi cổ điển lưu giá trị ghi lượng tử có khả lưu tất giá trị quan tâm, dạng chồng chất trạng thái Ngoài lúc phép toán logic nhận bit đầu vào trả kết cho bit đầu ra, cổng lượng tử tác động lên qubit làm thay đổi nó, nghĩa xử lý đồng thời giá trị nằm thạng thái chồng chất Như máy tính lượng tử ưu việt máy tính cổ điển chỗ có khả lưu trữ xử lý đồng thời giá trị quan tâm Một thuật toán lượng tử chất phép biến đổi unita, cài đặt thuật toán lượng tử phân tích phân tích phép biến đổi unita thành cổng lượng tử (là phép biến đổi unita cho trước) Đại số Lie so(n) su(n) đại số phép biến đổi tuyến tính đặc biệt có vai trị quan trọng việc cài đặt thuật tốn lượng tử Trong chương chúng tơi giới thiệu tổng quan thuật toán lượng tử số kiến thức đại số Lie so(n) su(n) Tổng quan thuật toán lượng tử 1.1 Các khái niệm tính tốn lượng tử Các khái niệm tính toán lượng tử bao gồm: ghi lượng tử, đo lượng tử, cổng lượng tử Trong mục giới thiệu số phép biến đổi unita quan trọng thường dùng xây dựng thuật toán lượng tử 1.1.1 Thanh ghi lượng tử Tại thời điểm, lúc bit cổ điển nhận hai giá trị 1, bit lượng tử (được gọi qubit) lại nhận đồng thời hai giá trị Dùng ký hiệu bra-ket (Paul Dirac, 1902-1984), qubit hệ vật lý gồm trạng thái |b = α0 |0 + α1 |1 với α0 , α1 số phức thỏa mãn |α0 |2 + |α1 |2 = {|0 , |1 } sở tắc C2 Thanh ghi lượng tử lưu trữ đồng thời giá trị tính tốn hình thành phân bố xác suất xác định Một ghi n qubit hệ vật lý gồm trạng thái 2n −1 |ψ = αk |k (1.1) k=0 n −1 với số phức αk thỏa mãn k=0 n −1 |αk |2 = {|k }2k=0 sở tắc (C2 )⊗n Trạng thái tổng quát (1.1) gọi trạng thái chồng chất  ⇒ G = Ad             e−i  −1       −1       −1       −1  α−β e−iβ e i α+β       Phân tích so(2N ) Kí hiệu t {Exy , Fxy , Xxy , Yxy } (1.36),(1.37) Đặt l = {Exy , Yxy }x : |xk−1 |x1 |x0 → |x0 |xk−1 |x1 Với n =  G = U>> 1         1 =           GAdσz ⊗I2 GT =   = AdΛσx ⊗I   1  −1  ⊗  ⊗  −1 53 −1  ⊗ (3.2)                       ⊗  1    ta có K11 = I, K12 = σx ⊗ I ⇒ K1 = Λσx ⊗ I         1 ⊗ ,S =  ⊗  C= 1          1 ⊗  suy K2 = AT K1T G = K21 ⊕ K22 = chọn A =      1       1            1  ⊗        1      1       1 ⊗ ⊗  K2 AdI⊗σz ⊗I K2T =  −1 −1       1 ⊗ ⊗  = AdΛσx  1 −1     0  , S2.1 = S2.2 =   Ta có K2.1 = I ⊗ Λσx , C2.1 = C2.2 =  0 54     ⊗ Chọn A2 =          1  suy     T K2.2 = AT2 K2.1 K2 = K2.21 ⊕ K2.22 = Λσx    1 ⊗    1        Vì K2.22 = Adσx ⊗I (Λσx ) ta có K2.2 = AdΛσx ⊗I (I ⊗ Λσx ) Vậy G = K1 AK2 = K1 AA2 K2.2 = (Λσx ⊗ I) AA2 AdΛσx ⊗I (I ⊗ Λσx ) Để ý K22 có cách nhân ma trân cổng XOR với K21      1             1   =   = (σx ⊗ I) K21 K22 =       1  1        1 Theo mệnh đề 3.1  n n T U>> Adσx ⊗ (U>> ) =  = AdΛσx ⊗I   1  −1  ⊗  ⊗  −1  −1   ⊗ In−2  ⊗ In−2  Ta có K1 = Λσx ⊗ In−2 cổng lượng tử nên khơng cần phân tích tiếp Do 55 (4.4), ta chọn:     A=    Ta có: n−1 Kí hiệu U>>  1   1  ⊗ In−2      U U  11 12      U U 11 12 n  K2 = AT K1T U>> =    U21 U22    U21 U22    U11 U12  = (Λσx ⊗ In−2 ) I ⊗  U21 U22   U11 U12 , đề nghị Thuật tốn 2.3 Từ = U21 U22 ta có:  n U>> = (Λσx     ⊗ In−2 )      1       1  ⊗ In−2  (Λσ ⊗ In−2 ) I ⊗ U n−1 >> x       Tương tự cho trường hợp dịch chuyển trái Vậy, áp dụng Thuật toán 2.3, 56 (3.2) cài đặt với độ phức tạp tuyến tính Cài đặt phép biến đổi Fourier Phép biến đổi Fourier, ký hiệu F 2n −1 2πi e 2n x.y |y F |x = (3.3) y=0 Tường minh số qubit, ta biết F1 = H (Phép biến đổi Hadamard (1.10)), ta phát triển từ Fn lên Fn−1 Xét F1 , thêm qubit nhân dòng với w = exp 2πi/2n+1 , chuyển vị cột, cộng trừ cặp dòng  1    −1 H  = √1  F1 → F2 = √  2  H 1  −1   1     −1    →√   2 1     −1   1     −1    →√   2 1     i −i   57           1 1     i −1 −i    →√    −1 −1     −i i Tổng quát: Fn → I ⊗ Fn → (I ⊗ Fn ) U>> → Dn+1 (I ⊗ Fn ) U>> → (H ⊗ I) Dn+1 (I ⊗ Fn ) U>> = Fn+1 Trong Dn = diag 1, 1, , 1, w0 , w1 , w2 , , wN −1 Kết luận Trong chương chúng tơi sử dụng thuật tốn phân tích trình bày chương cài đặt hộp đen hốn vị (3.1), hộp đen chuyển dịch bít (3.2), thuật tốn có vai trị quan trọng cài đặt hộp đen phép biến đổi Ứng dụng (3.2) cài đặt phép biến đổi Fourier 58 KẾT LUẬN Nội dung luận văn: Phân tích Cartan đại số Lie nửa đơn, áp dụng cụ thể su(N ) so(2N ) Chọn phân tích Cartan hạng cực đại từ xuyến tối đại chuẩn nhóm tương ứng, thủ tục xây dựng có kết hợp phân tích khơng gian nghiệm Áp dụng phân tích đồng thời phép biến đổi hoán vị, cung cấp cách cài đặt khác phép biến đổi nhóm hốn vị, tùy thuộc ý đồ người xây dựng thuật toán giải toán cụ thể Tác giả trình bày xếp nội dung kiến thức khoa học cách hệ thống, chi tiết hóa chứng minh phân tích xây dựng hệ thống ví dụ 59 TÀI LIỆU THAM KHẢO Tiếng Việt Đỗ Ngọc Diệp, Lí thuyết nhóm Lie (Preprint) Huỳnh Văn Đức, Đỗ Ngọc Diệp, Bùi Doãn Khanh (2009), “Tiếp cận đại số xây dựng thuật tốn lượng tử”, Tạp chí Ứng dụng Tốn học, Tập VII, số 01, 06-2009, pp 093-110 Huỳnh Văn Đức (2012), Xây dựng thuật toán lượng tử giải tốn tìm kiếm với tri thức Heuristic, Luận án Tiến sĩ Công nghệ thông tin, Đại học Quốc Gia TP Hồ Chí Minh Tiếng Anh Agaian, S S and Klappenecker, A (2002), Quantum Computing and a Unified Approach to Fast Unitary Transforms, arXiv:quant-ph/0201120v1 5.Dagli, M (2008), Lie algebra decompositions with applications to quantum dynamics, PhD Thesis, Iowa State University, Ames, Iowa Deutsch, D (1985), "Quantum theory, the Church-Turing principle and the universal quantum computer", Proceedings of the Royal Society of London A 400, pp 97-117 Deutsch, D (1989), "Quantum computational networks", Proc R Soc Lond A, Vol.425 No.1868, pp 73-90 60 ... số đại số Lie đặc biệt nhóm biến đổi unita, phân tích Cartan đại số Lie nửa đơn, hữu hạn chiều xây dựng số thuật tốn phân tích phép biến đổi Từ cài đặt số thuật tốn lượng tử (Phần thuật tốn lượng. .. quan thuật toán lượng tử số kiến thức đại số Lie so(n) su(n) Tổng quan thuật toán lượng tử 1.1 Các khái niệm tính tốn lượng tử Các khái niệm tính tốn lượng tử bao gồm: ghi lượng tử, đo lượng tử, ... nhóm Lie Định nghĩa 1.6 Giả sử G nhóm Lie, phần tử đơn vị e Khi khơng gian tiếp xúc Te G G e với tích Lie gọi đại số Lie nhóm Lie G kí hiệu g = LieG Đại số Lie số nhóm Lie LieR ∼ =R LieS ∼ =R LieGLn