Cổng Toffoli

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm
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ả 3 bit được giữ nguyên.

Hoàn cảnh[sửa | sửa mã nguồn]

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 xL(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 xL′(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 tiêu thụ ít nhiệt (trên lý thuyết là không tiêu thụ 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[sửa | sửa mã nguồn]

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.[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


\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(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[sửa | sửa mã nguồn]

  • 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ử[sửa | sửa mã nguồn]

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 Một năm 2009 tại Đại học Innsbruck, Áo.[3]

Tham khảo[sửa | sửa mã nguồn]

Trích dẫn[sửa | sửa mã nguồn]

  1. ^ Technical Report MIT/LCS/TM-151 (1980) and an adapted and condensed version: Toffoli, Tommaso (1980). Trong J. W. de Bakker and J. van Leeuwen. Reversible computing Automata, Languages and Programming, Seventh Colloquium. Noordwijkerhout, Netherlands: Springer Verlag. tr. 632–644. doi:10.1007/3-540-10003-2_104. ISBN 3-540-10003-2. 
  2. ^ Barenco, Adriano; Bennett, Charles H.; Cleve, Richard; DiVincenzo, David P.; Margolus, Norman; Shor, Peter; Sleator, Tycho; Smolin, John A.; Weinfurter, Harald (tháng 11 năm 1995). “Elementary gates for quantum computation”. Phys. Rev. A (American Physical Society) 52 (5): 3457–3467. arXiv:quant-ph/9503016. Bibcode:1995PhRvA..52.3457B. doi:10.1103/PhysRevA.52.3457. PMID 9912645. 
  3. ^ Monz, T.; Kim, K.; Hänsel, W.; Riebe, M.; Villar, A. S.; Schindler, P.; Chwalla, M.; Hennrich, M.; Blatt, R. (tháng 1 năm 2009). “Realization of the Quantum Toffoli Gate with Trapped Ions”. R. (American Physical Society) 102 (4): 040501. arXiv:0804.0082. Bibcode:2009PhRvL.102d0501M. doi:10.1103/PhysRevLett.102.040501.