×

zbMATH — the first resource for mathematics

Evaluating ESOP optimization methods in quantum compilation flows. (English) Zbl 07118476
Thomsen, Michael Kirkedal (ed.) et al., Reversible computation. 11th international conference, RC 2019, Lausanne, Switzerland, June 24–25, 2019, Proceedings. Cham: Springer (ISBN 978-3-030-21499-9/pbk; 978-3-030-21500-2/ebook). Lecture Notes in Computer Science 11497, 191-206 (2019).
Summary: Exclusive-or sum-of-products (ESOP) expressions are used as intermediate representations in quantum circuit synthesis flows, and their complexity impacts the number of gates of the resulting circuits. Many state-of-the-art techniques focus on minimizing the number of product terms in a ESOP expression, either exactly or in a heuristic fashion.
In this paper, we investigate into ESOP optimization considering two recent quantum compilation flows with opposite requirements. The first flow generates Boolean functions with a small number of Boolean variables, which enables the usage of methods from exact synthesis; the second flow generates Boolean functions with many Boolean variables, such that heuristics are more effective. We focus on the reduction of the number of \(T\) gates, which are expensive in fault-tolerant quantum computing and integrate ESOP optimization methods into both flows. We show an average reductions of 36.32% in \(T\)-count for the first flow, while in the second flow an average reduction of 28.23% is achieved.
For the entire collection see [Zbl 1420.68014].
MSC:
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
81P68 Quantum computation
Software:
ABC; PySAT; ScaffCC
PDF BibTeX XML Cite
Full Text: DOI
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. Comput. Aided Des. Integr. Circ. Syst. 32(6), 818-830 (2013)
[2] Brayton, R., Mishchenko, A.: ABC: an academic industrial-strength verification tool. In: Touili, T., Cook, B., Jackson, P. (eds.) CAV 2010. LNCS, vol. 6174, pp. 24-40. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14295-6_5
[3] De Vos, A., Van Rentergem, Y.: Young subgroups for reversible computers. Adv. Math. Commun. 2(2), 183-200 (2008) · Zbl 1175.94129
[4] Drechsler, R.: Pseudo-kronecker expressions for symmetric functions. IEEE Trans. Comput. 48(9), 987-990 (1999) · Zbl 1391.94910
[5] Drechsler, R., Finder, A., Wille, R.: Improving ESOP-based synthesis of reversible logic using evolutionary algorithms. In: Di Chio, C., et al. (eds.) EvoApplications 2011. LNCS, vol. 6625, pp. 151-161. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-20520-0_16
[6] Fazel, K., Thornton, M., Rice, J.E.: ESOP-based Toffoli gate cascade generation. In: IEEE Pacific Rim Conference on Communications, Computers and Signal Processing, pp. 206-209 (2007)
[7] Haener, T., Soeken, M., Roetteler, M., Svore, K.M.: Quantum circuits for floating-point arithmetic. In: Kari, J., Ulidowski, I. (eds.) RC 2018. LNCS, vol. 11106, pp. 162-174. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-99498-7_11 · Zbl 06957263
[8] Ignatiev, A., Morgado, A., Marques-Silva, J.: PySAT: a Python toolkit for prototyping with SAT oracles. In: Beyersdorff, O., Wintersteiger, C.M. (eds.) SAT 2018. LNCS, vol. 10929, pp. 428-437. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-94144-8_26 · Zbl 06916321
[9] JavadiAbhari, A., et al.: ScaffCC: a framework for compilation and analysis of quantum computing programs. In: Proceedings of the 11th ACM Conference on Computing Frontiers, p. 1. ACM (2014)
[10] Li, C.M., Manyà, F.: MaxSAT, hard and soft constraints. In: Handbook of Satisfiability, pp. 613-631 (2009)
[11] Maslov, D.: Advantages of using relative-phase Toffoli gates with an application to multiple control Toffoli optimization. Phys. Rev. A 93(2), 022311 (2016)
[12] Miller, D.M., Wille, R., Drechsler, R.: Reducing reversible circuit cost by adding lines. In: 2010 40th IEEE International Symposium on Multiple-Valued Logic, pp. 217-222. IEEE (2010)
[13] Mishchenko, A., Chatterjee, S., Brayton, R.K.: Improvements to technology mapping for LUT-based FPGAs. IEEE Trans. Comput. Aided Des. Integr. Circ. Syst. 26(2), 240-253 (2007)
[14] Mishchenko, A., Perkowski, M.: Fast heuristic minimization of exclusive-sums-of-products. In: Proceedings of International Workshop on Applications of the Reed-Muller Expansion in Circuit Design, pp. 242-250 (2001)
[15] Mizuki, T., Otagiri, T., Sone, H.: An application of ESOP expressions to secure computations. J. Circ. Syst. Comput. 16(02), 191-198 (2007)
[16] Papakonstantinou, K., Papakonstantinou, G.: A nonlinear integer programming approach for the minimization of boolean expressions. J. Circ. Syst. Comput. 27(10), 1850163 (2018) · Zbl 0415.94016
[17] Perkowski, M., Chrzanowska-Jeske, M.: An exact algorithm to minimize mixed-radix exclusive sums of products for incompletely specified Boolean functions. In: ISCAS, pp. 1652-1655 (1990)
[18] Rawski, M.: Application of functional decomposition in synthesis of reversible circuits. In: Krivine, J., Stefani, J.-B. (eds.) RC 2015. LNCS, vol. 9138, pp. 285-290. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-20860-2_20 · Zbl 06631946
[19] Riener, H., Ehlers, R., Schmitt, B., De Micheli, G.: Exact synthesis of ESOP forms. CoRR abs/1807.11103 (2018). http://arxiv.org/abs/1807.11103
[20] Sasao, T.: EXMIN2: a simplification algorithm for exclusive-or-sum-of-products expressions for multiple-valued-input two-valued-output functions. IEEE Trans. Comput. Aided Des. Integr. Circ. Syst. 12(5), 621-632 (1993)
[21] Sasao, T.: Representations of logic functions using EXOR operators. In: Sasao, T., Fujita, M. (eds.) Representations of Discrete Functions, pp. 29-54. Springer, Boston (1996). https://doi.org/10.1007/978-1-4613-1385-4_2 · Zbl 0861.94038
[22] Soeken, M., Haener, T., Roetteler, M.: Programming quantum computers using design automation. In: Design, Automation & Test in Europe Conference & Exhibition (DATE), pp. 137-146. IEEE (2018)
[23] Soeken, M., Mozafari, F., Schmitt, B., De Micheli, G.: Compiling permutations for superconducting QPUs. In: DATE (2019, to appear)
[24] Soeken, M., Riener, H., Haaswijk, W., Micheli, G.D.: The EPFL logic synthesis libraries. CoRR abs/1805.05121 (2018). http://arxiv.org/abs/1805.05121
[25] Soeken, M., Roetteler, M., Wiebe, N., De Micheli, G.: Logic synthesis for quantum computing. CoRR abs/1706.02721 (2017). http://arxiv.org/abs/1706.02721
[26] Soeken, M., Roetteler, M., Wiebe, N., De Micheli, G.: LUT-based hierarchical reversible logic synthesis. IEEE Trans. Comput. Aided Des. Integr. Circ. Syst. (2018)
[27] Stergiou, S., Daskalakis, K., Papakonstantinou, G.: A fast and efficient heuristic ESOP minimization algorithm. In: Proceedings of the 14th ACM Great Lakes symposium on VLSI, pp. 78-81. ACM (2004)
[28] Wille, R., Soeken, M., Otterstedt, C., Drechsler, R.: Improving the mapping of reversible circuits to quantum circuits using multiple target lines. In: 2013 18th Asia and South Pacific Design Automation Conference (ASP-DAC), pp. 145-150. IEEE (2013)
[29] Zhegalkin, I.: The technique of calculation of statementsin symbolic logic. Mathe. Sbornik. 34, 9-28 (1927)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.