Descreva como a porta Toffoli pode ser usada para implementar uma porta AND de forma reversível.

Passo 1

O que o enunciado pede: descrever como a porta Toffoli pode ser usada para implementar uma porta AND de forma reversível.
Informações relevantes (o que vamos usar):
  • A porta Toffoli atua em três bits clássicos (ou qubits, no contexto quântico) e tem dois bits de controle e um bit alvo.
  • A ação matemática da Toffoli sobre os bits (x,y,z) é:
(x,y,z)\mapsto\bigl(x,\;y,\;z\oplus(x\land y)\bigr).
  • Se o bit alvo z estiver inicialmente em 0, então após a Toffoli o novo valor do alvo é z'=x\land y.

Passo 2

Ideia básica e por que é necessária uma linha extra (ancilla):
  • Uma porta AND clássica recebe dois bits a e b e produz um único bit a\land b. Isso é irreversível porque dois bits são reduzidos a um: informação se perde.
  • Em computação reversível (como com portas Toffoli) não se pode descartar informação. Portanto precisa-se de uma linha extra (chamada ancilla) onde guardar o resultado, mantendo as entradas a e b intactas.
  • Concretamente: preparar uma linha ancilla com valor inicial 0 e usar a Toffoli com controles nas linhas a,b e alvo na ancilla.

Passo 3

Aplicação da Toffoli como AND (receita passo a passo):
  • Denote as entradas a, b e a ancilla z com z=0.
  • Aplique a porta Toffoli com controles a,b e alvo z.
  • A operação é, pelo comportamento da Toffoli,
(a,b,0)\mapsto\bigl(a,\;b,\;0\oplus(a\land b)\bigr)=\bigl(a,\;b,\;a\land b\bigr).
  • Resultado: a ancilla passa a conter o valor a\land b, enquanto a e b permanecem inalterados. Pronto: tem-se uma implementação reversível do AND.

Passo 4

Verificação por tabela (mostrando todos os casos):
  • Liste os oito casos iniciais com z=0 e o resultado após Toffoli:
(0,0,0)\mapsto(0,0,0)
(0,1,0)\mapsto(0,1,0)
(1,0,0)\mapsto(1,0,0)
(1,1,0)\mapsto(1,1,1)
  • Observação: a terceira coordenada após a porta é exatamente a\land b em todos os casos, enquanto as duas primeiras coordenadas ficam iguais às entradas originais.

Passo 5

Por que isso é reversível e seguro:
  • A Toffoli é uma porta reversível (na verdade é auto-inversa): aplicar a mesma Toffoli duas vezes devolve o estado inicial, pois
z''=z\oplus(x\land y)\oplus(x\land y)=z.
  • Como a transformação é bijetiva, nenhuma informação é perdida: conhecendo a saída (a,b,a\land b) é possível recuperar univocamente a entrada original (a,b,0).
  • Portanto essa construção respeita a exigência de reversibilidade.

Passo 6

Notas práticas e variações úteis:
  • Se a ancilla não estiver em 0 inicialmente, a Toffoli transforma z em z\oplus(a\land b). Por isso é importante garantir z=0 antes de usá-la para produzir o AND puro.
  • Se for desejado apenas o bit a\land b e libertar a ancilla para reutilização, deve-se usar técnicas de “uncomputation” ou mais ancillas: tipicamente copia-se o resultado para outro local (em contexto clássico isso pode ser feito por CNOTs quando permitido) e depois desfaz-se a computação original para restaurar ancillas a 0.
  • A Toffoli é suficiente (universal) para implementar qualquer função booleana reversível, então implementar AND dessa forma é um caso padrão e muito usado.

Passo 7

Resumo prático (receita curta que dá pra escrever na prova):
  • Pegue entradas a e b e uma ancilla inicializada em 0.
  • Aplique Toffoli com controles a,b e alvo a ancilla.
  • Após a porta obtém-se (a,b,a\land b), ou seja, a ancilla contém o resultado da AND de forma reversível.

Resposta

Aplicando uma porta Toffoli com controles nos bits de entrada a e b e alvo num ancilla inicializado em 0, obtém-se
(a,b,0)\mapsto\bigl(a,\;b,\;a\land b\bigr),
ou seja, a ancilla passa a conter a\land b preservando a e b.

Exercícios relacionados