8 Exact Synthesis of ESOP Forms
193
NPN4 equivalence class, Boolean functions that appeared during 8-LUT mapping,
and randomly generated Boolean functions. Moreover, we show how the proposed
techniques can be used to reduce the costs for implemented quantum circuits. We
envision that the proposed SAT-based synthesis technique can be integrated with
large-scale ESOP optimization procedures, e.g., by selecting windows of terms and
resynthesizing them.
Acknowledgements This research was supported by H2020-ERC-2014-ADG 669354 CyberCare
(200021-146600) and the Institutional Strategy of the University of Bremen, funded by the German
Excellence Initiative.
References
1. Amy, M., Maslov, D., Mosca, M., Roetteler, M.: A meet-in-the-middle algorithm for fast
synthesis of depth-optimal quantum circuits. IEEE Trans. CAD Integr. Circuits Syst. 32(6),
818–830 (2013)
2. Audemard, G., Simon, L.: On the glucose SAT solver. Int. J. Artif. Intell. Tools 27(1), 1–25
(2018)
3. Barenco, A., Bennett, C.H., Cleve, R., Divincenzo, D.P., Margolus, N., Shor, P., Sleator, T.,
Smolin, J.A., Weinfurter, H.: Elementary gates for quantum computation. Phys. Rev. A: At.
Mol. Opt. Phys. 52(5), 3457–3467 (1995)
4. Brayton, R.K., Mishchenko, A.: ABC: an academic industrial-strength verification tool. In:
Proceedings of Computer Aided Verification, 22nd International Conference, CAV 2010,
Edinburgh, July 15–19, 2010, pp. 24–40
5. De Vos, A., Van Rentergem, Y.: Young subgroups for reversible computers. Adv. Math.
Commun. 2(2), 183–200 (2008)
6. Drechsler, R.: Preudo-Kronecker expressions for symmetric functions. IEEE Trans. Comput.
48(9), 987–990 (1999)
7. Eén, N., Sörensson, N.: An extensible SAT-solver. In: Theory and Applications of Satisfiability
Testing, 6th International Conference, SAT 2003. Santa Margherita Ligure, Italy, May 5–8,
2003 Selected Revised Papers, pp. 502–518
8. Fazel, K., Thornton, M.A., Rice, J.E.: ESOP-based Toffoli gate cascade generation. In: Pacific
Rim Conference on Communications, Computers and Signal Processing (2007)
9. Feynman, R.P.: Quantum mechanical computers. Opt. News 11, 11–20 (1985)
10. Fredkin, E., Toffoli, T.: Conservative logic. Int. J. Theor. Phys. 21(3–4), 219–253 (1982)
11. Gaidukov, A.: Algorithm to derive minimum ESOP for 6-variable function. In: International
Workshop on Boolean Problems, pp. 141–148 (2002)
12. Goto, E., Takahasi, H.: Some theorems useful in threshold logic for enumerating Boolean
functions. In: IFIP Congress, pp. 747–752 (1962)
13. Kalay, U., Hall, D.V., Perkowski, M.A.: A minimal universal test set for self-test of EXORsum-of-products circuits. IEEE Trans. Comput. 49(3), 267–276 (2000)
14. Kamath, A.P., Karmarkar, N., Ramakrishnan, K.G., and Resende, M.G.C.: A continuous
approach to inductive inference. Math. Program. 57, 215–238 (1992)
15. Knuth, D.E.: The Art of Computer Programming, vol. 4. Fascicle 6: Satisfiability, 1st edn.
Addison-Wesley Professional, Boston (2015)
16. Kolesnikov, V., Schneider, T.: Improved garbled circuit: free XOR gates and applications. In:
Proceedings Automata, Languages and Programming, 35th International Colloquium, ICALP
2008, Reykjavik, July 7–11, 2008, pp. 486–498
193
NPN4 equivalence class, Boolean functions that appeared during 8-LUT mapping,
and randomly generated Boolean functions. Moreover, we show how the proposed
techniques can be used to reduce the costs for implemented quantum circuits. We
envision that the proposed SAT-based synthesis technique can be integrated with
large-scale ESOP optimization procedures, e.g., by selecting windows of terms and
resynthesizing them.
Acknowledgements This research was supported by H2020-ERC-2014-ADG 669354 CyberCare
(200021-146600) and the Institutional Strategy of the University of Bremen, funded by the German
Excellence Initiative.
References
1. Amy, M., Maslov, D., Mosca, M., Roetteler, M.: A meet-in-the-middle algorithm for fast
synthesis of depth-optimal quantum circuits. IEEE Trans. CAD Integr. Circuits Syst. 32(6),
818–830 (2013)
2. Audemard, G., Simon, L.: On the glucose SAT solver. Int. J. Artif. Intell. Tools 27(1), 1–25
(2018)
3. Barenco, A., Bennett, C.H., Cleve, R., Divincenzo, D.P., Margolus, N., Shor, P., Sleator, T.,
Smolin, J.A., Weinfurter, H.: Elementary gates for quantum computation. Phys. Rev. A: At.
Mol. Opt. Phys. 52(5), 3457–3467 (1995)
4. Brayton, R.K., Mishchenko, A.: ABC: an academic industrial-strength verification tool. In:
Proceedings of Computer Aided Verification, 22nd International Conference, CAV 2010,
Edinburgh, July 15–19, 2010, pp. 24–40
5. De Vos, A., Van Rentergem, Y.: Young subgroups for reversible computers. Adv. Math.
Commun. 2(2), 183–200 (2008)
6. Drechsler, R.: Preudo-Kronecker expressions for symmetric functions. IEEE Trans. Comput.
48(9), 987–990 (1999)
7. Eén, N., Sörensson, N.: An extensible SAT-solver. In: Theory and Applications of Satisfiability
Testing, 6th International Conference, SAT 2003. Santa Margherita Ligure, Italy, May 5–8,
2003 Selected Revised Papers, pp. 502–518
8. Fazel, K., Thornton, M.A., Rice, J.E.: ESOP-based Toffoli gate cascade generation. In: Pacific
Rim Conference on Communications, Computers and Signal Processing (2007)
9. Feynman, R.P.: Quantum mechanical computers. Opt. News 11, 11–20 (1985)
10. Fredkin, E., Toffoli, T.: Conservative logic. Int. J. Theor. Phys. 21(3–4), 219–253 (1982)
11. Gaidukov, A.: Algorithm to derive minimum ESOP for 6-variable function. In: International
Workshop on Boolean Problems, pp. 141–148 (2002)
12. Goto, E., Takahasi, H.: Some theorems useful in threshold logic for enumerating Boolean
functions. In: IFIP Congress, pp. 747–752 (1962)
13. Kalay, U., Hall, D.V., Perkowski, M.A.: A minimal universal test set for self-test of EXORsum-of-products circuits. IEEE Trans. Comput. 49(3), 267–276 (2000)
14. Kamath, A.P., Karmarkar, N., Ramakrishnan, K.G., and Resende, M.G.C.: A continuous
approach to inductive inference. Math. Program. 57, 215–238 (1992)
15. Knuth, D.E.: The Art of Computer Programming, vol. 4. Fascicle 6: Satisfiability, 1st edn.
Addison-Wesley Professional, Boston (2015)
16. Kolesnikov, V., Schneider, T.: Improved garbled circuit: free XOR gates and applications. In:
Proceedings Automata, Languages and Programming, 35th International Colloquium, ICALP
2008, Reykjavik, July 7–11, 2008, pp. 486–498