192
H. Riener et al.
Table 8.3 Synthesis of ESOP forms for Boolean functions from DBS
PKRM
Exact
Benchmark
k
Time [s]
T -gates
k
Time [s]
T -gates
1
0x50455400
18
0.00
355
4
0.01
128
2
0x0880
2
0.00
64
2
0.02
64
3
0x00f07800
4
0.00
78
3
0.11
80
4
0x00070000
8
0.00
174
2
0.01
80
5
0x0007f000
8
0.00
165
3
0.01
96
7
0x0000ff80
6
0.00
151
2
0.01
39
8
0x06170360
12
0.00
188
5
0.03
135
9
0x4770ce38
18
0.00
298
6
0.28
151
9
0x6a0a4b6e
18
0.00
339
6
0.25
167
10
0x4727724a
18
0.00
335
7
0.33
167
112
0.00
2147
40
1.06
1107
Reversible Logic Synthesis We synthesized ESOP forms for Boolean functions
obtained from decomposition-based synthesis (DBS), a recent approach to map
permutations into quantum circuits [5, 29]. We extracted the Boolean functions from
the DBS approach and synthesized for each Boolean function, a Pseudo-Kronecker
Expressions (PKRM)—a special case of ESOP forms—using the approach proposed
by Drechsler [6], and an exact ESOP form using our proposed method with
downward search.
Table 8.3 shows experimental results for 10 Boolean functions; each of them corresponds to one Toffoli gate in the quantum circuit. For both synthesis techniques,
the table lists the number of product terms (k), the required runtime (Time), and the
number of T -gates computed using Eq. (8.19). The example illustrates the positive
effect of ESOP optimization for reducing the cost of realizing a quantum circuits. By
using our exact ESOP synthesis method, the over-approximated number of T -gates
could be reduced by 48.44%, while the additional runtime can be almost neglected.
8.6 Conclusion
We have presented an exact synthesis approach for computing ESOP forms
using Boolean satisfiability. The approach needs no pre-computed information,
synthesizes one or multiple ESOP forms of minimal size, and can take completely
specified or incompletely specified Boolean functions as specifications. We have
implemented the approach using an off-the-shelf SAT-solver and have further
presented a relaxation that leverages the SAT-solver’s conflict limit to find ESOP
forms with almost minimal size. We have also presented evidence that the synthesis
procedure can deal with small-scale ESOP forms with up to 8 Boolean variables
and up to 100 terms. As benchmarks, we have used Boolean functions in the
H. Riener et al.
Table 8.3 Synthesis of ESOP forms for Boolean functions from DBS
PKRM
Exact
Benchmark
k
Time [s]
T -gates
k
Time [s]
T -gates
1
0x50455400
18
0.00
355
4
0.01
128
2
0x0880
2
0.00
64
2
0.02
64
3
0x00f07800
4
0.00
78
3
0.11
80
4
0x00070000
8
0.00
174
2
0.01
80
5
0x0007f000
8
0.00
165
3
0.01
96
7
0x0000ff80
6
0.00
151
2
0.01
39
8
0x06170360
12
0.00
188
5
0.03
135
9
0x4770ce38
18
0.00
298
6
0.28
151
9
0x6a0a4b6e
18
0.00
339
6
0.25
167
10
0x4727724a
18
0.00
335
7
0.33
167
112
0.00
2147
40
1.06
1107
Reversible Logic Synthesis We synthesized ESOP forms for Boolean functions
obtained from decomposition-based synthesis (DBS), a recent approach to map
permutations into quantum circuits [5, 29]. We extracted the Boolean functions from
the DBS approach and synthesized for each Boolean function, a Pseudo-Kronecker
Expressions (PKRM)—a special case of ESOP forms—using the approach proposed
by Drechsler [6], and an exact ESOP form using our proposed method with
downward search.
Table 8.3 shows experimental results for 10 Boolean functions; each of them corresponds to one Toffoli gate in the quantum circuit. For both synthesis techniques,
the table lists the number of product terms (k), the required runtime (Time), and the
number of T -gates computed using Eq. (8.19). The example illustrates the positive
effect of ESOP optimization for reducing the cost of realizing a quantum circuits. By
using our exact ESOP synthesis method, the over-approximated number of T -gates
could be reduced by 48.44%, while the additional runtime can be almost neglected.
8.6 Conclusion
We have presented an exact synthesis approach for computing ESOP forms
using Boolean satisfiability. The approach needs no pre-computed information,
synthesizes one or multiple ESOP forms of minimal size, and can take completely
specified or incompletely specified Boolean functions as specifications. We have
implemented the approach using an off-the-shelf SAT-solver and have further
presented a relaxation that leverages the SAT-solver’s conflict limit to find ESOP
forms with almost minimal size. We have also presented evidence that the synthesis
procedure can deal with small-scale ESOP forms with up to 8 Boolean variables
and up to 100 terms. As benchmarks, we have used Boolean functions in the