Luận văn thạc sĩ về thuật toán tổng hợp mạch khả đảo đa ngõ ra trong kỹ thuật điện tử

Khám phá luận văn thạc sĩ về kỹ thuật điện tử, tập trung vào thuật toán tổng hợp mạch khả đảo đa ngõ ra hoàn chỉnh và ứng dụng thực tiễn.

• Tác giả: Nguyễn Đức Hương Quỳnh
• Người hướng dẫn: TS. Trần Hoàng Linh
• Trường học: Đại học Bách Khoa
• Chuyên ngành: Kỹ thuật Điện Tử
• Đề tài: Thuật Toán Tổng Hợp Mạch Khả Đảo Đa Ngõ Ra Hoàn Chỉnh
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2019
• Địa điểm: TP. Hồ Chí Minh

Mục lục chi tiết

• LỜI CẢM ƠN
• LỜI CAM ĐOAN
• DANH SÁCH HÌNH VẼ
• DANH SÁCH BẢNG BIỂU
• DANH SÁCH CÁC TỪ VIẾT TẮT
• 1. CHƯƠNG 1: MỞ ĐẦU
• 1.1. Lý do chọn đề tài
• 1.2. Mục tiêu và nhiệm vụ của luận văn
• 1.3. Đối tượng và phạm vi nghiên cứu
• 1.4. Ý nghĩa khoa học và thực tiễn
• 2. CHƯƠNG 2: TỔNG QUAN
• 2.1. Các khái niệm cơ bản
• 2.1.1. Hàm khả đảo và mạch khả đảo
• 2.1.2. Các cổng khả đảo cơ bản
• 2.1.3. Đường Ancilla và Garbage
• 2.1.4. Chi phí lượng tử
• 2.2. Các phương pháp tổng hợp mạch hiện tại
• 2.2.1. Phương pháp transformation-based
• 2.2.2. Phương pháp cycle-based
• 2.2.3. Phương pháp graphical [7]
• 2.2.4. Phương pháp tối ưu hóa mạch sửu dụng template matching
• 2.2.5. Phương pháp giảm chi phí trong mạch khả đảo Toffoli
• 2.3. Hàm affine tuyến tính
• 2.4. Các biểu thức Product-of-EXOR-sums (POE) và tập hỗ trợ
• 3. CHƯƠNG 3: TỔNG HỢP HÀM BOOLEAN HOÀN CHỈNH MỘT NGÕ RA
• 3.1. Thuật toán tổng hợp mạch dạng EPOE
• 3.1.1. Phương pháp template matching
• 3.1.2. Phương pháp tạo ra thư viện POE với N biến ngõ vào
• 3.1.3. Thuật toán EPOEM-1s
• 3.1.4. Thuật toán EPOEM-1f
• 3.2. Kết quả thực nghiệm
• 4. CHƯƠNG 4: TỔNG HỢP MẠCH EPOE CHO HÀM KHÔNG HOÀN CHỈNH MỘT NGÕ RA
• 4.1. Giới thiệu tổng quan
• 4.2. Thuật toán EPOEM-1-DC
• 4.3. Thuật toán EPOEM-1-DC-tree
• 4.4. Kết quả thực nghiệm
• 5. CHƯƠNG 5: TỔNG HỢP MẠCH EPOE CHO CÁC HÀM HOÀN CHỈNH ĐA NGÕ RA
• 5.1. Thuật toán EPOEM-MO-1
• 5.1.1. Kết quả thực nghiệm
• 5.2. Thuật toán EPOEM-MO-2
• 5.2.1. Tổng hợp dựa trên mạng lưới Exclusive-OR
• 5.2.2. Thuật toán EPOEM-MO-2
• 5.2.3. Kết quả thực nghiệm
• 6. CHƯƠNG 6: KẾT LUẬN
• 6.1. Hướng phát triển
• PHỤ LỤC: BẢNG CHÚ THÍCH CÁC MẤU THỬ
• Tài Liệu Tham Khảo

Tóm tắt

I. Giới thiệu về thuật toán tổng hợp mạch khả đảo

Thuật toán tổng hợp mạch khả đảo là một lĩnh vực nghiên cứu quan trọng trong kỹ thuật điện tử, đặc biệt là trong thiết kế mạch logic. Thuật toán tổng hợp giúp chuyển đổi các hàm boolean thành các mạch khả đảo, từ đó tối ưu hóa chi phí và hiệu suất. Mạch khả đảo có khả năng thực hiện các phép toán mà không mất thông tin, điều này rất quan trọng trong các ứng dụng tính toán lượng tử và thiết kế mạch logic. Việc nghiên cứu và phát triển các thuật toán tổng hợp mới là cần thiết để cải thiện hiệu suất và giảm chi phí của các mạch này. Đặc biệt, trong bối cảnh công nghệ hiện đại, nhu cầu về các mạch điện tử có khả năng tiêu thụ năng lượng thấp và hiệu quả cao ngày càng gia tăng. Các mạch khả đảo có thể được sử dụng trong nhiều lĩnh vực khác nhau, từ điện tử tiêu dùng đến các hệ thống tính toán phức tạp.

1.1. Mục tiêu nghiên cứu

Mục tiêu của nghiên cứu này là phát triển một thuật toán tổng hợp cho mạch khả đảo đa ngõ ra, nhằm tối ưu hóa chi phí lượng tử và thời gian tổng hợp. Nghiên cứu sẽ tập trung vào việc xây dựng các công cụ tổng hợp mạch dựa trên thuật toán mới, từ đó đánh giá hiệu suất của các phương pháp tổng hợp hiện tại. Việc tối ưu hóa này không chỉ giúp giảm thiểu chi phí mà còn cải thiện hiệu suất tổng thể của các mạch khả đảo. Hơn nữa, nghiên cứu sẽ cung cấp các phương pháp mới trong việc xử lý các hàm boolean phức tạp, góp phần nâng cao khả năng ứng dụng của thuật toán tổng hợp trong thực tế.

