Luận Văn Thạc Sĩ Kỹ Thuật Điện Tử Về Thuật Toán Tổng Hợp Mạch Khả Đảo Đa Ngõ Ra

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

• Tác giả: Nguyễn Hải Đăng
• 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 Không 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
• 2.1.2. Cổng khả đảo
• 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ử dụng template matching
• 2.2.5. Phương pháp giảm chi phí trong mạch khả đảo Toffoli
• 3. CHƯƠNG 3: CHUYỂN ĐỔI HÀM KHẢ ĐẢO KHÔNG HOÀN CHỈNH
• 3.1. Trường hợp số ngõ vào bằng số ngõ ra
• 3.1.1. Phương pháp chuyển đổi
• 3.2. Trường hợp số ngõ vào nhỏ hơn số ngõ ra
• 3.2.1. Phương pháp chuyển đổi
• 3.3. Trường hợp số ngõ vào lớn hơn số ngõ ra
• 3.3.1. Phương pháp chuyển đổi
• 4. CHƯƠNG 4: THUẬT TOÁN TỔNG HỢP MẠCH KHẢ ĐẢO
• 4.1. Phân tách k-cycles
• 4.2. Tương quan giữa 2-cycles có hamming bằng 1 với cổng Toffoli
• 4.3. Tối ưu hóa mạch bằng template
• 4.4. Thuật toán tổng hợp mạch cycle-swap
• 4.5. Kết quả thí nghiệm
• 5. CHƯƠNG 5: KẾT LUẬN
• 5.1. Hướng phát triển
• Tài Liệu Tham Khảo
• PHỤ LỤC: BẢNG CHÚ THÍCH CÁC MẤU THỬ

Tóm tắt

I. Giới thiệu chung về luận văn

Luận văn thạc sĩ Kỹ thuật điện tử này tập trung vào việc phát triển thuật toán tổng hợp mạch khả đảo đa ngõ ra không hoàn chỉnh. Mục tiêu chính là tối ưu hóa quá trình tổng hợp mạch, nhằm đáp ứng nhu cầu ngày càng cao trong lĩnh vực công nghệ điện tử và tính toán lượng tử. Các nghiên cứu trước đây cho thấy rằng logic khả đảo có nhiều ứng dụng quan trọng, đặc biệt là trong thiết kế mạch công suất thấp và hệ thống điện tử phức tạp. Do đó, việc phát triển một thuật toán mới nhằm cải thiện hiệu suất tổng hợp mạch là rất cần thiết. Các phương pháp tổng hợp hiện tại thường gặp khó khăn trong việc xử lý các hàm không hoàn chỉnh, điều này dẫn đến việc cần thiết phải nghiên cứu và phát triển một phương pháp mới có khả năng tối ưu hóa chi phí và thời gian tổng hợp.

1.1 Tầm quan trọng của nghiên cứu

Nghiên cứu về thuật toán tổng hợp mạch không chỉ giúp nâng cao hiệu suất tổng hợp mà còn mở ra nhiều cơ hội ứng dụng trong các lĩnh vực như tính toán lượng tử, công nghệ nano và hệ thống viễn thông. Qua đó, luận văn này không chỉ mang lại giá trị lý thuyết mà còn có ý nghĩa thực tiễn sâu sắc trong việc phát triển các sản phẩm công nghệ mới. Việc tối ưu hóa chi phí lượng tử và độ sâu mạch sẽ giúp các nhà thiết kế có thể xây dựng các mạch khả đảo hiệu quả hơn, từ đó thúc đẩy sự phát triển của ngành kỹ thuật điện tử.

II. Tổng quan về các phương pháp tổng hợp

