Tài liệu Xây dựng thuật toán lượng tử giải bài toán tìm kiếm với tri thức heuristic

ĐẠI HỌC QUỐC GIA TP. HCM ĐẠI HỌC KHOA HỌC TỰ NHIÊN Huỳnh Văn Đức XÂY DỰNG THUẬT TOÁN LƯỢNG TỬ GIẢI BÀI TOÁN TÌM KIẾM VỚI TRI THỨC HEURISTIC LUẬN ÁN TIẾN SĨ CÔNG NGHỆ THÔNG TIN Tp. Hồ Chí Minh – Năm 2013 ĐẠI HỌC QUỐC GIA TP. HCM ĐẠI HỌC KHOA HỌC TỰ NHIÊN Huỳnh Văn Đức XÂY DỰNG THUẬT TOÁN LƯỢNG TỬ GIẢI BÀI TOÁN TÌM KIẾM VỚI TRI THỨC HEURISTIC Chuyên ngành: KHOA HỌC MÁY TÍNH Mã số chuyên ngành: 62 48 01 01 Phản biện 1: PGS.TS. Phan Trung Huy Phản biện 2: PGS.TS. Lê Anh Vũ Phản biện 3: TS. Trần Nam Dũng Phản biện độc lập 1: PGS.TS. Đoàn Văn Ban Phản biện độc lập 2: TS. Hồ Trung Dũng Phản biện độc lập 3: PGS.TS. Bùi Xuân Hải NGƯỜI HƯỚNG DẪN KHOA HỌC 1. GS.TSKH. Đỗ Ngọc Diệp 2. GS.TSKH. Bùi Doãn Khanh Tp. Hồ Chí Minh – Năm 2013 ii Chân thành tri ân: GS. TSKH. Đỗ Ngọc Diệp, Viện Toán học, Viện Khoa học và Công nghệ Việt Nam; GS. TSKH. Bùi Doãn Khanh, Đại học Paris VI, Cộng hòa Pháp. Những người thầy đáng kính, đã dày công hướng dẫn và giúp đỡ tác giả hoàn thành luận án này. iii Tác giả xin chân thành cảm ơn:  Quý Thầy Cô Khoa Công nghệ Thông tin, Trường Đại học Khoa học Tự nhiên, Đại học Quốc Gia TP.HCM;  Quý Thầy Cô, Nhân viên Khoa Hệ thống Thông tin kinh doanh, Trường Đại học Kinh Tế TP.HCM;  Quý Thầy Cô, Nhân viên Trường Đại học Kinh Tế TP.HCM; bởi sự quan tâm giúp đỡ tận tâm và thiết thực trong quá trình nghiên cứu cũng như trong quá trình hoàn thành luận án. Xin chân thành cám ơn quý Giáo sư, Phó Giáo sư đã đọc và góp ý chân thành để tác giả hoàn thiện luận án. Xin chân thành cảm ơn bạn bè, đồng nghiệp, những người thân đã động viên giúp đỡ trong suốt quá trình thực hiện luận án. Cuối cùng xin cảm ơn người vợ thân yêu và hai con ngoan đã đóng góp giá trị tinh thần to lớn để chồng, cha hoàn thành công việc. Tp. Hồ Chí Minh, tháng 01 năm 2013 Huỳnh Văn Đức iv Lời cam đoan Tôi xin cam đoan đây là công trình nghiên cứu của tôi dưới sự hướng dẫn của tập thể giáo sư hướng dẫn. Các kết quả được nêu trong luận án là trung thực và chưa từng được ai công bố trong bất kỳ công trình nào khác. Huỳnh Văn Đức v Mục lục Lời cam đoan ............................................................................................................. iv Mục lục ........................................................................................................................v Danh mục các ký hiệu, các chữ viết tắt ..................................................................... ix Danh mục các hình vẽ, đồ thị ......................................................................................x MỞ ĐẦU .....................................................................................................................1 Chương 1 1. 2. 3. 4. TỔNG QUAN ...................................................................................10 Các khái niệm cơ bản của tính toán lượng tử ..............................................10 1.1. Thanh ghi lượng tử ...............................................................................10 1.2. Đo lượng tử ...........................................................................................12 1.3. Cổng lượng tử .......................................................................................14 Thuật toán lượng tử .....................................................................................16 2.1. Thuật toán lượng tử mức tổng quát ......................................................16 2.2. Mô hình dây ..........................................................................................18 2.3. Chương trình con ..................................................................................23 Tích nửa trực tiếp.........................................................................................25 3.1. Khái niệm ..............................................................................................25 3.2. Tích bện ................................................................................................26 Cấu trúc đại số Lie .......................................................................................27 4.1. Hệ nghiệm của nhóm Lie ......................................................................28 4.2. Cấu trúc của su(N) ................................................................................29 vi 4.3. Cấu trúc của so(2N) ..............................................................................31 4.4. Nhóm Weyl ...........................................................................................33 5. Phép biến đổi Hough ...................................................................................34 6. Kết luận........................................................................................................37 Chương 2 - THUẬT TOÁN TÌM MẪU ...............................................................38 1. Mở đầu .........................................................................................................38 2. Phép biến đổi Hough và nhóm ....................................................................42 3. 4. 5. 2.1. Phép biến đổi Hough cơ bản .................................................................42 2.2. Phép biến đổi Hough tổng quát ............................................................43 2.3. Tổng quát hóa .......................................................................................44 2.4. Thuật toán tìm mẫu ...............................................................................47 Xây dựng thuật toán tìm mẫu ......................................................................48 3.1. Mô tả hàm Boole quyết định ................................................................48 3.2. Cài đặt hàm Boole quyết định ..............................................................51 3.3. Bổ sung heuristic ..................................................................................57 Các ví dụ minh họa ......................................................................................60 4.1. Tìm mẫu tịnh tiến ..................................................................................60 4.2. Tìm chu trình Hamilton ........................................................................64 Kết luận........................................................................................................65 Chương 3 - HỘP ĐEN ..........................................................................................67 1. Mở đầu .........................................................................................................68 2. Biểu diễn hộp đen ........................................................................................71 2.1. Chéo hóa đồng thời các hộp đen ...........................................................72 vii 2.2. 3. 4. 5. Biểu diễn hộp đen qua đại số Lie..........................................................73 Hai cơ sở của đại số Lie của xuyến tối đại chuẩn .......................................75 3.1. Cơ sở chuẩn ..........................................................................................76 3.2. Cơ sở Hadamard ...................................................................................77 3.3. Họ các tổ hợp tuyến tính ngắn ..............................................................78 3.4. Cài đặt cơ sở W .....................................................................................79 3.5. Cài đặt cơ sở W con và cơ sở B ............................................................81 Cài đặt ..........................................................................................................87 4.1. Cài đặt các cổng tịnh tiến......................................................................88 4.2. Cài đặt các cổng so sánh .......................................................................90 4.3. Hộp đen nhóm hoán vị ..........................................................................94 Kết luận......................................................................................................100 Chương 4 - PHÂN RÃ ........................................................................................102 1. Mở đầu .......................................................................................................102 2. Phân rã Cartan chuẩn .................................................................................106 2.1. Phân rã không gian nghiệm ................................................................106 2.2. Phân rã Cartan chuẩn ..........................................................................111 3. Phân rã su(N) .............................................................................................113 4. Phân rã so(2N) ...........................................................................................116 5. Cài đặt ........................................................................................................120 6. 5.1. Phép biến đổi hoán vị..........................................................................120 5.2. Cài đặt phép biến đổi dịch chuyển bit ................................................121 Kết luận......................................................................................................128 viii KẾT LUẬN .............................................................................................................129 KIẾN NGHỊ ............................................................................................................130 DANH MỤC CÔNG TRÌNH CỦA TÁC GIẢ .......................................................131 TÀI LIỆU THAM KHẢO .......................................................................................132 CHỈ MỤC ................................................................................................................142 ix Danh mục các ký hiệu, các chữ viết tắt Trong suốt luận án này, chúng tôi dùng thống nhất: Ký hiệu  U(n): nhóm unita cấp n;  SU(n): nhóm unita cấp n có định thức bằng đơn vị;  SO(n): nhóm trực giao cấp n có định thức bằng đơn vị;  u(n): đại số Lie của U(n);  su(n): đại số Lie của SU(n);  so(n): đại số Lie của SO(n) ;  Pr(A): xác suất xảy ra biến cố A;   f : B n  B m  : tập mẫu ; trong đó, B = {0, 1} và các thành phần của  x  B k được đánh số từ bên phải x   xk 1 , , x1 , x0   xk 1 x1x0 ;  G và g : nhóm Lie và đại số Lie tương ứng;  T và t : xuyến tối đại chuẩn và đạ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;  Gf : phần chính của thuật toán Grover áp dụng lên hàm Boole f;  U : phép biến đổi được điều khiển (U tác động khi điều kiện được thỏa). Viết tắt  Qubit: bít lượng tử;  HSP: bài toán tìm nhóm con ẩn, thường là của nhóm giao hoán;  NHSP: bài toán tìm nhóm con ẩn của nhóm không giao hoán. x Danh mục các hình vẽ, đồ thị Hình 1.1: Một trạng thái thanh ghi 2 qubit ...............................................................11 Hình 1.2: inh họa thuật toán lượng tử dạng tổng quát. ..........................................18 Hình 1.3: Cổng Hadamard ........................................................................................19 Hình 1.4: Các cổng chuyển pha 1 và 2 qubit ............................................................19 Hình 1. : Các cổng Pauli ..........................................................................................19 Hình 1. : Cổng CNOT ..............................................................................................19 Hình 1. : Thuật toán Deutsch – Jozsa.......................................................................20 Hình 1. : Phần chính của thuật toán Grover. ............................................................21 Hình 1. : Thuật toán xấp xỉ pha. ...............................................................................22 Hình 1.10: Thuật toán tìm chu kỳ. ............................................................................22 Hình 1.11: Cổng Deutsch – Toffoli. .........................................................................24 Hình 1.12: Phép biến đổi Fourier. .............................................................................25 Hình 2.1: ạng XOR p trong q ................................................................................54 Hình 2.2: ạng bầu cho h bởi q................................................................................55 Hình 2.3: ạng tính tích hai mẫu .............................................................................56 Hình 2.4: ạng bầu h bởi p ......................................................................................56 Hình 2. : ạng bầu h bởi p tổng quát ......................................................................57 Hình 2. : ạng bầu k bởi p dùng heuristic h. ...........................................................60 Hình 3.1: Dạng cột của cơ sở B. ...............................................................................76 Hình 3.2: Dạng cột của cơ sở W. ..............................................................................78 xi Hình 3.3: Thuật toán cài đặt phép toán cộng lượng tử U+ ........................................89 Hình 3.4: Thuật toán cài đặt phép cộng với hằng U+k...............................................90 Hình 3. : inh họa cài đặt hộp đen so sánh bằng ....................................................92 Hình 3. : inh họa cài đặt hộp đen so sánh lớn hơn ...............................................93 Hình 3. : inh họa cài đặt hộp đen nhóm hoán vị ...................................................97 MỞ ĐẦU Tính toán lượng tử có khả năng cách mạng hóa lĩnh vực khoa học máy tính; tuy nhiên, tính toán lượng tử vẫn đang ở trong giai đoạn phôi thai, khả năng của nó có thể đạt bao xa vẫn còn một câu hỏi mở [15]. Có ba hoạt động đang cùng diễn ra trên ba ngành khoa học khác nhau. Các nhà vật lý tìm cách chế tạo ra máy tính lượng tử; các nhà toán học xây dựng các mô hình tính toán lượng tử; và các nhà tin học tìm kiếm các thuật toán lượng tử và xây dựng ngôn ngữ mô phỏng tính toán lượng tử. Trong lúc chờ đợi các nhà vật lý khắc phục được các rào cản công nghệ để xây dựng máy tính lượng tử, các nghiên cứu về thuật toán vẫn phải được tiến hành. Ở Việt Nam, có thể xem việc nghiên cứu về tính toán lượng tử được khởi đầu vào năm 2004 với một số bài báo tổng quan trên Tạp chí Ứng dụng Toán học của Đỗ Ngọc Diệp (2004), Cao Long Vân (2005, 2006); một số báo cáo hội thảo của các thành viên nhóm Phan Trung Huy (2004, 2005, 2006); về nhóm này, đáng chú ý có 1 đề tài cấp bộ (2006), 1 luận văn thạc sĩ (2011), và phần mềm VQS mô phỏng trên máy tính truyền thống hiện nay (được giới thiệu lần đầu vào năm 2005). Như vậy việc tìm ra các thuật toán lượng tử hiệu quả luôn có ý nghĩa lớn và rất được quan tâm. Cho đến nay chỉ mới xuất hiện một số thuật toán đáng kể, mang tính đột phá mạnh mẽ, có thể xem chi tiết ở các tài liệu mang tính khảo sát, đánh giá và tổng hợp như [5], [ ]. Các nghiên cứu về thuật toán lượng tử vẫn không ngừng được quan tâm ở nhiều khía cạnh khác nhau: liên quan đến đến cấu trúc [1], đến kỹ thuật [10], [27], đến cơ sở lý thuyết nhóm [14], đến các dạng bài toán khác nhau [37], [77], và đến mô hình tính toán [64]. Để biết thêm chi tiết về các khái niệm cơ sở của tính toán lượng tử có thể xem ở các tài liệu, mà phần lớn là sách, như [7], [40], [52], [67], [84], [89], [99], và [101]. 2 Trong phần mở đầu này chúng tôi trình bày về lý do lựa chọn đề tài; mục đích, đối tượng, phạm vi nghiên cứu và ý nghĩa của đề tài luận án; những kết quả liên quan mật thiết đến đề tài luận án; những tồn tại cần giải quyết; cơ sở lý thuyết, lý luận, giả thiết khoa học và phương pháp nghiên cứu. Ngoài ra chúng tôi cũng giới thiệu vắn tắt về tính toán lượng tử và bài toán tìm kiếm. Giới thiệu Máy tính lượng tử. Kích thước của các đơn vị cơ bản dùng để xây dựng các cấu trúc mạch của máy tính ngày càng nhỏ, đến lúc nào đó hoạt động của chúng phải tuân theo quy luật của vật lý lượng tử. Năm 1982, Feynman [43] đã khẳng định “một hệ cơ học lượng tử không thể được mô hình bởi các hệ cổ điển, mà chỉ có thể được mô hình bởi một hệ cơ học lượng tử khác” và lần đầu tiên đề xuất sử dụng hệ lượng tử thực hiện việc tính toán, khai sinh ý tưởng sử dụng các hiệu ứng cơ học lượng tử để làm tính toán. Khả năng lưu trữ theo cấp số nhân, kết hợp với một số hiệu ứng như rối lượng tử (quantum entanglement), đã dẫn các nhà nghiên cứu thăm dò sâu hơn vào sức mạnh của máy tính lượng tử. Mô hình tính toán lượng tử. Deutsch lần đầu tiên đặt ra câu hỏi “liệu có thể tính toán trên máy tính lượng tử hiệu quả hơn trên máy tính cổ điển?” [34]. Trả lời câu hỏi này cần phải đưa ra mô hình tính toán cũng như các thuật toán có thể được thực hiện trên đó. Về mô hình máy tính lượng tử, vào năm 1982, Feynman phác thảo một mô hình máy tính lượng tử trừu tượng [43]; năm 1985, Deutsch đưa ra mô hình máy tính lượng tự phổ dụng và mô hình máy Turing lượng tử; năm 1989, Deutsch tiếp tục đưa ra mô hình mạng tính toán lượng tử, còn được gọi mô hình dây (quantum unit wires) [35]. Trong luận án này chúng tôi dùng mô hình dây để minh họa các thuật toán lượng tử và gọi là sơ đồ dây hoặc mạng. Thuật toán lượng tử. Năm 1985 Deutsch đưa ra thuật toán đầu tiên, thuật toán Deutsch, xác định xem một hàm có là hằng hoặc cân bằng, về sau được tổng quát hoá thành thuật toán Deutsch – Jozsa vào năm 1992 [36]. Các thuật toán lượng tử khi được đưa ra đều phải hiệu quả hơn thuật toán cổ điển khi cùng giải quyết một 3 bài toán. Cho đến hiện nay, chúng ta đang có nhiều bài toán NP khó [87] và việc tìm ra một thuật toán giải quyết một bài toán như vậy thật sự có ý nghĩa. Tiếp sau thuật toán của Deutsch, vào các năm 1 4 và 1 , lần lượt xuất hiện hai thuật toán lượng tử gây tiếng vang lớn, đó là thuật toán phân tích số nguyên của Shor [ ] và thuật toán tìm kiếm của Grover [4 ]; trong đó, thuật toán Shor tăng tốc mũ còn thuật toán Grover tăng tốc bậc hai so với các thuật toán cổ điển tốt nhất được biết. Bài toán tìm kiếm. Một lớp lớn các bài toán trong khoa học máy tính có thể được quy về bài toán tìm kiếm: “Tìm phần tử x ∈ D ⊂ X thỏa điều kiện P ”. Trong lĩnh vực tính toán lượng tử, dĩ nhiên thuật toán nổi tiếng của Grover là tìm kiếm, nhưng ngay cả một thuật toán nổi tiếng khác, thuật toán phân tích số nguyên của Shor, cũng là tìm kiếm; một cách tổng quát, thuật toán Shor đi tìm các phần tử sinh của một nhóm con chưa biết. Bài toán tìm các phần tử sinh của một nhóm con chưa biết như vậy được gọi là bài toán tìm nhóm con ẩn (Hidden Subgroup Problem – HSP). Trong lúc bài toán HSP đã được giải với các nhóm giao hoán, thì vẫn còn đó các thách thức với các nhóm không giao hoán, có thể xem chi tiết ở [8], [9], [11], [48], [63], [66], [76], [92], [96], [113]. Ta cũng có bài toán đẳng cấu đồ thị, một bài toán thuộc lớp NP, cũng được quy về bài toán HSP [50], do đó cũng là bài toán tìm kiếm. Gần đây, vào năm 200 , Lomonaco đã chỉ ra rằng thuật toán của Grover và của Shor là rất gần nhau; cụ thể, thuật toán Grover thực chất nhằm giải một bài toán tìm nhóm con ẩn của một nhóm không giao hoán (Non Abelian Hidden Subgroup Problem – NHSP) [80]. Lý do chọn đề tài Tính cần thiết. Xây dựng thuật toán lượng tử là một thách thức nhưng cũng là cơ hội. Lĩnh vực này hứa hẹn thu hút các nhà khoa học máy tính, đặc biệt những ai có cơ sở toán học tốt, nhanh chóng tiếp cận và sớm có các đóng góp. Sự thành công của tiếp cận đại số trong xây dựng thuật toán lượng tử. Bằng cách dùng công cụ lý thuyết nhóm để giải thích và tổng quát hóa thuật toán phân tích số nguyên của Shor, đã hình thành khung thuật toán hiệu quả cho lớp bài toán HSP. 4 Liên quan đến bài toán NHSP chúng tôi quan sát thấy nhiều thuật toán thành công trong trường hợp làm việc với nhóm tích nửa trực tiếp, xem [41], [95], [96]. Tiếp cận đại số cũng cho ra các thủ tục phân rã một phép biến đổi unita thành các cổng lượng tử, cơ sở để xây dựng thuật toán lượng tử. Sự thành công của phép biến đổi Fourier lượng tử. Trong quá trình phát triển của thuật toán lượng tử, phép biến đổi Fourier luôn có vai trò quan trọng. Kể từ khi dùng công cụ lý thuyết nhóm nghiên cứu, phép biến đổi Fourier trở thành công cụ chính giải bài toán HSP, xem [8], [65], [66], [85], [91]. Liên quan đến nhóm là tích trực tiếp hoặc tích nửa trực tiếp, xuất hiện vai trò của phép biến đổi Clebsch – Gordan [75]. Phép biến đổi Clebsch – Gordan dần trở thành công cụ hiệu quả trong thiết kế thuật toán lượng tử giải bài toán NHSP, xem [8], [9], [75]. Gần đây xuất hiện phiên bản lượng tử của phép biến đổi wavelet, xem [44], [61], vốn được dùng rộng rãi trong lĩnh vực xử lý ảnh. Các phép biến đổi loại này có thể mang những nét tươi mới trong xây dựng thuật toán lượng tử [114]. Chưa có các nghiên cứu về hộp đen một cách có hệ thống. Hầu hết các thuật toán lượng tử đều sử dụng hộp đen. Trong thuật toán lượng tử, một hộp đen là biểu diễn của một hàm dưới dạng một phép biến đổi unita, lượng giá đồng thời các giá trị của hàm dưới dạng trạng thái tổ hợp tuyến tính của các trạng thái cơ sở, xem công thức (1.14), chương 1. Hộp đen thường dùng để biểu diễn dữ liệu bài toán nhưng vẫn chưa được nghiên cứu thỏa đáng, các thuật toán thường chấp nhận sự tồn tại của các hộp đen, trong lúc các thuật toán xây dựng lại thường làm việc với hàm tường minh dưới dạng công thức [5], [31]. Các nghiên cứu dùng thông tin heuristic vẫn đang bị bỏ ngỏ. Rất nhiều thuật toán sử dụng thuật toán Grover, dù nó chỉ tăng tốc bậc hai so với cổ điển, xem [18], [19], [46], [51]. Liệu thông tin heuristic có giúp tăng tốc Grover không ? Câu trả lời còn rất hạn chế. Năm 1 , Cerf đề nghị dùng Grover tìm ứng viên trong lời giải bộ phận, rồi tổ hợp lại [25]. Trước đó, từ năm 1 , Hogg đã tìm cách đưa heuristic vào các góc pha của phép biến đổi unita dạng đường chéo để giải bài toán tìm kiếm 5 tổ hợp [53]. Ngoài ra Brassard vào năm 2000 đề nghị một dạng hàm heuristic dùng cho Grover [19]. Mục đích, đối tượng, phạm vi nghiên cứu và ý nghĩa của đề tài luận án Mục đích. Xây dựng thuật toán giải bài toán tìm mẫu, được biểu diễn bằng hộp đen, dựa trên thuật toán Grover và phép biến đổi Hough, cho phép bổ sung thông tin heuristic. Đối tượng, phạm vi nghiên cứu. Đối tượng nghiên cứu của luận án vẫn là phép biến đổi unita, phần chính của một thuật toán lượng tử. Phạm vi nghiên cứu của luận án giới hạn trong hộp đen và phép biến đổi trực giao SO(2N). Ý nghĩa khoa học. Áp dụng thành công công cụ lý thuyết nhóm cho thấy có thể sử dụng được các kết quả của toán học hiện đại trong xây dựng thuật toán lượng tử. Ý nghĩa thực tiễn. Nhiều bài toán có khối lượng dữ liệu đồ sộ, đặc biệt trong lĩnh vực khai phá dữ liệu (data mining). Hộp đen biểu diễn dữ liệu bài toán có thể được xây dựng với số cổng lượng tử ít hơn rất nhiều. Những kết quả liên quan mật thiết đến đề tài luận án. Dùng heuristic. Các kết quả của Cerf [25], của Hogg [54], [55], [56], [57], [58], [59], [60], và của Brassard [19]. Cerf làm việc với bài toán có cấu trúc, dùng Grover tìm ứng viên trong lời giải bộ phận trong các không gian con, rồi xây dựng cách tổ hợp chúng lại; còn Hogg làm việc với bài toán có ràng buộc, bổ sung thông tin về các ràng buộc vào các phần tử pha, hình thành một bộ khung heuristic; trong khi đó, Brassard đề xuất một dạng hàm heuristic chuyển bài toán tìm kiếm sang không gian khác hiệu quả hơn. Ngoài ra, chúng tôi cho rằng việc tìm ra hàm f, là hằng trên các lớp kề, trong bài toán tìm nhóm con ẩn thật sự là một heuristic hiệu quả. Phiên bản lượng tử của một số phép biến đổi có ý nghĩa. Các phiên bản lượng tử cài đặt các phép biến đổi sin, cosin, Slan và Hartley có thể xem ở [2], [74]. Phiên bản lượng tử cài đặt phép biến đổi wavelet có thể xem ở [44], [61]. Phép biến đổi Fourier được cài đặt rất sớm từ năm 1 với độ phức tạp O(n2) [72] và vẫn tiếp tục 6 được dùng hiệu quả cho đến nay (mặc dù có một phiên bản xấp xỉ có độ phức tạp O(nlog(n/ε)) được giới thiệu vào năm 2000 [50], trong đó ε là độ chính xác được yêu cầu, nhưng theo quan sát của chúng tôi, chưa thấy được dùng trong các thuật toán lượng tử). Bài toán tìm mẫu dùng hộp đen biểu diễn dữ liệu bài toán. Có nhiều thuật toán lượng tử giải bài toán thực tế dùng trực tiếp các hộp đen gốc, biểu diễn dữ liệu gốc của bài toán. Cách xây dựng thuật toán phần lớn mang tính trực giác có được từ cách giải cổ điển [82], [83]. Phân rã phép biến đổi unita. Thuật toán lượng tử được xây dựng bởi các cổng lượng tử. Như vậy một phép biến đổi được sử dụng trong xây dựng thuật toán cần phải được phân tích thành dãy các cổng. Với một số phép biến đổi cụ thể, các ý tưởng cụ thể có thể được vận dụng thành công, xem [2], [44], [61], [74]. Một hướng đi khác, tìm các phương pháp tổng quát cho một phép biến đổi tùy ý. Gần đây, dùng định lý phân rã Cartan, tận dụng mối quan hệ giữa nhóm Lie và đại số Lie, một số thủ tục phân rã đã được giới thiệu, xem [21], [22], [23], [33], [38], [39], [69], [70], [86], [100], [102], [106]. Kết quả phân rã hiệu quả phép biến đổi Fourier và một số phép biến đổi có số chiều nhỏ, xem [106], [108], [109], [110]. Những tồn tại cần giải quyết. Heuristic. Thuật toán Grover giúp giải bài toán tìm kiếm tổng quát. Hạn chế chủ yếu của nó nằm ở khả năng tăng tốc chỉ ở mức bậc hai so với cổ điển. Như vậy một thuật toán cổ điển nếu được bổ sung thông tin heuristic sẽ vẫn hiệu quả hơn nhiều so với thuật toán Grover. Quan tâm đến thuật toán Grover, chúng tôi cho rằng để dùng hiệu quả thuật toán này nên xem xét đến khả năng sử dụng heuristic bổ sung, giúp thu hẹp không gian tìm kiếm. Hộp đen. Mặc dù các hộp đen thường xuyên xuất hiện trong các thuật toán lượng tử, nhưng chúng tôi vẫn chưa tìm thấy các kết quả nghiên cứu riêng về hộp đen. Các hộp đen là giao hoán với nhau nên có thể được chéo hóa đồng thời, do đó cùng nằm trong một xuyến tối đại nào đó của nhóm U(N). Chéo hóa đồng thời các hộp đen 7 cho phép khảo sát chúng một cách gián tiếp trên đại số Lie của xuyến tối đại chuẩn. Ngoài ra có thể thấy phần còn lại chưa được phân rã của các thủ tục phân rã theo kiểu Cartan cũng giao hoán với nhau. Như vậy hộp đen có thể là một giải pháp cho việc hoàn tất các thủ tục phân rã. Phép biến đổi Hough. Hiện chúng tôi chưa quan sát thấy có các phiên bản lượng tử cài đặt các phép biến đổi Hough. Ngoài ra dù đã có các cài đặt lượng tử, các phép như sin, cosin, Hartley, Slan, và wavelet vẫn chưa thấy có ứng dụng trong xây dựng thuật toán lượng tử. Phân rã phép biến đổi SO(2N). Các thủ tục phân rã cho đến nay đều làm việc với ma trận unita, có các số hạng là các số phức. Trong khi đó vẫn có nhiều phép biến đổi là trực giao với các số hạng là các số thực như sin, cos, wavelet (ngay cả phép biến đổi Fourier khi phân rã cũng xuất hiện các ma trận thành phần có các số hạng là các số thực). Trong đó, các phép biến đổi hoán vị, hoán vị các véc tơ cơ sở, cũng xuất hiện nhiều trong các thuật toán lượng tử. Những kết quả mới của luận án bao gồm: 1. Thuật toán lượng tử giải bài toán tìm mẫu với thông tin heuristic. Mẫu chịu tác động của nhóm H và thuật toán nhằm cài đặt hàm Boole f xác định trên H, xác định lời giải bài toán. Hàm f được sử dụng trong thuật toán Grover để giải bài toán. Thuật toán cho phép dùng một phần tử nhóm làm heuristic, thu hẹp không gian tìm kiếm trên một lớp kề của một nhóm con K cho trước. 2. Kỹ thuật phân tích hộp đen thành các cổng lượng tử. Hộp đen được biểu diễn qua các phần tử đại số Lie của xuyến tối đại chuẩn. Các phần tử này được xây dựng hiệu quả bởi dãy tác động phụ hợp của các cổng CNOT và Toffoli lên cơ sở của đại số Lie su(2). Dùng kỹ thuật này, các phép biến đổi so sánh, tịnh tiến và hoán vị dùng để xây dựng thuật toán tìm mẫu cũng được cài đặt hiệu quả. 3. Thủ tục phân rã Cartan chuẩn. Chọn một phân rã Cartan hạng cực đại từ xuyến tối đại chuẩn của nhóm tương ứng, thủ tục được xây dựng có sự kết 8 hợp của phân rã không gian nghiệm. Áp dụng phân rã đồng thời các phép biến đổi hoán vị, cung cấp một cách cài đặt khác các phép biến đổi của nhóm hoán vị, tùy thuộc ý đồ của người xây dựng thuật toán giải bài toán cụ thể. Cơ sở lý thuyết, lý luận, giả thiết khoa học và phương pháp nghiên cứu Cơ sở lý thuyết, lý luận. 1. Thuật toán lượng tử: thuật toán Grover và hộp đen; 2. Phép biến đổi Hough; 3. Tác động phụ hợp; 4. Lý thuyết nghiệm của nhóm Lie; 5. Nhóm tích nửa trực tiếp và nhóm tích bện (wreath product); 6. Hàm heuristic. Giả thiết khoa học. 1. Cài đặt phép biến đổi Hough dùng hộp đen, cho phép bổ sung heuristic; 2. Cài đặt hộp đen qua các cổng Deutsch-Toffoli; 3. Cài đặt phép biến đổi hoán vị dùng hộp đen và thủ tục phân rã. Phương pháp nghiên cứu. 1. Cài đặt phép biến đổi Hough. Tổng quát hóa phép biến đổi Hough dưới thuật ngữ tác động nhóm. Mô tả các hàm bầu chọn thông qua các phép toán nhóm. Biểu diễn tác động nhóm, phép toán nhóm, và hàm bầu chọn bằng hộp đen. Dùng các hộp đen này và các hộp đen biểu diễn dữ liệu bài toán xây dựng phiên bản lượng tử cho phép biến đổi Hough. 2. Cài đặt heuristic. Mô tả hàm heuristic qua phép toán nhóm. Vẫn dùng hộp đen biểu diễn nhóm con và phép toán hợp thành của nhóm, qua đó thiết kế thuật toán cho phép cài đặt heuristic. 3. Cài đặt hộp đen. Chéo hóa đồng thời các hộp đen, chuyển bài toán về khảo sát phần tử đại số tương ứng trên đại số Lie. Chọn cơ sở không gian véc tơ thích hợp và dùng tác động phụ hợp của các cổng CNOT và Toffoli cài đặt