II. Các phương pháp tổng hợp mạch hiện tại

Hiện nay, có nhiều phương pháp tổng hợp mạch khả đảo khác nhau, bao gồm phương pháp transformation-based, cycle-based, và Binary Decision Diagram (BDD). Mỗi phương pháp đều có những ưu điểm và nhược điểm riêng. Phương pháp transformation-based thường được sử dụng để chuyển đổi các hàm boolean thành các dạng dễ xử lý hơn, trong khi phương pháp cycle-based tập trung vào việc tối ưu hóa các chu trình trong mạch. BDD là một công cụ mạnh mẽ giúp biểu diễn các hàm boolean một cách hiệu quả và dễ dàng hơn trong việc thực hiện các phép toán logic. Tuy nhiên, các phương pháp này vẫn còn tồn tại những hạn chế, đặc biệt là khi áp dụng cho các hàm boolean có số ngõ ra lớn. Nghiên cứu này sẽ đề xuất các cải tiến cho các phương pháp hiện tại, nhằm nâng cao khả năng tổng hợp mạch khả đảo đa ngõ ra.

2.1. Phương pháp transformation based

Phương pháp transformation-based là một trong những phương pháp phổ biến nhất trong tổng hợp mạch khả đảo. Phương pháp này dựa trên nguyên tắc biến đổi các hàm boolean thành các dạng dễ xử lý hơn, giúp đơn giản hóa quá trình tổng hợp mạch. Một trong những ưu điểm của phương pháp này là khả năng tối ưu hóa chi phí lượng tử, giúp giảm thiểu số lượng cổng cần thiết trong mạch. Tuy nhiên, phương pháp này cũng có những hạn chế nhất định, đặc biệt là khi áp dụng cho các hàm boolean phức tạp với nhiều ngõ ra. Nghiên cứu này sẽ phân tích sâu hơn về phương pháp transformation-based và đề xuất các cải tiến nhằm nâng cao hiệu suất tổng hợp mạch.

III. Kết quả thực nghiệm và phân tích

Trong nghiên cứu này, các thuật toán tổng hợp mạch khả đảo đã được thử nghiệm trên nhiều mẫu hàm boolean khác nhau. Kết quả cho thấy rằng thuật toán mới phát triển có khả năng tổng hợp mạch với chi phí lượng tử thấp hơn so với các phương pháp hiện tại. Đặc biệt, việc sử dụng cổng Toffoli âm trong quá trình tổng hợp đã giúp giảm thiểu số lượng cổng cần thiết, từ đó tối ưu hóa chi phí tổng thể của mạch. Các kết quả thực nghiệm cũng cho thấy rằng thời gian tổng hợp mạch đã được cải thiện đáng kể, cho phép thực hiện nhanh chóng và hiệu quả hơn. Những kết quả này không chỉ khẳng định tính khả thi của thuật toán tổng hợp mới mà còn mở ra hướng đi mới trong nghiên cứu và phát triển các mạch khả đảo.

3.1. Đánh giá hiệu suất

Đánh giá hiệu suất của thuật toán tổng hợp mạch khả đảo mới cho thấy sự cải thiện rõ rệt về chi phí và thời gian tổng hợp. Các thử nghiệm đã chỉ ra rằng thuật toán mới không chỉ giảm thiểu số lượng cổng cần thiết mà còn tối ưu hóa chi phí lượng tử, từ đó nâng cao hiệu suất tổng thể của mạch. Việc so sánh với các phương pháp hiện tại cho thấy rằng thuật toán mới có thể tổng hợp các hàm boolean phức tạp một cách hiệu quả hơn, đồng thời giữ được tính khả đảo của mạch. Những kết quả này chứng minh rằng việc áp dụng các cải tiến trong thuật toán tổng hợp có thể mang lại lợi ích lớn trong thực tế, đặc biệt trong các ứng dụng yêu cầu hiệu suất cao và chi phí thấp.

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

Nghiên cứu về thuật toán tổng hợp mạch khả đảo vẫn còn nhiều tiềm năng để phát triển. Các hướng nghiên cứu tương lai có thể bao gồm việc mở rộng các thuật toán hiện tại để xử lý các hàm boolean phức tạp hơn, hoặc phát triển các công cụ tổng hợp mạch tự động hóa hoàn toàn. Hơn nữa, việc tích hợp các công nghệ mới như trí tuệ nhân tạo và học máy vào quá trình tổng hợp mạch có thể mở ra những khả năng mới trong việc tối ưu hóa chi phí và hiệu suất. Những nghiên cứu này không chỉ góp phần nâng cao hiểu biết về mạch khả đảo mà còn tạo ra những ứng dụng thực tiễn trong lĩnh vực điện tử và tính toán lượng tử.

4.1. Tích hợp công nghệ mới

Tích hợp các công nghệ mới vào thuật toán tổng hợp mạch khả đảo có thể mang lại nhiều lợi ích. Việc sử dụng trí tuệ nhân tạo và học máy để tối ưu hóa quá trình tổng hợp có thể giúp cải thiện đáng kể hiệu suất và giảm thiểu chi phí. Những công nghệ này có khả năng phân tích và xử lý các hàm boolean phức tạp một cách nhanh chóng và hiệu quả, từ đó tạo ra các mạch khả đảo tối ưu hơn. Hướng nghiên cứu này không chỉ giúp nâng cao khả năng tổng hợp mà còn mở ra cơ hội mới cho các ứng dụng trong lĩnh vực điện tử và tính toán lượng tử.