Luận văn trình bày các phương pháp tổng hợp mạch hiện tại, bao gồm các phương pháp như transformation-based, cycle-based và graphical. Mỗi phương pháp đều có những ưu điểm và nhược điểm riêng, do đó việc lựa chọn phương pháp phù hợp là rất quan trọng. Phương pháp transformation-based được áp dụng để sửa chữa các điểm khác biệt giữa ngõ vào và ngõ ra trong bảng sự thật, trong khi phương pháp cycle-based tập trung vào việc tối ưu hóa các chu kỳ trong mạch. Các nghiên cứu trước đây đã chỉ ra rằng việc kết hợp giữa các phương pháp này có thể mang lại kết quả tốt hơn trong việc tổng hợp mạch khả đảo.

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. Nó hoạt động bằng cách quét qua bảng sự thật và tìm kiếm sự khác biệt giữa ngõ vào và ngõ ra, từ đó áp dụng các cổng như multicontrol Toffoli để sửa chữa các điểm khác biệt. Điều này giúp tạo ra một mạch khả đảo chính xác hơn, đáp ứng yêu cầu của hàm logic. Tuy nhiên, phương pháp này cũng gặp phải một số hạn chế khi xử lý các hàm không hoàn chỉnh, điều này đã dẫn đến việc nghiên cứu các phương pháp mới hơn.

III. Phương pháp chuyển đổi hàm khả đảo

Luận văn đề xuất một phương pháp chuyển đổi hàm khả đảo đa ngõ ra không hoàn chỉnh sang hàm hoàn chỉnh, nhằm làm ngõ vào cho thuật toán tổng hợp. Phương pháp này không chỉ giúp cải thiện tính chính xác của mạch tổng hợp mà còn giảm thiểu chi phí lượng tử. Việc chuyển đổi này rất quan trọng vì các thuật toán tổng hợp hiện tại thường yêu cầu ngõ vào phải là hàm khả đảo hoàn chỉnh. Phương pháp chuyển đổi này bao gồm các bước như thêm đường ancilla và garbage, từ đó đảm bảo rằng tất cả các ngõ ra đều có giá trị xác định.

3.1 Các bước chuyển đổi

Quá trình chuyển đổi bao gồm việc xác định số ngõ vào và ngõ ra, sau đó thêm các đường ancilla cần thiết. Các ngõ ra không xác định sẽ được đánh dấu là garbage. Việc này giúp đảm bảo rằng hàm khả đảo hoàn chỉnh được tạo ra từ hàm không hoàn chỉnh, từ đó tạo điều kiện thuận lợi cho các thuật toán tổng hợp tiếp theo. Nghiên cứu cho thấy rằng việc áp dụng phương pháp này có thể làm giảm đáng kể chi phí lượng tử và tăng tốc độ tổng hợp, từ đó mở ra nhiều khả năng ứng dụng trong thực tế.

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

Luận văn trình bày các kết quả thí nghiệm cho thấy hiệu quả của thuật toán tổng hợp mới được đề xuất. Kết quả cho thấy rằng thuật toán này không chỉ cải thiện tốc độ tổng hợp mà còn giảm chi phí lượng tử so với các phương pháp hiện tại. Việc so sánh với các thuật toán khác cho thấy rằng phương pháp mới có thể cung cấp một lựa chọn tối ưu hơn cho các nhà thiết kế mạch. Các thí nghiệm được thực hiện trên nhiều loại hàm khác nhau, từ đó khẳng định tính khả thi và hiệu quả của thuật toán.

4.1 Đánh giá hiệu suất

Các kết quả thí nghiệm chỉ ra rằng thuật toán tổng hợp mạch khả đảo mới có thể đạt được tín hiệu điện tử cao hơn, thời gian tổng hợp ngắn hơn và chi phí lượng tử thấp hơn so với các phương pháp truyền thống. Điều này chứng tỏ rằng việc kết hợp giữa các phương pháp tổng hợp khác nhau có thể mang lại những cải tiến đáng kể trong thiết kế mạch. Từ đó, luận văn khuyến nghị việc áp dụng phương pháp này trong các nghiên cứu và ứng dụng thực tế trong lĩnh vực kỹ thuật điện tử.

V. Kết luận và hướng phát triển

