# Reversible Logic Synthesis Benchmarks Page

you are in... Main\Definitions

Definition 1. A generalized Toffoli gate TOF(x 1, x2, ..., xn; xn+1) is a gate which maps a Boolean pattern (x01, x 0 2, ..., x0n, x0n+1 ) to (x01, x02, ..., x0 n, x0n+1+ x01x0 2...x0n), where "+" is a modula-2 addition. In a machine-readable format such gate will be written as " t", number of inputs (n+1), and "x 1,x2,... ,xn,xn+1".
Examples.

• NOT gate is a TOF(Ø;a) gate.
• CNOT gate is a TOF(a;b) gate.
• Original Toffoli gate is a TOF(a,b;c).
Definition 2. A generalized Fredkin gate FRE(x1, x2, ..., xn; xn+1 , x n+2) is a gate which maps Boolean pattern (x0 1 , x02, ..., x0n, x 0 n+1, x0n+2) to (x0 1, x 02, ..., x0n, x 0n+2 , x0n+1) if and only if Boolean product x0 1x02... x0 n = 1, otherwise passes the pattern unchanged. In a machine-readable format such gate will be written as "f", number of inputs (n+2), and " x1,x2,... ,xn,xn+1,xn+2 ".
Examples.
• SWAP gate is a FRE(Ø;a,b) gate.
• Original Fredkin gate is a FRE(a;b,c) gate.
Quantum cost is found based on the reported quantum costs of the generalized Toffoli and generalized Fredkin gates by the following procedure.

In our calculations, quantum cost of the generalized Toffoli gates is taken from the following table, according to the known to us published results on their cost (a paper by Barenco et al. and its optimizations one and two).

 Size (n) Name Quantum Cost Garbage 1 0 NOT, t1 1 2 0 CNOT, t2 1 3 0 Toffoli, t3 5 4 0 Toffoli4, t4 13 5 0 t5 29 5 2 t5 26 6 0 t6 61 6 1 t6 52 6 3 t6 38 7 0 t7 125 7 1 t7 80 7 4 t7 50 8 0 t8 253 8 1 t8 100 8 5 t8 62 9 0 t9 509 9 1 t9 128 9 6 t9 74 10 0 t10 1021 10 1 t10 152 10 7 t10 86 n > 10 0 tn 2n - 3 n > 10 1 tn 24n - 88 n > 10 n-3 tn 12n - 34

The cost of a size n Fredkin gate is calculated by the formula: cost of size n Toffoli gate plus 2, as the size n Fredkin gate can be efficiently simulated by a size n Toffoli gate and 2 CNOTs.
The cost calculator finds each gate in these two tables and takes the minimal cost (if several gate implementations are known) with the condition that sum of values in columns Size and Garbage of this implementation does not exceed the number of lines in the analyzed circuit. Then, if a sequence of gates TOF(a,b,c)TOF(a,b) (Peres gate) or TOF(a,b)TOF(a,b,c) (inverse of Peres gate), its cost is set to be 4 (instead of expected 5+1 = 6), since a quantum implementation of each of these patterns was found with cost 4.
As the new quantum costs for any of the above gates are found, the table and quantum cost calculator will be updated.