Nội dung chính

Tổng quan nghiên cứu

Theo nguyên lý vật lý Landauer, quá trình xóa bỏ hoặc làm mất một bit thông tin trong các mạch logic truyền thống sẽ tiêu tán một lượng nhiệt năng tối thiểu bằng kT ln 2, tương đương khoảng 2.8 x 10^-21 Joules ở nhiệt độ phòng. Trong bối cảnh công nghệ vi mạch bán dẫn tiến dần đến các giới hạn vật lý lượng tử dưới 7nm, sự thất thoát năng lượng này trở thành rào cản lớn đối với hiệu năng tản nhiệt. Mạch logic khả đảo (Reversible Logic) với khả năng bảo toàn thông tin tuyệt đối thông qua các ánh xạ một-một giữa ngõ vào và ngõ ra đang nổi lên như giải pháp nền tảng cho tính toán lượng tử và thiết kế vi mạch công suất siêu thấp.

Tuy nhiên, thách thức lớn nhất hiện nay là sự bùng nổ chi phí lượng tử và số lượng cổng khi tổng hợp các hàm logic phức tạp. Nhiều thuật toán tổng hợp trước đây như phương pháp biến đổi bảng sự thật (Transformation-based) hay phương pháp chu trình (Cycle-based) thường tạo ra các mạch có chi phí lượng tử rất cao, dao động từ 800 đến hơn 4800 đơn vị đối với các mạch từ 6 đến 8 biến ngõ vào.

Luận văn thạc sĩ chuyên ngành Kỹ thuật Điện tử của tác giả Nguyễn Đức Hương Quỳnh, dưới sự hướng dẫn của Tiến sĩ Trần Hoàng Linh tại Trường Đại học Bách Khoa - Đại học Quốc gia Thành phố Hồ Chí Minh (hoàn thành từ tháng 02/2019 đến tháng 07/2019), tập trung giải quyết bài toán này. Mục tiêu trọng tâm của nghiên cứu là xây dựng thuật toán tổng hợp mạch khả đảo cho hàm boolean hoàn chỉnh đơn ngõ ra và đa ngõ ra dựa trên dạng chuẩn EXOR-sum of Products-of-EXOR-sums (EPOE), kết hợp cấu hình cổng lượng tử âm nhằm tối ưu hóa chi phí lượng tử. Kết quả nghiên cứu đạt được mức cắt giảm chi phí lượng tử từ 15% đến trên 93% trên các tập kiểm thử chuẩn quốc tế, tạo tiền đề vững chắc cho việc tự động hóa thiết kế mạch lượng tử hiện đại.

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 được xây dựng dựa trên nền tảng lý thuyết tính toán khả đảo, cấu trúc đại số Reed-Muller phân cực dương (PPRM) và biểu thức dạng tổng EXOR của các tích EXOR (EPOE). Trong mô hình này, bốn khái niệm kỹ thuật cốt lõi chi phối toàn bộ thuật toán tổng hợp:

Thứ nhất, hàm khả đảo n biến là ánh xạ song ánh một-một giữa không gian 2^n trạng thái ngõ vào và 2^n trạng thái ngõ ra. Để chuyển đổi các hàm bất khả đảo thành hàm khả đảo, hệ thống cần bổ sung các đường phụ ancilla với số lượng tối thiểu g = ceil(log2(M)), trong đó M là số lần lặp lại tối đa của một tổ hợp ngõ ra, cùng các đường rác garbage không tái sử dụng.

Thứ hai, chi phí lượng tử (Quantum Cost) được định nghĩa là số lượng các cổng lượng tử cơ bản 1-qubit và 2-qubit cần thiết để cấu thành nên một cổng phức hợp. Cổng NOT và CNOT dương có chi phí bằng 1; cổng CNOT âm có chi phí bằng 3; cổng Toffoli dương và Toffoli bán âm 3-bit có chi phí bằng 5; cổng Toffoli âm có chi phí bằng 7. Đối với cổng tổng quát N x N Toffoli, chi phí lượng tử được xác định theo công thức 2^N - 3 đối với cổng bán âm và 2^N - 1 đối với cổng âm.

Thứ ba, hàm affine tuyến tính và cấu trúc EPOE. Với n biến ngõ vào, tồn tại 2^(n+1) hàm affine tuyến tính khác nhau. Biểu thức EPOE cho phép phân rã các hàm logic phức tạp thành tích của các tổng EXOR, từ đó dễ dàng chuyển dịch sang cấu trúc phân tầng các cổng Toffoli có mức tiêu hao tài nguyên thấp.

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

Nghiên cứu sử dụng phương pháp thực nghiệm mô phỏng trên tập dữ liệu gồm 27 mẫu kiểm thử chuẩn quốc tế (benchmark) trong lĩnh vực thiết kế tự động hóa vi mạch (EDA), bao gồm các hàm từ 4 biến đến 8 biến ngõ vào như sym6, 8rd84f1, 5alu_9, 7rd73f3 và 4mod5_8. Phương pháp chọn mẫu bao phủ đa dạng các dạng hàm số học, hàm đối xứng và hàm điều khiển logic để bảo đảm tính khách quan.

Quy trình phân tích và tổng hợp được tiến hành qua ba giai đoạn:

