Trong mạch logic, cổng Toffoli (còn gọi là cổng CCNOT), phát minh bởi Tommaso Toffoli, là một cổng đảo ngược phổ quát, nghĩa là mọi cổng đảo ngược đều có thể xây dựng từ cổng Toffoli. Nó có 3 bit đầu vào và 3 bit đầu ra; nếu 2 bit đầu là 1, nó sẽ đảo ngược bit thứ 3; ngược lại, cả ba bit được giữ nguyên.
Hoàn cảnh
Một cổng logic L được gọi là đảo ngược nếu với mọi đầu ra y, tồn tại duy nhất đầu vào x mà L(x) = y. Nếu một cổng L là đảo ngược, tồn tại một cổng ngược L′ ánh xạ mỗi y đến một x mà L′(y) = x. Trong các cổng logic cơ bản, NOT là cổng đảo ngược, thể hiện qua bảng chân lý sau.
INPUT
OUTPUT
0
1
1
0
Tuy nhiên, cổng AND không phải cổng đảo ngược. Các đầu vào 00, 01 và 10 đều cho đầu ra 0.
Các cổng đảo ngược đã được nghiên cứu từ những năm 1960. Nguyên nhân ban đầu là do các cổng đảo ngược tỏa ra ít nhiệt (trên lý thuyết là không tỏa ra nhiệt). Với một cổng bình thường, trạng thái đầu vào bị mất đi, vì đầu ra chứa ít thông tin hơn đầu vào. Sự mất mát thông tin này làm đánh mất năng lượng ra môi trường xung quanh dưới dạng nhiệt. Một cách hiểu khác là điện tích trong mạch bị nối đất nên biến mất, mang theo một phần năng lượng nhỏ. Một cổng đảo ngược chỉ chuyển giữa các trạng thái nên không có thông tin bị mất đi, như vậy năng lượng được bảo toàn.
Gần đây, đã có thêm những động lực để nghiên cứu đến từ máy tính lượng tử. Cơ học lượng tử cần các phép biến đổi có thể đảo ngược. Vì vậy, các cổng đảo ngược là một phần quan trọng của các cổng trong cơ học lượng tử; nếu một phép tính có thể đảo ngược thì nó có thể tính bằng máy tính lượng tử.
Tính phổ quát và cổng Toffoli
Mọi cổng đảo ngược phải có số lượng bit đầu vào bằng số bit đầu ra, theo định lý Dirichlet. Có 2 cổng đảo ngược với 1 bit đầu vào. Một trong số đó là cổng NOT. Thứ hai là cổng identity, cho đầu ra chính bằng đầu vào. Với 2 bit đầu vào, cổng đảo ngược không tầm thường duy nhất là Cổng CNOT, nó đảo ngược bit thứ 2 nếu bit thứ 1 là 1.
Bảng chân lý
Dạng ma trận
INPUT
OUTPUT
0
0
0
0
0
1
0
1
1
0
1
1
1
1
1
0
Tuy nhiên, có những hàm đảo ngược không thể xây dựng chỉ từ những cổng trên. Nói cách khác, tập hợp cổng NOT và XOR không phải phổ quát. Nếu muốn biểu diễn một hàm bất kỳ bằng các cổng đảo ngược, chúng ta cần thêm một cổng nữa. Đó có thể là cổng Toffoli, được đề xuất năm 1980 bởi Toffoli.[1]
Cổng này có 3 bit đầu vào và 3 bit đầu ra. Nếu 2 bit đầu tiên bằng 1, nó sẽ đảo ngược bit thứ 3. Dưới đây là bảng chân lý:
Bảng chân lý
Dạng ma trận
INPUT
OUTPUT
0
0
0
0
0
0
0
0
1
0
0
1
0
1
0
0
1
0
0
1
1
0
1
1
1
0
0
1
0
0
1
0
1
1
0
1
1
1
0
1
1
1
1
1
1
1
1
0
Cổng này cũng có thể hiểu là ánh xạ a, b, c với a, b, c XOR (a AND b).
Cổng Toffoli là cổng phổ quát; nghĩa là với mọi hàm Booleanf(x1, x2,..., xm), tồn tại một mạch chỉ chứa cổng Toffoli, nhận vào x1, x2,..., xm cùng với một vài bit phụ và cho ra x1, x2,..., xm, f(x1, x2,..., xm), và các bit phụ (gọi là bit rác). Điều này nghĩa là chúng ta có thể sử dụng cổng Toffoli để xây dựng các hệ thống thực hiện bất kỳ hàm Boolean đảo ngược nào.
Các cổng logic liên quan
Cổng Fredkin là một cổng đảo ngược với 3 bit đầu vào. Nó sẽ hoán đổi giá trị 2 bit cuối nếu bit đầu tiên là 1.
Cổng Toffoli n bit là dạng tổng quát hóa của cổng Toffoli. Nó nhận n bit x1, x2,..., xn đầu vào và cho ra n bit. n−1 bit đầu ra đầu tiên chính là x1,..., xn−1. Bit đầu ra cuối cùng là (x1 AND... AND xn−1) XOR xn.
Cổng Toffoli có thể tạo ra bởi 5 cổng lượng tử khác, mỗi cổng có 2 đầu vào.[2]
Liên hệ với tính toán lượng tử
Mọi cổng đảo ngược có thể được lập trình trên máy tính lượng tử, vì thế cổng Toffoli cũng là một cổng lượng tử. Tuy nhiên, cổng Toffoli không thể được dùng cho mọi tính toán lượng tử, mặc dù máy tính lượng tử có thể thực hiện mọi phép tính cổ điển. Cổng Toffoli phải được lập trình cùng với một cổng qubit để có thể sử dụng cho các tính toán lượng tử. Một cổng Toffoli lượng tử đã được cài đặt thành công vào tháng 1 năm 2009 tại Đại học Innsbruck, Áo.[3]
^Technical Report MIT/LCS/TM-151 (1980) and an adapted and condensed version: Toffoli, Tommaso (1980). J. W. de Bakker and J. van Leeuwen (biên tập). Reversible computing(PDF). Automata, Languages and Programming, Seventh Colloquium. Noordwijkerhout, Netherlands: Springer Verlag. tr. 632–644. doi:10.1007/3-540-10003-2_104. ISBN3-540-10003-2. Bản gốc(PDF) lưu trữ ngày 15 tháng 4 năm 2010. Truy cập ngày 26 tháng 7 năm 2014.
