On Exploiting PSOP Decomposition for Quantum Synthesis
Keywords:
Circuit decomposition, reversible logic, quantum circuitsAbstract
The synthesis strategy for quantum oracles is based on a reversible logic synthesis and a quantum compilation step. In reversible logic synthesis it is important to obtain a compact reversible circuit in order to minimize the size of the final quantum circuit. Projected Sum Of Product, PSOP, decomposition is an EXOR based technique that can be applied to any Boolean function as a very fast pre-processing step for further minimizing the circuit area in standard logic synthesis. In this paper, we exploit PSOP decomposition in quantum synthesis. In particular, we describe a new technique for the quantum synthesis of PSOP decomposed functions. The experimental results validate the proposed pre-processing method in quantum synthesis, showing an interesting gain in area, within the same time limit.
References
A. Bernasconi, A. Berti, V. Ciriani, G. M. D. Corso, and I. Fulginiti, “XOR-AND-XOR logic forms for autosymmetric functions and applications to quantum computing,” IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., vol. 42, no. 6, pp. 1861–1872, 2023.
A. Bernasconi, V. Ciriani, and R. Cordone, “On Projecting Sums of Products,” in 11th Euromicro Conference on Digital Systems Design: Architectures, Methods and Tools, 2008.
——, “The optimization of kEP-SOPs: Computational complexity, ap-proximability and experiments,” ACM Trans. Design Autom. Electr. Syst.,vol. 13, no. 2, 2008.
A. Bernasconi, V. Ciriani, A. T. Monfared, and S. Zanoni, “Compact quantum circuits for dimension reducible functions,” in 26th Euromicro Conference on Digital System Design, DSD 2023, Golem, Albania, September 6-8, 2023. IEEE, 2023, pp. 776–781.
A. Bernasconi, V. Ciriani, G. Trucco, and T. Villa, “On decomposing boolean functions via extended cofactoring,” in 2009 Design, Automation & Test in Europe Conference & Exhibition. IEEE, 2009, pp. 1464–1469.
J. C. Bioch, “The complexity of modular decomposition of boolean functions,” Discrete Applied Mathematics, vol. 149, no. 1-3, pp. 1–13, 2005.
R. Brayton, G. Hachtel, C. McMullen, and A. Sangiovanni-Vincentelli, Logic Minimization Algorithms for VLSI Synthesis. Kluwer Academic Publishers, 1984.
P. Kerntopf, “New generalizations of shannon decomposition,” in Int. Workshop on Applications of Reed-Muller Expansion in Circuit Design, 2001, pp. 109–118.
D. Maslov, G. W. Dueck, and D. M. Miller, “Synthesis of fredkin-toffoli reversible networks,” IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 13, no. 6, pp. 765–769, 2005.
G. Meuli, M. Soeken, E. Campbell, M. Roetteler, and G. De Micheli, “The role of multiplicative complexity in compiling low t-count oracle circuits,” in 2019 IEEE/ACM International Conference on Computer-Aided Design (ICCAD). IEEE, 2019, pp. 1–8.
G. Meuli, M. Soeken, E. Campbell, M. Roetteler, and G. D. Micheli, “The role of multiplicative complexity in compiling low $t$-count oracle circuits,” in Proceedings of the International Conference on Computer-Aided Design, ICCAD, D. Z. Pan, Ed. ACM, 2019, pp. 1–8.
D. M. Miller, D. Maslov, and G. W. Dueck, “A transformation based algorithm for reversible logic synthesis,” in Proceedings of the 40th annual Design Automation Conference, 2003, pp. 318–323.
M. A. Nielsen and I. L. Chuang, Quantum computation and quantum information. Cambridge university press, 2010.
B. Schmitt, F. Mozafari, G. Meuli, H. Riener, and G. D. Micheli, “From boolean functions to quantum circuits: A scalable quantum compilation flow in C++,” in Design, Automation & Test in Europe Conference & Exhibition. IEEE, 2021, pp. 1044–1049.
B. Schmitt, M. Soeken, G. D. Micheli, and A. Mishchenko, “Scaling-up ESOP synthesis for quantum compilation,” in 2019 IEEE 49th International Symposium on Multiple-Valued Logic (ISMVL), Fredericton, NB, Canada, May 21-23, 2019. IEEE, 2019, pp. 13–18.
E. Testa, M. Soeken, H. Riener, L. Amaru, and G. D. Micheli, “A logic synthesis toolbox for reducing the multiplicative complexity in logic networks,” in 2020 Design, Automation Test in Europe Conference Exhibition (DATE), 2020, pp. 568–573.
E. Testa, M. Soeken, L. G. Amar`u, and G. D. Micheli, “Reducing the multiplicative complexity in logic networks for cryptography and security applications,” in Proceedings of the 56th Annual Design Automation Conference 2019, DAC 2019, Las Vegas, NV, USA, 2019, p. 74.
R. Wille, S. Hillmich, and L. Burgholzer, “Efficient and correct compilation of quantum circuits,” in 2020 IEEE International Symposium on Circuits and Systems (ISCAS). IEEE, 2020, pp. 1–5.
S. Yang, “Logic synthesis and optimization benchmarks user guide version 3.0,” Microelectronic Center, User Guide, 1991.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2024 Anna Bernasconi, Valentina Ciriani, Gianmarco Cuciniello, Asma Taheri Monfared
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
License Terms:
Except where otherwise noted, content on this website is lincesed under a Creative Commons Attribution Non-Commercial License (CC BY NC)
Use, distribution and reproduction in any medium, provided the original work is properly cited and is not used for commercial purposes, is permitted.
Copyright to any article published by WiPiEC retained by the author(s). Authors grant WiPiEC Journal a license to publish the article and identify itself as the original publisher. Authors also grant any third party the right to use the article freely as long as it is not used for commercial purposes and its original authors, citation details, and publisher are identified, in accordance with CC BY NC license. Fore more information on license terms, click here.