Giai đoạn một, xây dựng cơ sở dữ liệu template matching và thư viện POE. Tác giả phát triển hai dạng thư viện: thư viện đơn thức (hỗ trợ tối đa 8 biến ngõ vào, mỗi template gán với một biểu thức POE có chi phí thấp nhất) và thư viện đa thức (hỗ trợ tối đa 6 biến ngõ vào, lưu trữ toàn bộ các biểu thức POE tương đương). Tiêu chí lựa chọn template Ti dựa trên điều kiện bao phủ tập ON-set với tỷ lệ vượt quá 2/3 tổng số minterm của template.

Giai đoạn hai, phát triển các giải thuật chuyên biệt: thuật toán EPOEM-1s (duyệt đơn thư viện) và EPOEM-1f (duyệt đa thư viện kết hợp nhân tử hóa đại số) cho hàm đơn ngõ ra hoàn chỉnh; thuật toán EPOEM-1-DC và EPOEM-1-DC-tree cho hàm không hoàn chỉnh có điều kiện tùy định; thuật toán EPOEM-MO-1 (chia sẻ biểu thức POE) và EPOEM-MO-2 (dựa trên cây EXOR) cho hàm đa ngõ ra hoàn chỉnh.

Giai đoạn ba, đo lường và đánh giá. Toàn bộ thuật toán được lập trình hiện thực hóa bằng ngôn ngữ Python trên máy tính Intel Core i7 1.8 GHz chạy hệ điều hành Windows 8 trong khung thời gian từ tháng 02/2019 đến tháng 06/2019. Lý do lựa chọn giải pháp này là khả năng thao tác linh hoạt trên các tập hợp minterm và ma trận logic quy mô lớn.

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

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

Quá trình thực nghiệm trên 27 mẫu thử benchmark chuẩn đã chứng minh tính ưu việt vượt trội của các thuật toán đề xuất, thể hiện rõ nét qua bốn phát hiện trọng tâm:

Thứ nhất, việc tích hợp cổng Toffoli âm và CNOT âm trực tiếp vào quá trình hiện thực hóa mạch giúp giảm mạnh chi phí lượng tử so với cách tổng hợp truyền thống chỉ dùng cổng dương. Tại mẫu kiểm thử 5alu_9, chi phí lượng tử giảm từ 39 xuống 27 đơn vị, tương ứng mức tiết kiệm 30.77%. Tại mẫu 7rd73f1, chi phí giảm từ 150 xuống 118 đơn vị, tương ứng giảm 21.33%.

Thứ hai, thuật toán thể hiện hiệu quả đột phá trên các hàm phức tạp có số biến lớn từ 6 đến 8 biến ngõ vào. Đối với mẫu chuẩn sym6 (6 biến), thuật toán đề xuất đạt mức chi phí 120 đơn vị, vượt trội hoàn toàn so với mức 857 đơn vị của các nghiên cứu trước đây, tương đương tỷ lệ cắt giảm lên tới 86.00%. Đặc biệt, tại mẫu 8rd84f4 (8 biến), chi phí lượng tử giảm từ 4824 đơn vị ở các công bố trước xuống còn 330 đơn vị, đạt mức giảm kỷ lục 93.16%.

Thứ ba, kỹ thuật chia sẻ biểu thức POE trong thuật toán EPOEM-MO-1 và cấu trúc mạng lưới Exclusive-OR trong EPOEM-MO-2 giúp loại bỏ triệt để các cổng logic dư thừa giữa các nhánh ngõ ra, tiết kiệm từ 20% đến 45% số đường dây ancilla cần thiết.

Thứ tư, thuật toán EPOEM-1-DC-tree giải quyết xuất sắc bài toán tối ưu trên các hàm không hoàn chỉnh, giúp cấu trúc mạch rút gọn thêm từ 15% đến 25% chi phí lượng tử so với phương pháp duyệt tham lam từng bước.

Thảo luận kết quả

Nguyên nhân cốt lõi giúp thuật toán đạt được các chỉ số ấn tượng nằm ở cơ chế kết hợp giữa biểu diễn đại số EPOE và cổng điều khiển âm. Trong các mạch lượng tử thông thường, để hiện thực hóa một điều khiển âm cần chèn 2 cổng NOT ở hai đầu đường dây, làm tăng thêm 2 đơn vị chi phí trên mỗi cổng Toffoli. Việc ánh xạ trực tiếp sang cổng Toffoli âm và bán âm đã triệt tiêu hoàn toàn các cổng NOT phụ trợ này.

So sánh với phương pháp Transformation-based vốn quét từng hàng của bảng sự thật và sinh ra chuỗi cascade cổng multicontrol rất dài, phương pháp EPOE phân tầng theo minterm duy trì tính hội tụ nhanh và kiểm soát chặt chẽ quy mô mạch. Đồng thời, so với phương pháp Graphical dựa trên S-maps thường rơi vào trạng thái bế tắc chọn ngẫu nhiên khi số biến vượt quá 3, thuật toán đề xuất duy trì tính ổn định tuyệt đối trên các hàm 8 biến.

Các kết quả thực nghiệm này được thể hiện trực quan qua bảng tổng hợp chi phí lượng tử đa chiều và đồ thị so sánh hiệu năng cascade. Đường cong suy giảm chi phí lượng tử minh họa rõ sự khác biệt giữa cấu hình thuần cổng dương và cấu hình kết hợp cổng âm, khẳng định tính khả thi cao của phương pháp khi triển khai trên phần cứng thực tế.

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

Để thúc đẩy việc ứng dụng các thuật toán tổng hợp mạch khả đảo vào thực tiễn thiết kế vi mạch và tính toán lượng tử, bốn khuyến nghị chiến lược được đề xuất:

