Ancilla bit

Using three ancilla bits and four Toffoli gates to construct a NOT gate with 5 controls. The ancilla bits end up trashed because the effects on them were not uncomputed.

Ancilla bits are extra bits (units of information) used in computing paradigms requiring reversible operations, such as classical reversible computing and quantum computing. Unlike classical computing, where bits can be freely set to 0 or 1, reversible computation requires all operations on computer memory to be invertible. Ancilla bits, whose initial state is known, provide the necessary "workspace" for performing operations that would otherwise erase information. They play a crucial role in implementing complex logic gates and enabling universal computation within these reversible models.

In quantum computing, and unless explicitly established otherwise, the values of ancilla (qu)bits require uncomputation, as they may otherwise carry unwanted entanglement and will likely invalidate the result of the computation.

Ancilla bits can simplify complex operations. For example, an ancilla bit can be used to control a Toffoli gate, effectively turning it into a simpler gate like a controlled NOT or a NOT gate.

This page is issued from Wikipedia. The text is available under Creative Commons Attribution-Share Alike 4.0 unless otherwise noted. Additional terms may apply for the media files.