Cổng Toffoli

Ký hiệu của cổng Toffoli

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	${\begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&0&1\\0&0&1&0\\\end{bmatrix}}$

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.

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	${\begin{bmatrix}1&0&0&0&0&0&0&0\\0&1&0&0&0&0&0&0\\0&0&1&0&0&0&0&0\\0&0&0&1&0&0&0&0\\0&0&0&0&1&0&0&0\\0&0&0&0&0&1&0&0\\0&0&0&0&0&0&0&1\\0&0&0&0&0&0&1&0\\\end{bmatrix}}$

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 Boolean f(x₁, x₂,..., x_m), tồn tại một mạch chỉ chứa cổng Toffoli, nhận vào x₁, x₂,..., x_m cùng với một vài bit phụ và cho ra x₁, x₂,..., x_m, f(x₁, x₂,..., x_m), 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 x₁, x₂,..., x_n đầu vào và cho ra n bit. n−1 bit đầu ra đầu tiên chính là x₁,..., x_n−1. Bit đầu ra cuối cùng là (x₁ AND... AND x_n−1) XOR x_n.
• 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.

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.

Tham khảo

• Máy tính lượng tử