Porta Toffoli

porta lógica reversível que realiza inversão em um bit controlado por dois outros bits

Em circuitos lógicos, a porta Toffoli (também conhecida como porta CCNOT), inventada por Tommaso Toffoli, é uma porta lógica reversível universal, o que significa que qualquer circuito reversível clássico pode ser construído a partir de portas Toffoli. Também é conhecida como a porta "controlada-não controlada", que descreve sua ação. Tem entradas e saídas de 3 bits; se os dois primeiros bits forem 1, o terceiro bit é invertido, caso contrário, todos os bits permanecem iguais.[1]

A Porta Toffoli pode ser construída a partir de portas T e Hadamard de um qubit e um mínimo de seis CNOT.

Uma porta lógica L que consome entradas é reversível se cumprir as seguintes condições: L(x)=y é uma porta onde, para qualquer saída y, há uma entrada única x. A porta L é reversível se houver uma porta L′(y)=x que mapeia y para x. A partir das portas lógicas comuns, NOT é reversível, como pode ser visto em sua tabela de verdade a seguir.[2]

ENTRADA SAÍDA
0 1
1 0

A porta AND comum não é reversível, pois as entradas 00, 01 e 10 estão todas mapeadas para a saída 0. As portas reversíveis têm sido estudadas desde os anos 60. A motivação original era que as portas reversíveis dissipavam menos calor (ou, em princípio, nenhum calor).[3]

A motivação mais recente vem da computação quântica. Na mecânica quântica, o estado quântico pode evoluir de duas maneiras, pela equação de Schrödinger (transformações unitárias) ou pelo seu colapso. As operações lógicas para computadores quânticos, das quais a porta Toffoli é um exemplo, são transformações unitárias e, portanto, evoluem de forma reversível.[4]

Qualquer porta reversível que consuma suas entradas e permita todos os cálculos de entrada não deve ter mais bits de entrada do que bits de saída, de acordo com o princípio de encaixotamento. Para um bit de entrada, existem duas portas reversíveis possíveis. Uma delas não é. A outra é a porta de identidade, que mapeia sua entrada para a saída sem alterações. Para dois bits de entrada, a única porta não trivial é a porta NAND, que realiza uma operação XOR entre o primeiro e o segundo bit, deixando o primeiro bit inalterado.

ENTRADA SAÍDA
0 0 0 0
0 1 0 1
1 0 1 1
1 1 1 0

Referências

  1. «Toffoli Gate - an overview | ScienceDirect Topics» (em inglês). https://www.sciencedirect.com. Consultado em 20 de abril de 2023 
  2. «Toffoli gate | Prefetch» (em inglês). https://prefetch.eu. Consultado em 20 de abril de 2023 
  3. Landauer, R. (julho de 1961). IBM Journal of Research and Development. 5 (3): 183–191. ISSN 0018-8646. doi:10.1147/rd.53.0183 
  4. Williams, Colin P. (2011). Explorations in Quantum Computing. [S.l.]: Springer. pp. 25–29, 61. ISBN 978-1-84628-887-6