Synthesis of quantum circuits based on incompletely specified functions and if-decision diagrams

A. A. Prihozhy

Journal of the Belarusian State University. Mathematics and Informatics, Tome 3 (2021), pp. 84-97.

Résumé

The problem of synthesis and optimisation of logical reversible and quantum circuits from functional descriptions represented as decision diagrams is considered. It is one of the key problems being solved with the aim of creating quantum computing technology and quantum computers. A new method of stepwise transformation of the initial functiona specification to a quantum circuit is proposed, which provides for the following project states: reduced ordered binary decision diagram, if-decision diagram, functional if-decision diagram, reversible circuit and quantum circuit. The novelty of the method consists in extending the Shannon and Davio expansions of a Boolean function on a single variable to the expansions of the same Boolean function on another function with obtaining decomposition products that are represented by incompletely defined Boolean functions. Uncertainty in the decomposition products gives remarkable opportunities for minimising the graph representation of the specified function. Instead of two outgoing branches of the binary diagram vertex, three outgoing branches of the if-diagram vertex are generated, which increase the level of parallelism in reversible and quantum circuits. For each transformation step, appropriate mapping rules are proposed that reduce the number of lines, gates and the depth of the reversible and quantum circuit. The comparison of new results with the results given by the known method of mapping the vertices of binary decision diagram into cascades of reversible and quantum gates shows a significant improvement in the quality of quantum circuits that are synthesised by the proposed method.

Détail

Keywords: reversible computation; quantum logic circuit; synthesis; incompletely specified function; expansion of function; decision diagram; circuit size; circuit depth; minimisation.

Bibliographie

[1] A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, “Elementary gates for quantum computation”, Physical Review A, 52(5) (1995), 3457–3467 | DOI

[2] M. Nielsen, I. L. Chuang, “Quantum computation and quantum information”, Cambridge: Cambridge University Press, 2000, 700 | MR

[3] Z. Sasanian, R. Wille, D. M. Miller, “Realizing reversible circuits using a new class of quantum gates”, The 49th Annual design automation conference 2012 (San Francisco, USA), Association for Computing Machinery, New York, 2012, 36–41

[4] M. Handique, A. Sonka, “An extended approach for mapping reversible circuits to quantum circuits using NCV- v1 library”, Procedia Computer Science, 125 (2018), 832–839 | DOI

[5] R. Wille, A. Chattopadhyay, R. Drechsler, “From reversible logic to quantum circuits: logic design for an emerging technology”, Proceedings of the 2016 International conference on embedded computer systems: architectures, modeling and simulation (Samos, Greece), New York, 2016, 268–274 | DOI | MR

[6] Z. Sasanian, “Technology mapping and optimization for reversible and quantum circuits”, Victoria: University of Victoria, 2012, 145

[7] K. Smith, Technology-dependent quantum logic synthesis and compilation, dissertation, Southern Methodist University, Dallas, 2019 | DOI

[8] L. Burgholzer, R. Raymond, I. Sengupta, R. Wille, “Efficient construction of functional representations for quantum algorithms; Reversible Computation”, Proceedings of 13th International conference; virtual event., Springer, Cham, 2021, 227–241 | DOI | MR | Zbl

[9] T. N. Sasamala, A. K. Singh, A. Mohan, “Reversible logic circuit synthesis and optimization using adaptive genetic algorithm”, Procedia Computer Science, 70 (2015), 407–413 | DOI

[10] A. Bhattacharjee, C. Bandyopadhyay, A. Mukherjee, R. Wille, R. Drechsler, H. Rahaman, “Efficient implementation of nearest neighbor quantum circuits using clustering with genetic algorithm”, IEEE 50th International Symposium on Multiple-Valued Logic (ISMVL) (Miyazaki, Japan), Los Alamitos, 2020, 40–45 | DOI | MR

[11] G. Meuli, B. Schmitt, R. Ehlers, H. Riener, Micheli. De, “Evaluating ESOP optimization methods in quantum compilation flows; Reversible Computation”, Proceedings of the 11th International sonference (Lausanne, Switzerland), 11497, Springer, Cham, 2019, 191–208 | DOI | MR

[12] R. Wille, R. Drechsler, “Effect of BDD optimization on synthesis of reversible and quantum logic”, Electronic Notes in Theoretical Computer Science, 253(6) (2010), 57–70 | DOI

[13] A. Zulehner, P. Niemann, R. Drechsler, “Accuracy and compactness in decision diagrams for quantum computation”, Design, automation and test in Europe Conference and Exhibition (DATE) (Florence, Italy), 2019, 280–283 | DOI

[14] M. Lukac, M. Kameyama, M. Perkowski, P. Kerntopf, Minimization of quantum circuits using quantum operator forms, 2017, arXiv: 1701.01999

[15] D. Grobe, R. Wille, G. W. Dueck, R. Drechsler, “Exact multiple-control Toffoli network synthesis with SAT techniques”, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 28(5) (2009), 703–715 | DOI

[16] N. Abdessaied, R. Wille, M. Soeken, R. Drechsler, “Reducing the depth of quantum circuits using additional circuit lines. Reversible Computation”, Proceedings of the 5th International Conference (Victoria, BC, Canada), 7948, Springer, Berlin, 2013, 221–233 | DOI | MR | Zbl

[17] A. A. Prihozhy, “If-diagrams: theory and application”, Proceedings of the 7th International workshop PATMOS’97 (Louvain-la-Neuve, Belgium), 1997, 369–378

[18] A. A. Prihozhy, “Chastichno opredelennye logicheskie sistemy i algoritmy [Incompletely specified logical systems and algorithms]”, Belarusian National Technical University, Minsk, 2013, 343

[19] A. A. Prihozhy, “Synthesis of parallel adders from if-decision diagrams”, System Analysis and Applied Information Science, 2 (2020), 61–70 | DOI

[20] L. Amaru, P-E. Gaillardon, Micheli. De, “Biconditional BDD: a novel canonical BDD for logic synthesis targeting XOR-rich circuits”, Design, Automation and Test in Europe Conference and Exhibition (Grenoble, France), 2013, 1014–1017 | DOI