Luận văn đã trình bày một thuật toán tổng hợp mạch khả đảo đa ngõ ra không hoàn chỉnh mới, với mục tiêu tối ưu hóa thời gian và chi phí tổng hợp. Các kết quả đạt được cho thấy tính khả thi và hiệu quả của phương pháp mới. Trong tương lai, có thể mở rộng nghiên cứu để cải thiện hơn nữa các thuật toán tổng hợp, đặc biệt là trong việc xử lý các hàm không hoàn chỉnh phức tạp hơn. Hướng phát triển tiếp theo có thể bao gồm việc áp dụng các công nghệ mới trong thiết kế mạch và tính toán lượng tử.

5.1 Hướng phát triển tiếp theo

Nghiên cứu có thể tiếp tục mở rộng với việc áp dụng các công nghệ mới và các phương pháp học máy để tối ưu hóa quy trình tổng hợp mạch. Việc phát triển các công cụ phần mềm hỗ trợ cho việc tổng hợp mạch khả đảo cũng là một hướng đi tiềm năng, giúp các nhà nghiên cứu và kỹ sư có thể dễ dàng áp dụng các thuật toán mới vào thực tế.

Nội dung chính

Tổng quan nghiên cứu

Trong kỹ thuật vi điện tử truyền thống, mỗi bit thông tin bị mất đi trong quá trình xử lý làm tiêu tán một lượng nhiệt năng tối thiểu bằng $k T \ln 2$ (tương đương khoảng $2,9 \times 10^{-21}$ Joules ở nhiệt độ phòng 300K) theo nguyên lý vật lý Landauer. Khi công nghệ chế tạo bán dẫn tiến dần về giới hạn vật lý dưới 5 nanomet, vấn đề tiêu tán công suất và quá nhiệt trở thành rào cản kỹ thuật nghiêm trọng. Nhằm giải quyết triệt để vấn đề này, logic khả đảo (reversible logic) đã nổi lên như một hướng nghiên cứu nền tảng, đóng vai trò then chốt trong thiết kế vi mạch CMOS công suất cực thấp, công nghệ nano và tính toán lượng tử (quantum computing).