Một là, mở rộng và nén cấu trúc lưu trữ thư viện template POE bằng cấu trúc dữ liệu đồ thị quyết định nhị phân BDD hoặc ZDD. Mục tiêu cụ thể là nâng giới hạn xử lý của thư viện đa thức từ 6 biến lên 10 đến 12 biến ngõ vào, đồng thời giảm khoảng 40% dung lượng bộ nhớ RAM tiêu thụ trong thời gian 6 tháng tới. Trách nhiệm thực hiện thuộc về nhóm nghiên cứu thiết kế tự động hóa vi mạch tại các trường đại học.

Hai là, phát triển mô-đun tối ưu hóa hậu tổng hợp (Post-synthesis Optimization) ứng dụng kỹ thuật khớp mẫu mở rộng cho các khối 5-qubit và 6-qubit. Mục tiêu là cắt giảm thêm từ 10% đến 15% chi phí lượng tử dư thừa sau khi hoàn tất bước tổng hợp EPOE ban đầu trong lộ trình 3 tháng, do các kỹ sư thuật toán lượng tử phụ trách.

Ba là, đóng gói giải thuật thành bộ thư viện mã nguồn mở hoàn chỉnh trên Python, tích hợp cổng xuất mã định dạng chuẩn QASM (Quantum Assembly Language). Mục tiêu là đạt khả năng tương thích 100% với các nền tảng điện toán đám mây lượng tử hàng đầu như IBM Qiskit và Google Cirq trong vòng 9 tháng, do các lập trình viên công nghệ lượng tử phối hợp triển khai.

Bốn là, ứng dụng thuật toán tổng hợp đa ngõ ra vào quy trình thiết kế khối số học ALU công suất siêu thấp cho vi mạch bán dẫn nano. Mục tiêu là giảm từ 25% đến 30% mức tiêu tán công suất động trên chip IoT trong giai đoạn 12 tháng, do các trung tâm R&D vi điện tử và doanh nghiệp bán dẫn chủ trì.

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

Nội dung luận văn mang lại giá trị học thuật và thực tiễn sâu sắc cho bốn nhóm đối tượng chuyên môn:

Thứ nhất, kỹ sư thiết kế mạch lượng tử và thuật toán lượng tử. Công trình cung cấp phương pháp luận chi tiết để thiết kế các khối mạch số học lượng tử, bộ giải mã và biến đổi bit với chi phí lượng tử tối ưu, sẵn sàng thực thi trên các bộ xử lý lượng tử siêu dẫn hoặc ion bẫy.

Thứ hai, học viên cao học, nghiên cứu sinh và nhà khoa học ngành Kỹ thuật Điện tử, Vi điện tử và Khoa học Máy tính. Luận văn đóng vai trò tài liệu tham khảo chuẩn mực về logic khả đảo, quy trình xây dựng thư viện template, kỹ thuật phân rã đại số boolean và phương pháp kiểm thử benchmark theo chuẩn quốc tế.

Thứ ba, giảng viên đại học chuyên ngành Kỹ thuật Điện - Điện tử và Công nghệ Thông tin. Tài liệu là nguồn học liệu giá trị để bổ sung vào giáo trình các môn học nâng cao như Thiết kế luận lý nâng cao, Tự động hóa thiết kế vi mạch (VLSI CAD) và Kiến trúc máy tính lượng tử.

Thứ tư, chuyên gia R&D tại các tập đoàn công nghệ vi mạch và hệ thống nhúng như Bosch, Synopsys hay Cadence. Doanh nghiệp có thể khai thác thuật toán chia sẻ biểu thức POE để tối ưu hóa diện tích silicon, tiết kiệm tài nguyên kết nối và hạ thấp công suất tỏa nhiệt cho các dòng vi xử lý chuyên dụng thế hệ mới.

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

Mạch logic khả đảo mang lại ưu thế gì vượt trội so với mạch logic truyền thống? Mạch logic khả đảo bảo toàn thông tin toàn vẹn nhờ ánh xạ song ánh một-một giữa ngõ vào và ngõ ra, triệt tiêu sự tiêu tán nhiệt năng theo giới hạn Landauer (khoảng 2.8 x 10^-21 Joules trên mỗi bit bị xóa). Trong thực tế, đây là yêu cầu vật lý bắt buộc để xây dựng các cổng logic lượng tử không suy hao và các hệ thống vi mạch CMOS công suất siêu thấp.

Chi phí lượng tử (Quantum Cost) được định nghĩa và lượng hóa như thế nào? Chi phí lượng tử là thước đo tiêu chuẩn thể hiện số lượng cổng lượng tử cơ bản 1-qubit và 2-qubit cần thiết để cấu tạo nên mạch logic. Ví dụ cụ thể: cổng NOT và CNOT có chi phí bằng 1; cổng Toffoli dương hoặc bán âm có chi phí bằng 5; trong khi cổng Toffoli âm có chi phí bằng 7 và cổng tổng quát N x N Toffoli có chi phí lên tới 2^N - 1.

Tại sao việc tích hợp cổng Toffoli âm lại giúp cắt giảm chi phí lượng tử của toàn mạch? Cổng Toffoli âm cho phép đặt điều khiển đảo trực tiếp trên các đường tín hiệu mà không cần chèn thêm 2 cổng NOT phụ trợ ở hai đầu như cách hiện thực thuần cổng dương. Nhờ đó, số lượng cổng trung gian giảm rõ rệt, điển hình tại hàm kiểm thử 5alu_9 giúp chi phí giảm từ 39 xuống 27 đơn vị.

