Reversible Logic Synthesis Benchmarks Page

you are in... Main\Definitions

    Definition 1. A generalized Toffoli gate TOF(x1, x2, ..., xn; xn+1) is a gate which maps a Boolean pattern (x01, x02, ..., x0n, x0n+1) to (x01, x02, ..., x0n, x0n+1+ x01x02...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 "x1,x2,... ,xn,xn+1".
    Examples.

     Definition 2. A generalized Fredkin gate FRE(x1, x2, ..., xn; xn+1, xn+2) is a gate which maps Boolean pattern (x01, x02, ..., x0n, x0n+1, x0n+2) to (x01, x02, ..., x0n, x0n+2, x0n+1) if and only if Boolean product x01x02... x0n = 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. This table is to be updated with a better results shortly.
 

Size 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
6 0 t6 61
6 3 t6 60
7 0 t7 125
7 4 t7 112
8 0 t8 253
8 1 t8 156
8 3 t8 124
9 0 t9 507
9 4 t9 172
Table 1: Toffoli gate costs

    The cost of a size k Fredkin gate is calculated by the formula: cost of size k Toffoli gate plus 2, as the size-k Fredkin gate can be efficiently simulated by a size k 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 these gates are found, the tables and quantum cost calculator will be updated.