Lower bound on the number of Toffoli gates in a classical reversible circuit through quantum information concepts

Popescu, Sandu; Groisman, Berry; Massar, Serge

Lower bound on the number of Toffoli gates in a classical reversible circuit through quantum information concepts

Authors

Popescu, Sandu

Groisman, Berry

Massar, Serge

Description

The question of finding a lower bound on the number of Toffoli gates in a classical reversible circuit is addressed. A method based on quantum information concepts is proposed. The method involves solely concepts from quantum information - there is no need for an actual physical quantum computer. The method is illustrated on the example of classical Shannon data compression.
4 pages, 2 figures; revised version