Thuật toán EPOEM-1f có điểm gì khác biệt cốt lõi so với thuật toán EPOEM-1s? Thuật toán EPOEM-1s sử dụng thư viện đơn thức để chọn nhanh biểu thức POE tối ưu cục bộ theo cơ chế tham lam từng bước. Ngược lại, thuật toán EPOEM-1f khai thác thư viện đa thức để quét qua tất cả các biểu thức POE tương đương, sau đó áp dụng phép nhân tử hóa đại số để tìm ra cấu hình có chi phí lượng tử toàn cục thấp nhất (ví dụ giảm từ 28 xuống 24 đơn vị).

Luận văn giải quyết bài toán tổng hợp hàm đa ngõ ra hoàn chỉnh bằng cách nào? Luận văn phát triển hai giải thuật chuyên sâu: EPOEM-MO-1 phân rã hệ thống thành các hàm đơn ngõ ra và chia sẻ các biểu thức POE chung giữa các nhánh; EPOEM-MO-2 sử dụng mạng lưới cây EXOR tối ưu. Giải pháp này giúp loại bỏ hoàn toàn các khối logic trùng lặp, tiết kiệm từ 20% đến 45% tài nguyên đường ancilla và số lượng cổng mạch.

Kết luận

Công trình nghiên cứu luận văn thạc sĩ của tác giả Nguyễn Đức Hương Quỳnh đã giải quyết trọn vẹn bài toán tổng hợp mạch logic khả đảo đa ngõ ra hoàn chỉnh với những đóng góp quan trọng:

• Đóng góp lý thuyết: Hoàn thiện mô hình toán học tổng hợp mạch khả đảo dựa trên cấu trúc EPOE kết hợp linh hoạt hệ thống cổng lượng tử âm, bán âm và CNOT âm.
• Đóng góp thuật toán: Đề xuất thành công hệ thống giải thuật toàn diện gồm EPOEM-1s, EPOEM-1f, EPOEM-1-DC, EPOEM-1-DC-tree và EPOEM-MO (1 và 2) xử lý linh hoạt từ hàm đơn đến đa ngõ ra.
• Đóng góp thực nghiệm: Đạt hiệu quả cắt giảm chi phí lượng tử vượt trội, giảm tới 86.00% trên mẫu sym6 và 93.16% trên mẫu 8rd84f4 so với các nghiên cứu công bố trước đây.
• Đóng góp công cụ: Hiện thực hóa bộ phần mềm tổng hợp tự động hoàn chỉnh trên nền tảng Python, kiểm chứng thành công trên 27 bộ dữ liệu benchmark quốc tế.
• Kế hoạch phát triển: Định hướng mở rộng thuật toán với cấu trúc BDD để xử lý hàm trên 10 biến ngõ vào và xuất mã QASM cho máy tính lượng tử trong thời gian 6 đến 12 tháng tới.

Quý độc giả, chuyên gia vi mạch và các nhà nghiên cứu quan tâm có thể tiếp cận toàn văn luận văn thạc sĩ để khai thác chi tiết các chứng minh đại số, mã nguồn thuật toán và bảng thông số mạch khả đảo chuyên sâu.

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

Mở đầu HVTH: Nguyễn Đức Hương Quỳnh Luận văn thạc sĩ 4 GVHD: TS. Trần Hoàng Linh CHƯƠNG 2: TỔNG QUAN 2. Các khái niệm cơ bản 2. Hàm khả đảo và mạch khả đảo Hàm boolean hoàn chỉnh là một hàm boolean mà ở tất cả các giá trị của ngõ vào đều có giá trị của ngõ ra tương ứng.

Trong luận văn này, hàm boolean hoàn chỉnh là đối tượng chính trong việc tổng hợp mạch và được chia làm hai loại dựa theo số ngõ ra. Hai loại đó là hàm boolean hoàn chỉnh một ngõ ra, sẽ được gọi tắt là là hàm một ngõ ra, và hàm boolean hoàn chỉnh đa ngõ ra, sẽ được gọi tắt là hàm đa ngõ ra. Một ví dụ về hàm boolean hoàn chỉnh được thể hiện trong Bảng 2-1. Bảng 2-1 a) Hàm hoàn chỉnh một ngõ ra; b) hàm hoàn chỉnh đa ngõ ra a) b) Ngõ vào Ngõ ra Ngõ vào Ngõ ra a b c F a b c f1 f0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 1 0 1 0 1 0 1 0 1 0 0 1 0 1 1 0 0 1 1 1 0 1 0 0 1 1 0 0 0 0 1 0 1 1 1 0 1 1 1 1 1 0 1 1 1 0 1 0 1 1 1 0 1 1 1 0 0 Với các hàm có số biến ngõ vào nhỏ thì có thể thể hiện bằng bảng sự thật cũng như bìa Kanaugh.

Tuy nhiên với các hàm có số biến ngõ vào lớn thì việc thể hiện như thế rất bất tiện và gây khó khăn cho người đọc. Vì vậy, để dễ dàng theo dõi, các hàm trong luận văn này sẽ được quy ước cách viết như sau:  Đối với hàm f trong ví dụ ở Bảng 2-1a, f(a, b, c) = m(2, 4, 5, 6)  Đối với hàm Y1 và Y0 trong ví dụ ở Bảng 2-1b, f1(a, b, c) = m(0, 3, 5, 6) và f2(a, b, c) = m(0, 1, 2, 5). Chương 2 HVTH: Nguyễn Đức Hương Quỳnh Luận văn thạc sĩ 5 GVHD: TS. Trần Hoàng Linh Hàm boolean không hoàn chỉnh là một hàm boolean có các giá trị tùy định ở ngõ ra.

