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.

     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.     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)
 Garbage Name Quantum Cost
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
Table : Toffoli gate costs

    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.