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
é:
- Se o bit alvo
estiver inicialmente em , então após a Toffoli o novo valor do alvo é .
Passo 2
Ideia básica e por que é necessária uma linha extra (ancilla):
- Uma porta AND clássica recebe dois bits
e e produz um único bit . 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
e intactas. - Concretamente: preparar uma linha ancilla com valor inicial
e usar a Toffoli com controles nas linhas e alvo na ancilla.
Passo 3
Aplicação da Toffoli como AND (receita passo a passo):
- Denote as entradas
, e a ancilla com . - Aplique a porta Toffoli com controles
e alvo . - A operação é, pelo comportamento da Toffoli,
- Resultado: a ancilla passa a conter o valor
, enquanto e 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
e o resultado após Toffoli:
- Observação: a terceira coordenada após a porta é exatamente
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
- Como a transformação é bijetiva, nenhuma informação é perdida: conhecendo a saída
é possível recuperar univocamente a entrada original . - 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
inicialmente, a Toffoli transforma em . Por isso é importante garantir antes de usá-la para produzir o AND puro. - Se for desejado apenas o bit
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 . - 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
e e uma ancilla inicializada em . - Aplique Toffoli com controles
e alvo a ancilla. - Após a porta obtém-se
, 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
e
e alvo num ancilla inicializado em
, obtém-se
ou seja, a ancilla passa a conter
preservando
e
.