8 Exact Synthesis of ESOP Forms
187
x1
. . .
xt−1
xt+1
. . .
xn
xt
f
x1
. . .
xt−1
xt+1
. . .
xn
xt ⊕ f (x1, . . . , xt−1, xt+1, xn)
(a)
x1
x2
x3
y
x1
x2
x3
y ⊕ h(x1, x2, x3)
(b)
x 1
x 2
x 3
y H
T
T
T
†
T
†
T
†
H
H
T
T
†
T
†
T
T
†
T
T
†
H
T
T
x 1
x 2
x 3
y ⊕ h
(c)
Fig. 8.2 Graphical notation of reversible logic circuits and quantum circuits. (a) Toffoli gate. (b)
Reversible circuit. (c) Quantum circuit
control function f ; on the top-right, a concrete example of a reversible circuit
is given consisting of the cascade of the two Toffoli gates ({x 1 , ¯
x 2 }, x 5 ) and
({x 2 , x 3 }, x 5 ), where the composition function h(x 1 , x 2 , x 3 ) = x 1 ¯
x 2 ⊕ x 2 x 3 of the
two gates can be observed on line y. In this notation, the line with the ⊕ denotes the
target line, whereas black and white dots denote positive and negative control lines,
respectively. On the bottom, a quantum circuit is shown for the same example. We
show this example for completeness, but will not discuss the graphical notation of
quantum circuits (see, e.g., Soeken et al. [27] for details).
Mapping ESOP forms into reversible circuits is straightforward. An ESOP form
c 1 ⊕· · ·⊕c k with k product terms and n Boolean variables is functionally equivalent
to a reversible circuit with at most n + 2 lines and k Toffoli gates, where the control
function of each gate is exactly one c i for 1 ≤ i ≤ k. Since each Toffoli gate is
reversible, the concrete order of the Toffoli gates does not matter.
Next, Toffoli gates are mapped into a quantum gate library [18]. In this paper,
we focus on the universal fault-tolerant quantum gate library Clifford+T [17] and
use the number of T -gates as cost function. This simple cost model is based on
the assumption that T -gates are far more expensive to realize than all other gates
in the Clifford+T library [1]. Based on concrete mappings for Toffoli gates with
small number of control lines [18] and a decomposition schemata [3] for larger
Toffoli gates, an overapproximation for the number of T -gates necessary to realize
an ESOP form c 1 ⊕ · · · ⊕ c k can be computed as
T (c 1 ⊕ · · · ⊕ c k ) =
k
i=1
T cube (|c i |)
(8.19)
187
x1
. . .
xt−1
xt+1
. . .
xn
xt
f
x1
. . .
xt−1
xt+1
. . .
xn
xt ⊕ f (x1, . . . , xt−1, xt+1, xn)
(a)
x1
x2
x3
y
x1
x2
x3
y ⊕ h(x1, x2, x3)
(b)
x 1
x 2
x 3
y H
T
T
T
†
T
†
T
†
H
H
T
T
†
T
†
T
T
†
T
T
†
H
T
T
x 1
x 2
x 3
y ⊕ h
(c)
Fig. 8.2 Graphical notation of reversible logic circuits and quantum circuits. (a) Toffoli gate. (b)
Reversible circuit. (c) Quantum circuit
control function f ; on the top-right, a concrete example of a reversible circuit
is given consisting of the cascade of the two Toffoli gates ({x 1 , ¯
x 2 }, x 5 ) and
({x 2 , x 3 }, x 5 ), where the composition function h(x 1 , x 2 , x 3 ) = x 1 ¯
x 2 ⊕ x 2 x 3 of the
two gates can be observed on line y. In this notation, the line with the ⊕ denotes the
target line, whereas black and white dots denote positive and negative control lines,
respectively. On the bottom, a quantum circuit is shown for the same example. We
show this example for completeness, but will not discuss the graphical notation of
quantum circuits (see, e.g., Soeken et al. [27] for details).
Mapping ESOP forms into reversible circuits is straightforward. An ESOP form
c 1 ⊕· · ·⊕c k with k product terms and n Boolean variables is functionally equivalent
to a reversible circuit with at most n + 2 lines and k Toffoli gates, where the control
function of each gate is exactly one c i for 1 ≤ i ≤ k. Since each Toffoli gate is
reversible, the concrete order of the Toffoli gates does not matter.
Next, Toffoli gates are mapped into a quantum gate library [18]. In this paper,
we focus on the universal fault-tolerant quantum gate library Clifford+T [17] and
use the number of T -gates as cost function. This simple cost model is based on
the assumption that T -gates are far more expensive to realize than all other gates
in the Clifford+T library [1]. Based on concrete mappings for Toffoli gates with
small number of control lines [18] and a decomposition schemata [3] for larger
Toffoli gates, an overapproximation for the number of T -gates necessary to realize
an ESOP form c 1 ⊕ · · · ⊕ c k can be computed as
T (c 1 ⊕ · · · ⊕ c k ) =
k
i=1
T cube (|c i |)
(8.19)