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