13.3 Comparison with ordinary circuits
On this page · Permalink · Source line 41
Theorem 13.1: Classical/restored simulation comparison
For every Boolean function \(f\),
Proof
Compute every Boolean gate onto a fresh zero wire. An AND costs one Toffoli. A NOT of an existing signal is obtained with one NOT and one CNOT. An OR is computed as \(a+b+ab\), using two CNOTs and one Toffoli. Repeated operands are simplified to a copy, not encoded as an illegal repeated-control gate. Compute the output, copy it to \(y\), and reverse the first computation. This uses at most \(6C(f)+1\) gates and restores every work register.
Conversely, express each reversible gate as an ordinary Boolean update. XOR has a four-gate AND/OR/NOT realization. A Toffoli needs that XOR plus one AND, hence at most five gates. Substitute zero for initial ancillas and \(y=0\), then read the final target. The resulting Boolean circuit has at most \(5L(f)\) gates.