Và hàm boolean không hoàn chỉnh này cũng được chia ra thành hai loại dưa theo số ngõ ra. Tuy nhiên, đây không phải là đối tượng chính trong luận văn này nên sẽ không được đề cập nhiều. Hàm khả đảo là một hàm boolean có số ngõ ra bằng với số ngõ vào và ánh xạ giữa ngõ ra và ngõ vào là 1-1. Hàm khả đảo n biến là một hàm khả đảo có n ngõ vào và n ngõ ra.

Bảng 2-2 là một ví dụ về hàm khả đảo 3 biến: Bảng 2-2 Bảng sự thật của hàm khả đảo 3 biến Ngõ vào Ngõ ra a b c f2 f1 f0 0 0 0 1 0 0 0 0 1 1 0 1 0 1 0 1 1 0 0 1 1 0 0 1 1 0 0 0 0 0 1 0 1 1 1 1 1 1 0 0 1 0 1 1 1 0 1 1 Và biểu diễn ở dạng công thức theo quy ước của các hàm f2, f1 và f0 lần lượt là:  f2(a, b, c) = m(0, 1, 2, 5)  f1(a, b, c) = m(2, 5, 6, 7)  f0(a, b, c) = m(1, 3, 5, 7) Mạch khả đảo là mạch hiện thực hóa của hàm khả đảo. Trong logic khả đảo cổ điển, mỗi cặp ngõ vào/ngõ ra thường được gọi là một đường hoặc một dây, trong khi ở logic lượng tử, nó được gọi là một qubit. Một ví dụ về mạch khả đảo được thể hiện trong Hình 2-1. 𝑥2 𝑥2 𝑥2 𝑥2 𝑥1 𝑥1 𝑥1 𝑥1 𝑥0 𝑥0 ⨁𝑥1 𝑥0 𝑥0 ⨁𝑥1 ⨁𝑥1 𝑥2 Hình 2-1 Mạch khả đảo với cổng NOT, CNOT và Toffoli Chương 2 HVTH: Nguyễn Đức Hương Quỳnh Luận văn thạc sĩ 6 GVHD: TS.

Trần Hoàng Linh 2. Các cổng khả đảo cơ bản Một số cổng khả đảo cơ bản thường được sử dụng như: 𝑥 𝑥̅  NOT: (𝑥) → (𝑥̅ ) Hình 2-2 Cổng NOT  CNOT: (𝑥; 𝑦) → (𝑥; 𝑦 ⊕ 𝑥) 𝑥1 𝑥1 𝑥1 𝑥1 𝑥0 𝑥0 ⨁𝑥1 𝑥0 𝑥0 ⨁𝑥1 a b Hình 2-3 a) cổng CNOT, b) cổng CNOT âm  Toffoli: (𝑥, 𝑦; 𝑧) → (𝑥, 𝑦; 𝑧 ⊕ 𝑥𝑦) 𝑥2 𝑥2 𝑥2 𝑥2 𝑥2 𝑥2 𝑥1 𝑥1 𝑥1 𝑥1 𝑥1 𝑥1 𝑥0 𝑥0 ⨁𝑥1 𝑥2 𝑥0 𝑥0 ⨁𝑥1 𝑥2 𝑥0 𝑥0 ⨁𝑥1 𝑥2 a b c Hình 2-4 a) cổng Toffoli, b) cổng Toffoli bán âm, c) cổng Toffoli âm  Multicontrol Toffoli: 𝑥𝑛 𝑥𝑛 𝑥𝑛−1 𝑥𝑛−1 … … … … 𝑥 … …𝑥 1 1 𝑥0 𝑥0 ⨁𝑥1 … 𝑥𝑛−1 𝑥𝑛 Hình 2-5 Cổng multicontrol Toffoli Chương 2 HVTH: Nguyễn Đức Hương Quỳnh Luận văn thạc sĩ 7 GVHD: TS. Trần Hoàng Linh 2. Đường Ancilla và Garbage Có 2𝑛 ! hàm khả đảo phân biệt n biến với các hoán vị của 2𝑛 phần tử.

Tuy 𝑖 𝑛 nhiên, cũng tồn tại ∑𝑛𝑖=1(2𝑖 )2 ≃ 2𝑛2 hàm không khả đảo từ 1 đến n ngõ ra. Để chuyển đổi các hàm đó thành hàm khả đảo cần phải thêm các ngõ vào/ ngõ ra. Các đường thêm vào ở ngõ vào được gọi là đường ancilla và thường là hằng số 0 hoặc 1. Các đường ancilla mà giá trị của nó không bị đặt lại thành một hằng số ở cuối quá trình tính toán được gọi là các đường garbage.

Ngõ ra của các đường ancilla không bị ràng buộc trong bảng sự thật được gọi là tùy định (DC). Với một hàm bất khả đảo có số tổ hợp của mỗi ngõ ra có thể được lặp lại đến M lần, thì cần 𝑔 = ⌈𝑙𝑜𝑔2 𝑀⌉ đường ancilla để xây dựng được mạch khả đảo [3]. Chi phí lượng tử Chi phí lượng tử là một thông số đo lường quan trọng trong việc so sánh các mạch khả đảo. Chi phí lượng tử của một cổng được định nghĩa như là số lượng các lượng tử cơ bản cần thiết để tạo nên cổng đó [1].

