Bits ancilla

Em computação reversível, os bits ancilla são bits extras usados para implementar operações lógicas irreversíveis. Na computação clássica, qualquer bit de memória pode ser ligado ou desligado a qualquer momento, sem exigir conhecimento prévio ou complexidade extra. No entanto, isso não é o caso na computação quântica ou na computação clássica reversível. Nessas modelos de computação, todas as operações na memória do computador devem ser reversíveis, e alternar um bit ligado ou desligado perderia a informação sobre o valor inicial desse bit. Por essa razão, em um algoritmo quântico não há como colocar bits de forma determinística em um estado prescrito específico, a menos que se tenha acesso a bits cujo estado original seja conhecido antecipadamente. Tais bits, cujos valores são conhecidos a priori, são conhecidos como bits ancilla em uma tarefa de computação quântica ou reversível.

Usando três bits ancilla e quatro Portão Toffolis para construir um portão NOT com 5 controles. Os bits ancilla acabam sendo descartados porque os efeitos sobre eles não foram descomputados

A utilização trivial dos bits ancilla é reduzir portões quânticos complicados em portões simples. Por exemplo, ao colocar controles nos bits ancilla, um Portão Toffoli pode ser usado como um portão NOT controlado ou um portão NOT.

Para a computação reversível clássica, sabe-se que um número constante O(1) de bits ancilla é necessário e suficiente para a computação universal. Bits ancilla adicionais não são necessários, mas o espaço de trabalho extra pode permitir construções de circuitos mais simples que utilizam menos portões.