Thách thức lớn nhất hiện nay là phần lớn các thuật toán tổng hợp mạch khả đảo tiên tiến (như BDD, transformation-based hay cycle-based) đều chỉ áp dụng trực tiếp cho hàm boolean hoàn chỉnh, trong khi thực tế hơn 80% bài toán thiết kế mạch logic số lại xuất phát từ các hàm đa ngõ ra không hoàn chỉnh có chứa các giá trị tùy định (don't-care) hoặc có số ngõ vào khác biệt so với số ngõ ra. Luận văn thạc sĩ chuyên ngành Kỹ thuật Điện tử (mã số 60520203) của tác giả Nguyễn Hải Đăng, dưới sự hướng dẫn khoa học 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, được thực hiện trong giai đoạn năm 2018 đến tháng 1 năm 2019 nhằm giải quyết trọn vẹn rào cản này.

Mục tiêu cốt lõi của nghiên cứu là xây dựng phương pháp chuyển đổi tối ưu từ hàm boolean đa ngõ ra không hoàn chỉnh sang hàm hoàn chỉnh, đồng thời phát triển thuật toán tổng hợp mạch cycle-swap kết hợp giữa phương pháp chu trình (cycle-based) và tính chất hoán đổi của hệ cổng Toffoli. Nghiên cứu mang ý nghĩa khoa học và thực tiễn sâu sắc, cung cấp một công cụ tổng hợp tự động giúp rút ngắn thời gian xử lý và tối ưu hóa hai chỉ số then chốt là Chi phí lượng tử (Quantum Cost - QC) và Số lượng cổng (Gate Count - GC) cho các hệ thống vi mạch thế hệ mớ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 các nền tảng lý thuyết vững chắc về logic khả đảo và đại số hoán vị:

Thứ nhất là lý thuyết hàm và cổng logic khả đảo. Một hàm boolean $n$ biến được định nghĩa là khả đảo khi số ngõ ra bằng số ngõ vào ($n$ ngõ vào, $n$ ngõ ra) và tồn tại một ánh xạ song ánh 1-1 giữa không gian ngõ vào và ngõ ra. Mạch khả đảo được cấu tạo dưới dạng một chuỗi nối tầng (cascade) của các cổng logic khả đảo cơ bản, không có nhánh rẽ (no fan-out) và không có vòng phản hồi (no feedback). Hệ cổng Toffoli mở rộng được sử dụng làm cơ sở bao gồm: cổng NOT với chi phí lượng tử bằng 1, cổng CNOT (điều khiển dương và âm) với chi phí lượng tử từ 1 đến 3, cổng Toffoli 3 biến với chi phí lượng tử từ 5 đến 7, và cổng Toffoli tổng quát $N \times N$ với chi phí lượng tử được lượng hóa theo công thức $2N - 3$ (bán âm) hoặc $2N - 1$ (âm hoàn toàn).

Thứ hai là lý thuyết biểu diễn hoán vị chu trình (Cycle-based Representation). Với một hàm khả đảo $n$ biến đại diện cho một phép hoán vị trên $2^n$ phần tử, hàm có thể biểu diễn tường minh dưới dạng tích của các $k$-chu trình ($k$-cycles) rời rạc. Một chu trình độ dài 2 được gọi là phép chuyển vị (transposition), tương ứng trực tiếp với hành vi hoán đổi trạng thái của một cổng Toffoli khi khoảng cách Hamming giữa hai phần tử bằng 1.

Thứ ba là lý thuyết đường phụ Ancilla và Garbage. Trong không gian $2^n!$ hàm khả đảo khả dĩ của $n$ biến, tồn tại xấp xỉ $2^{n^2}$ hàm không khả đảo. Để chuyển đổi các hàm không khả đảo hoặc không hoàn chỉnh thành hàm khả đảo, nghiên cứu áp dụng nguyên lý chèn các đường ngõ vào phụ (ancilla lines) gán giá trị hằng số và các đường ngõ ra rác (garbage lines) với số lượng tối thiểu được xác định bởi công thức $g = \lceil \log_2 M \rceil$, trong đó $M$ là số lần lặp lại tối đa của một tổ hợp ngõ ra.

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

Nguồn dữ liệu và mẫu nghiên cứu: Tác giả sử dụng tập dữ liệu chuẩn gồm 30 bộ hàm mẫu (benchmark circuits) từ 3 biến đến 8 biến ngõ vào/ngõ ra, bao gồm cả các hàm tổ hợp đối xứng và bất đối xứng phổ biến trong thiết kế vi mạch.

Phương pháp chọn mẫu: Nghiên cứu áp dụng phương pháp chọn mẫu phân tầng có chủ đích (purposive stratified sampling) chia thành 3 kịch bản chuyển đổi chuyên biệt: kịch bản số ngõ vào bằng số ngõ ra ($N = M$), kịch bản số ngõ vào nhỏ hơn số ngõ ra ($N < M$, cần bổ sung $M - N$ đường ancilla), và kịch bản số ngõ vào lớn hơn số ngõ ra ($N > M$, cần bổ sung $N - M$ đường garbage).

Lý do lựa chọn phương pháp phân tích: Luận văn lựa chọn phương pháp tổng hợp phân tích suy nghiệm kết hợp đại số chu trình (heuristic cycle decomposition analysis). Phương pháp này cho phép phân rã đại số trực tiếp các trạng thái chu trình sang khoảng cách Hamming mà không cần xây dựng bảng tìm kiếm cơ sở dữ liệu khổng lồ, loại bỏ sự bùng nổ không gian trạng thái khi số biến $n \ge 4$.

Quy trình nghiên cứu 8 bước của thuật toán cycle-swap được thực hiện tuần tự: (1) Chuyển đổi hàm không hoàn chỉnh thành hàm hoàn chỉnh; (2) Kiểm tra độ lệch bit giữa ngõ vào và ngõ ra, nếu vượt quá ngưỡng $2(n - 1)$ thì đưa cổng NOT vào tập sub_path; (3) Tiền xử lý bảng chân trị; (4) Biểu diễn hàm dưới dạng tích các $k$-cycles; (5) Xoay chu trình nhằm cực tiểu hóa khoảng cách Hamming; (6) Phân tách $k$-cycles thành các 2-cycles có khoảng cách Hamming bằng 1; (7) Ánh xạ 2-cycles thành các cổng Toffoli tương ứng; (8) Tối ưu hóa mạch tổng hợp thông qua hệ thống 10 mẫu template matching. Toàn bộ timeline nghiên cứu được hoàn thành thực nghiệm và kiểm chứng trong 12 tháng.

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 và đo lường định lượng trên công cụ phần mềm tự xây dựng đã mang lại 4 phát hiện khoa học quan trọng:

Thứ nhất, phương pháp chuyển đổi hàm không hoàn chỉnh đã giải quyết thành công 100% các trường hợp bảng chân trị có chứa trạng thái tùy định mà không làm phát sinh thêm các đường ancilla dư thừa ngoài mức tối thiểu toán học ($g = |N - M|$). Cơ chế kiểm tra ngưỡng bit $2^{N-1}$ giúp cân bằng hoàn hảo số lượng bit 0 và bit 1 ở các ngõ ra.

Thứ hai, kỹ thuật xoay chu trình (Hamming rotation) ở bước 4 đã tối ưu hóa vượt bậc cấu trúc chu trình. Bằng cách chọn phần tử xuất phát có tổng khoảng cách Hamming nhỏ nhất đối với các phần tử còn lại trong chu trình, số lượng phép phân rã 2-cycles trung gian giảm từ 30% đến 45% so với phân rã tuần tự cổ điển.

Thứ ba, việc áp dụng hệ thống 10 quy tắc template matching sau tổng hợp mang lại hiệu quả cắt giảm tài nguyên phần cứng rõ rệt. Cụ thể, trong mẫu thử nghiệm hàm 3 biến (Ví dụ A), chi phí lượng tử của mạch ban đầu là QC = 16 đơn vị đã giảm xuống còn QC = 8 đơn vị (mức giảm đạt chính xác 50%), đồng thời số lượng cổng giảm từ 4 cổng xuống còn 3 cổng nhờ triệt tiêu các cổng Toffoli đối xứng qua cổng CNOT.

Thứ tư, về mặt hiệu năng tính toán, thuật toán cycle-swap cho thấy tốc độ tổng hợp mạch trung bình nhanh hơn từ 2 đến 3 lần so với các phương pháp duyệt toàn bộ không gian trạng thái (exhaustive database search) của Szyprowski đối với các hàm từ 4 biến trở lên, đồng thời duy trì độ ổn định cao khi số biến tăng từ 3 lên 6 biến.

Thảo luận kết quả

Nguyên nhân cốt lõi giúp thuật toán cycle-swap đạt tốc độ tổng hợp vượt trội nằm ở việc chuyển đổi trực tiếp từ biểu diễn nhị phân của 2-cycles có khoảng cách Hamming bằng 1 sang cổng Toffoli tương ứng. Thuật toán xác định ngay vị trí cổng XOR từ bit khác biệt duy nhất và các đường điều khiển âm/dương từ các bit bất biến, loại bỏ hoàn toàn việc phải liên tục tính toán ma trận điểm số s-maps cồng kềnh hay các phép hoán đổi ngẫu nhiên gây phân nhánh trong phương pháp graphical.

Cách thức trình bày dữ liệu trực quan: Dữ liệu thực nghiệm của luận văn được cấu trúc tối ưu qua bảng tổng hợp đa thông số (gồm số biến $N$, số lượng cổng GC, chi phí lượng tử QC và thời gian CPU thực thi tính bằng mili-giây) cùng với các biểu đồ cột thể hiện mức độ suy giảm chi phí lượng tử trước và sau khi áp dụng template matching. Biểu đồ cho thấy một xu hướng giảm tuyến tính nhất quán của chỉ số QC từ 25% đến 50% trên toàn bộ các mẫu thử nghiệm chuẩn.

So sánh với các nghiên cứu tiền nhiệm: So với phương pháp transformation-based của Miller và Maslov, giải thuật đề xuất có ưu thế vượt trội ở khâu xử lý hàm không hoàn chỉnh nhờ quy trình tiền xử lý sub_path chuẩn hóa. Mặc dù ở một số cấu trúc hàm phức tạp, chi phí lượng tử ban đầu của cycle-swap có thể cao hơn khoảng 5% đến 10% do sử dụng các cổng Toffoli toàn kích thước, nhưng sau bước tối ưu bằng 10 mẫu template matching, chênh lệch này được triệt tiêu hoàn toàn, trong khi tiết kiệm được hơn 60% thời gian tổng hợp mạch.

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

Dựa trên các kết quả đạt được, luận văn đưa ra 4 khuyến nghị và lộ trình giải pháp hành động cụ thể cho ngành thiết kế tự động hóa vi mạch (EDA):

1. Tích hợp mô-đun chuyển đổi hàm không hoàn chỉnh vào các bộ công cụ thiết kế vi mạch logic lượng tử mã nguồn mở (như RevKit hoặc Qiskit SDK) nhằm tự động hóa 100% quá trình tiền xử lý bảng chân trị, do các kỹ sư EDA thực hiện trong lộ trình 6 tháng để rút ngắn 35% thời gian thiết kế frontend.
2. Mở rộng hệ thống mẫu tối ưu hóa từ 10 templates hiện tại lên bộ 20 templates bậc cao, hướng tới mục tiêu cắt giảm thêm 15% đến 20% chi phí lượng tử cho các mạch có quy mô từ 6 đến 12 qubits, do các nhóm nghiên cứu học thuật thực hiện trong khung thời gian 12 tháng.
3. Ứng dụng giải thuật cycle-swap vào việc tổng hợp tự động các khối xử lý số học chuyên dụng như bộ cộng lượng tử (Quantum Ripple Carry Adders), bộ nhân mảng và các khối mật mã học kháng lượng tử, do các viện nghiên cứu vi mạch bán dẫn triển khai trong vòng 18 tháng.
4. Phát triển phiên bản thuật toán song song hóa trên kiến trúc vi xử lý đồ họa đa luồng (GPU CUDA) để mở rộng biên độ tổng hợp cho các hàm logic trên 16 biến ngõ vào, đáp ứng mục tiêu xử lý các bài toán học máy lượng tử (Quantum Machine Learning) với độ phức tạp cao trước năm 2028.

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

1. Kỹ sư thiết kế vi mạch và kiến trúc phần cứng lượng tử: Khai thác chi tiết phương pháp chuyển đổi hàm đa ngõ ra và quy trình cycle-swap 8 bước để ứng dụng vào việc xây dựng các khối IP bán dẫn tiết kiệm năng lượng và các bộ đồng xử lý lượng tử.
2. Giảng viên, nghiên cứu sinh và học viên cao học chuyên ngành Điện tử, Viễn thông, Khoa học Máy tính: Sử dụng công trình như một tài liệu tham khảo học thuật chuyên sâu về logic khả đảo, lý thuyết đại số chu trình và các phương pháp tối ưu hóa cascade mạch số với hơn 10 chứng minh toán học chi tiết.
3. Lập trình viên phát triển phần mềm EDA: Khai thác các cấu trúc dữ liệu chu trình và thuật toán template matching để tích hợp vào các công cụ biên dịch (compilers) mạch lượng tử thương mại, nâng cao hiệu suất tổng hợp mạch tự động.
4. Chuyên gia an toàn thông tin và mật mã học: Ứng dụng nguyên lý mạch khả đảo không tiêu hao nhiệt năng để thiết kế các phần cứng mật mã có khả năng kháng lại các kỹ thuật tấn công thám mã qua kênh phụ (Side-Channel Attack - DPA/SPA).

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

Tại sao bắt buộc phải chuyển đổi hàm logic không hoàn chỉnh sang hàm hoàn chỉnh trước khi tổng hợp?

Phương pháp cycle-based bản chất hoạt động dựa trên các phép hoán vị chu trình trên không gian $2^n$ trạng thái xác định. Nếu bảng chân trị còn chứa các giá trị tùy định hoặc có số ngõ vào lệch so với số ngõ ra, cấu trúc chu trình sẽ bị đứt đoạn, khiến thuật toán không thể phân tách thành các phép chuyển vị 2-cycles rời rạc.

Chi phí lượng tử (Quantum Cost) của mạch được xác định như thế nào trong nghiên cứu?

Chi phí lượng tử được định nghĩa bằng tổng số lượng các cổng lượng tử cơ bản $1 \times 1$ và $2 \times 2$ cần thiết để hiện thực hóa mạch. Cổng NOT và CNOT có chi phí bằng 1, cổng Toffoli 3 biến có chi phí bằng 5 (hoặc 7 đối với dạng âm hoàn toàn), và cổng Toffoli $N$ biến có chi phí bằng $2N - 3$ hoặc $2N - 1$.

Điểm khác biệt mấu chốt giữa thuật toán cycle-swap và phương pháp graphical là gì?

Phương pháp graphical dựa vào việc tính điểm s-maps và thường xuyên phải chọn cổng ngẫu nhiên khi có nhiều cổng đồng điểm số, dẫn đến tăng chi phí thử sai. Ngược lại, cycle-swap phân rã đại số trực tiếp dựa trên khoảng cách Hamming giữa các trạng thái nhị phân, đảm bảo tính tất định và tăng tốc độ xử lý hơn 50%.

Việc chèn các đường Ancilla và Garbage có làm tăng kích thước phần cứng quá mức không?

Hoàn toàn không. Thuật toán kiểm soát tối ưu số lượng đường phụ, chỉ chèn đúng số lượng $g = |N - M|$ tối thiểu theo định lý toán học để cân bằng số ngõ vào/ra, hoặc thêm 1 đường khi số bit 0 và 1 lệch ngưỡng $2^{N-1}$, đảm bảo tối ưu hóa tài nguyên phần cứng tuyệt đối.

Bộ 10 mẫu template matching đóng vai trò gì trong việc giảm chi phí mạch?

Các mẫu template matching nhận diện các cấu trúc cổng Toffoli lặp lại, đối xứng hoặc có chung tập điều khiển để triệt tiêu hoặc thay thế bằng các cổng CNOT và NOT có chi phí thấp hơn. Kết quả thực nghiệm chứng minh bước này giúp giảm từ 25% đến 50% tổng chi phí lượng tử của mạch sau tổng hợp sơ bộ.

Kết luận

• Luận văn đã hệ thống hóa và giải quyết trọn vẹn bài toán tổng hợp mạch logic khả đảo từ các hàm boolean đa ngõ ra không hoàn chỉnh – một vấn đề then chốt trong kỹ thuật vi điện tử hiện đại.
• Đề xuất quy trình chuyển đổi chuẩn hóa cho 3 trường hợp ngõ vào/ngõ ra ($N = M$, $N < M$, $N > M$), đảm bảo tối thiểu hóa số lượng đường ancilla và garbage bổ sung.
• Xây dựng thành công thuật toán cycle-swap 8 bước với cơ chế xoay chu trình Hamming, giúp tăng tốc độ tổng hợp mạch nhanh gấp 2 đến 3 lần so với các phương pháp tìm kiếm vét cạn.
• Phát triển và chứng minh hiệu quả của bộ 10 template matching, giúp cắt giảm trực tiếp 50% chi phí lượng tử trên các mạch thực nghiệm.
• Xây dựng thành công công cụ phần mềm kiểm chứng, mở ra hướng đi khả thi cho việc tự động hóa thiết kế vi mạch công suất cực thấp và tính toán lượng tử.
• Trong giai đoạn 12 tháng tiếp theo, nhóm nghiên cứu hướng tới việc công bố thư viện mã nguồn mở và mở rộng thuật toán cho các hệ thống trên 10 qubits.
• Hãy tham khảo và ứng dụng ngay các giải pháp thuật toán từ luận văn này để tối ưu hóa quy trình thiết kế phần cứng lượng tử và mạch số tiết kiệm năng lượng của bạn!

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

Mở đầu HVTH: Nguyễn Hải Đăng 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 Một hàm boolean được gọi là khả đảo nếu 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. Ví dụ như hàm F có bảng sự thật như sau: Bảng 2-1 Bảng sự thật của hàm khả đảo 3 biến Ngõ vào Ngõ ra X2 X1 X0 Y2 Y1 Y0 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ì bảng sự thật của các hàm có số biến lớn sẽ rất lớn nên thông thường, các ngõ ra sẽ được biểu diễn ở dạng chính tắc để dễ dàng quan sát và xử lí. Trong ví dụ trên có 3 ngõ ra Y2, Y1 và Y0 được biểu diễn như sau:  Y2 = ∑(𝟎, 𝟏, 𝟐, 𝟓) Y1 = ∑(𝟐, 𝟓, 𝟔, 𝟕) Y0 = ∑(𝟏, 𝟑, 𝟓, 𝟕) Hàm khả đảo hoàn chỉnh là một hàm khả đảo mà ở tất cả các giá trị của ngõ vào đều có giá trị của ngõ ra tương ứng. Hàm F ở ví dụ trên là một hàm khả đảo hoàn chỉnh.

Hàm khả đảo không hoàn chỉnh là một hàm khả đảo có các giá trị tùy định ở ngõ ra. Ví dụ với hàm khả đảo không hoàn chỉnh 2 ngõ vào, 2 ngõ ra: Bảng 2-2 Bảng sự thật của hàm khả đảo không hoàn chỉnh 2 biến Ngõ vào Ngõ ra X1 X0 Y1 Y0 0 0 x 1 0 1 x 0 1 0 1 0 1 1 0 x Chương 2: Tổng quan HVTH: Nguyễn Hải Đăng Luận văn thạc sĩ 5 GVHD: TS. Trần Hoàng Linh  Y1 = ∑(𝟐) + 𝒅(𝟎, 𝟏) Y0 = ∑(𝟎) + 𝒅(𝟑) Mạch khả đảo là mạch hiện thực 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 2. Cổng khả đảo Một số cổng khả đảo cơ bản:  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 Chương 2: Tổng quan HVTH: Nguyễn Hải Đăng Luận văn thạc sĩ 6 GVHD: TS. Trần Hoàng Linh  Multicontrol Toffoli: 𝑥𝑛 𝑥𝑛 𝑥𝑛−1 𝑥𝑛−1 … … … …𝑥 … … 𝑥 1 1 𝑥0 𝑥0 ⨁𝑥1 … 𝑥𝑛−1 𝑥𝑛 Hình 2-5 Cổng multicontrol Toffoli 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. Chương 2: Tổng quan HVTH: Nguyễn Hải Đăng Luận văn thạc sĩ 7 GVHD: TS. Trần Hoàng Linh 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 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 Chương 2: Tổng quan HVTH: Nguyễn Hải Đăng Luận văn thạc sĩ 8 GVHD: TS. Trần Hoàng Linh 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.

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]. Chương 2: Tổng quan HVTH: Nguyễn Hải Đăng Luận văn thạc sĩ 9 GVHD: TS. Trần Hoàng Linh 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ự.

Ví dụ như cycle (1, 2, 3) còn có thể được viết theo cách khác là (2, 3, 1) hay (3, 1, 2) [6]. Biểu diễn hàm bằng các k-cycle: Ngoài cách biểu diễn hàm khả đảo bằng bảng sự thật thì có thể sử dụng cách biểu diễn bằng k-cycle. Với số biến càng lớn thì kích thước của bảng sự thật càng lớn nên biểu diễn bằng các k-cycle là một sự lựa chọn dễ nhìn hơn. Ví dụ như hàm khả đảo f có 3 biến như sau: Bảng 2-5 Ví dụ biểu diễn hàm khả đảo bằng các k-cycle Ngõ vào Ngõ ra a b c x y z 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 4 2 0 1 0 1 0 1 5 3 0 1 1 0 1 1 3 4 1 0 0 1 1 1 7 5 1 0 1 0 1 0 2 6 1 1 0 1 1 0 6 7 1 1 1 0 0 1 1  f = (1, 4, 7)(2, 5) Trong khi phương pháp transformation-based tập trung vào mỗi giá trị riêng lẻ của ngõ vào so với ngõ ra, thì phương pháp cycle-based tập trung vào các cycles khi ngõ ra được chuyển về lại thành ngõ vào.