Definition 1. A generalized Toffoli
gate
TOF(x_{ 1}, x_{2}, ..., x_{n}; x_{n+1})
is a gate which maps a Boolean pattern (x^{0}_{1}, x^{
0}_{ 2}, ..., x^{0}_{n}, x^{0}_{n+1}
) to (x^{0}_{1}, x^{0}_{2}, ..., x^{0}_{
n}, x^{0}_{n+1}+ x^{0}_{1}x^{0}_{
2}...x^{0}_{n}), where "+" is a modula2 addition.
In a machinereadable format such gate will be written as " t", number of inputs (n+1), and "x_{ 1},x_{2},... ,x_{n},x_{n+1}".
Examples.
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


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

2^{n}  3

n > 10

1

tn

24n  88

n > 10

n3

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.