Chi phí lượng tử của một cổng n-bit Toffoli âm với ít nhất một đường điều khiển dương bằng với chi phí của một cổng n- bit Toffoli. Nếu tất cả các đường điều khiển điều là âm thì chi phí lượng tử sẽ phải cộng thêm 2 [1]. Chi phí lượng tử của một mạch được định nghĩa là tổng chi phí của tất cả các cổng trong mạch. Trong đó, chi phí các cổng cơ bản được định nghĩa trong bảng 2-3.

Bảng 2-3 Chi phí lượng tử của các cổng cơ bản Tên cổng Chi phí NOT 1 CNOT 1 CNOT âm 3 Toffoli 5 Toffoli bán âm 5 Toffoli âm 7 𝑁 𝑁𝑥𝑁 Toffoli (bán âm) 2 −3 𝑁𝑥𝑁 Toffoli âm 2𝑁 − 1 Chương 2 HVTH: Nguyễn Đức Hương Quỳnh Luận văn thạc sĩ 8 GVHD: TS. Trần Hoàng Linh 2. Các phương pháp tổng hợp mạch hiện tại 2. Phương pháp transformation-based Phương pháp transformation-based lần đầu được đưa ra bởi Miller et al [4] dựa trên sự tương quan giữa ngõ vào và ngõ ra trong bảng sự thật.

Các thuật toán dựa trên phương pháp này sẽ quét qua tất cả các hàng trong bảng sự thật, tìm kiếm sự khác biệt giữa các ngõ vào và ngõ ra, và sửa chữa các điểm khác biệt đó bằng cách áp dụng các cổng multicontrol Toffoli nhưng chỉ với các điều khiển dương [5]. Một ví dụ về phương pháp này được miêu tả ở bảng 2-4: Bảng 2-4 Ví dụ về phương pháp transformation-based Ngõ vào Ngõ ra 1 2 3 4 5 6 7 8 9 stt abc xyz xyz xyz xyz xyz xyz xyz xyz xyz xyz 0 000 011 010 000 000 000 000 000 000 000 000 1 001 000 000 010 011 001 001 001 001 001 001 2 010 101 101 111 110 110 010 010 010 010 010 3 011 010 011 001 001 011 111 011 011 011 011 4 100 001 001 011 010 010 110 110 100 100 100 5 101 111 110 100 100 100 100 100 110 111 101 6 110 110 111 101 101 111 011 111 101 101 111 7 111 100 100 110 111 101 101 101 111 110 110 1) Ở hàng 0, ngõ vào và ngõ ra khác nhau 2 bit, nên sử dụng 1 cổng CNOT (y;z) để thay đổi bit thấp nhất từ 1 thành 0. Các giá trị in đậm là các giá trị ngõ ra sẽ bị thay đổi theo. Kết quả sau khi qua cổng CNOT được thể hiện ở cột 1.

2) Lúc này hàng 0 chỉ còn lại bit thứ y là 1 nên sử dụng 1 cổng NOT (y) để chuyển bit này về 0. Kết quả được thể hiện ở cột 2. 3) Ngõ ra ở hàng 0 đã giống với ngõ vào, nên ở bước này cần chọn cổng mà không làm ảnh hưởng đến hàng 0. Ở hàng 1, cần chuyển đổi bit z thành 1 trước nên cổng CNOT (y;z) được chọn.

Kết quả được thể hiện ở cột 3. 4) Lúc này cần chuyển bit y ở hàng 1 về 0, cổng CNOT (z;y) được chọn. 5) Tiếp tục lặp lại như các bước trên cho đến cột 5, bit x ở hàng 3 cần phải chuyển về 0, vì để không ảnh hưởng đến các hàng trên nên cổng Toffoli (y,z;x) được chọn. 6) Như vậy, cứ lặp lại từng hàng cho đến khi ngõ ra giống với ngõ vào.

Lúc này chỉ cần viết lại các cổng từ cột 1 đến cột 9 theo chiều từ phải sang trái. Lý do phải viết ngược lại là vì thuật toán này đang biến đổi ngõ ra sao cho giống với ngõ vào, nên để từ ngõ vào thành ngõ ra, mạch phải được đảo lại. Chương 2 HVTH: Nguyễn Đức Hương Quỳnh Luận văn thạc sĩ 9 GVHD: TS. Trần Hoàng Linh Thuật toán này được cải tiến bởi Maslov, tác giả tổng hợp mạch một cách trực tiếp bởi sự phức tạp của phổ Reed-Muller thay vì sử dụng khoảng cách Hamming.

Cổng Toffoli với cả hai điều khiển âm và dương đều được áp dụng. Sau khi tổng hợp mạch thì có thể tối ưu bởi các template của cổng Toffoli [3]. Phương pháp cycle-based Một số khái niệm cơ bản trong phương pháp cycle-based: Cycle là một tâp hoán vị (𝑎1 , 𝑎2 , … , 𝑎𝑘 ) mà trong đó 𝑓 (𝑎1 ) = 𝑎2 , 𝑓 (𝑎2 ) = 𝑎3 , … , 𝑓 (𝑎𝑘 ) = 𝑎1. Chiều dài của một cycle được tính bằng số phần tử trong tập hoán vị của cycle đó.

Một cycle có chiều dài k được gọi là k-cycle. Với cycle có chiều dài bằng 2 được gọi là một transposition. Hai cycle được gọi là phân biệt (disjoint) nếu chúng không có chung bất kì một phần tử nào. Và hai cycle phân biệt có thể hoán đổi vị trí cho nhau.

Tính chất hoán đổi này sẽ không còn đúng nếu hai cycle có ít nhất một phần tử chung [3]. Ngoài ra, một cycle có thể được viết theo nhiều cách khác nhau bằng cách thay đổi vị trí các phần tử trong cycle một cách tuần tự.