Landauer's principle establishes a theoretical minimum energy cost for erasing a bit of information, but reversible computations have no such lower bound. Toffoli gates — three-bit reversible logic gates that flip the third bit only when both other inputs are 1 — are their own inverse and thus reversible. Since any Boolean function can be built from NAND gates, and a NAND gate can be simulated with a Toffoli gate (by setting the third input to 1), it follows that any Boolean function can be computed reversibly using only Toffoli gates. A practical trade-off is that Toffoli-based circuits require more input and output bits than conventional gates.

3m read timeFrom johndcook.com
Post cover image

Sort: