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

  • Anatoly A. Prihozhy Belarusian National Technical University, 65 Niezaliežnasci Avenue, Minsk 220013, Belarus
DOI: https://doi.org/10.33581/2520-6508-2021-3-84-97

Abstract

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 functional 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.

Author Biography

Anatoly A. Prihozhy, Belarusian National Technical University, 65 Niezaliežnasci Avenue, Minsk 220013, Belarus

Anatoly A. Prihozhy, doctor of science (engineering), full professor; professor at the department of information system and technology software, faculty of information technologies and robotics

References

  1. Barenco A, Bennett CH, Cleve R, Di Vincenzo DP, Margolus N, Shor P, et al. Elementary gates for quantum computation. Physical Review A. 1995;52(5):3457–3467. DOI: 10.1103/PhysRevA.52.3457.
  2. Nielsen M, Chuang IL. Quantum computation and quantum information. Cambridge: Cambridge University Press; 2000. 700 p.
  3. Sasanian Z, Wille R, Miller DM. Realizing reversible circuits using a new class of quantum gates. In: Groeneveld P, editor. The 49th Annual design automation conference 2012; 2012 June 3–7; San Francisco, USA. New York: Association for Computing Machinery; 2012. p. 36–41.
  4. Handique M, Sonka A. An extended approach for mapping reversible circuits to quantum circuits using NCV- v1 library. Procedia Computer Science. 2018;125:832–839. DOI: 10.1016/j.procs.2017.12.106.
  5. Wille R, Chattopadhyay A, Drechsler R. From reversible logic to quantum circuits: logic design for an emerging technology. In: Najjar WA, Gerstlauer A, editors. Proceedings of the 2016 International conference on embedded computer systems: architectures, modeling and simulation; 2016 July 17–21; Samos, Greece. New York: IEEE; 2016. p. 268–274. DOI: 10.1109/SAMOS.2016.7818357.
  6. Sasanian Z. Technology mapping and optimization for reversible and quantum circuits [dissertation]. Victoria: University of Victoria; 2012. 145 p.
  7. Smith K. Technology-dependent quantum logic synthesis and compilation [dissertation] [Internet]. Dallas: Southern Methodist University; 2019 [cited 2021 September 9]. 133 p. Available from: https://scholar.smu.edu/engineering_electrical_etds/30.
  8. Burgholzer L, Raymond R, Sengupta I, Wille R. Efficient construction of functional representations for quantum algorithms. In: Yamashita S, Yokoyama T, editors. Reversible Computation. Proceedings of 13th International conference; virtual event; 2021 July 7–8. Cham: Springer; 2021. p. 227–241. (Lecture Notes in Computer Science; volume 12805). DOI: 10.1007/978-3-030-79837-6_14.
  9. Sasamala TN, Singh AK, Mohan A. Reversible logic circuit synthesis and optimization using adaptive genetic algorithm. Procedia Computer Science. 2015;70:407–413. DOI: 10.1016/j.procs.2015.10.054.
  10. Bhattacharjee A, Bandyopadhyay C, Mukherjee A, Wille R, Drechsler R, Rahaman H. Efficient implementation of nearest neighbor quantum circuits using clustering with genetic algorithm. In: 2020 IEEE 50th International Symposium on Multiple-Valued Logic (ISMVL); 2020 November 9–11; Miyazaki, Japan. Los Alamitos: IEEE; 2020. p. 40–45. DOI: 10.1109/ISMVL49045.2020.00-32.
  11. Meuli G, Schmitt B, Ehlers R, Riener H, De Micheli G. Evaluating ESOP optimization methods in quantum compilation flows. In: Thomsen M, Soeken M, editors. Reversible Computation. Proceedings of the 11th International сonference; 2019 June 24–25; Lausanne, Switzerland. Cham: Springer; 2019. p. 191–208. (Lecture Notes in Computer Science; volume 11497). DOI: 10.1007/978-3-030-21500-2_12.
  12. Wille R, Drechsler R. Effect of BDD optimization on synthesis of reversible and quantum logic. Electronic Notes in Theoretical Computer Science. 2010;253(6):57–70. DOI: 10.1016/j.entcs.2010.02.006.
  13. Zulehner A, Niemann P, Drechsler R. Accuracy and compactness in decision diagrams for quantum computation. In: 2019 Design, automation and test in Europe Conference and Exhibition (DATE); 2019 March 25–29; Florence, Italy. [S. l.]: IEEE; 2019. p. 280–283. DOI: 10.23919/DATE.2019.8715040.
  14. Lukac M, Kameyama M, Perkowski M, Kerntopf P. Minimization of quantum circuits using quantum operator forms. arXib:1701.01999. 2017 [cited 2021 September 9]: [11 p.]. Available from: https://arxiv.org/abs/1701.01999.
  15. Große D, Wille R, Dueck GW, Drechsler R. Exact multiple-control Toffoli network synthesis with SAT techniques. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 2009;28(5):703–715. DOI: 10.1109/TCAD.2009.2017215.
  16. Abdessaied N, Wille R, Soeken M, Drechsler R. Reducing the depth of quantum circuits using additional circuit lines. In: Dueck GW, Miller DM, editors. Reversible Computation. Proceedings of the 5th International Conference; 2013 July 4–5; Victoria, BC, Canada. Berlin: Springer; 2013. p. 221–233 (Lecture Notes in Computer Science; volume 7948). DOI: 10.1007/978-3-642-38986-3_18.
  17. Prihozhy AA. If-diagrams: theory and application. In: Proceedings of the 7th International workshop PATMOS’97; 1997 September 8–10; Louvain-la-Neuve, Belgium. [S. l.]: UCL; 1997. p. 369–378.
  18. Prihozhy АА. Chastichno opredelennye logicheskie sistemy i algoritmy [Incompletely specified logical systems and algorithms]. Minsk: Belarusian National Technical University; 2013. 343 p. Russian.
  19. Prihozhy AA. Synthesis of parallel adders from if-decision diagrams. System Analysis and Applied Information Science. 2020;2:61–70. DOI: 10.21122/2309-4923-2020-2-61-70.
  20. Amarú L, Gaillardon P-E, De Micheli G. Biconditional BDD: a novel canonical BDD for logic synthesis targeting XOR-rich circuits. In: 2013. Design, Automation & Test in Europe Conference & Exhibition; 2013 March 18–22; Grenoble, France. [S. l.]: IEEE; 2013. p. 1014–1017. DOI: 10.7873/DATE.2013.211.
Published
2021-12-14
Supporting Agencies reversible computation, quantum logic circuit, synthesis, incompletely specified function, expansion of function, decision diagram, circuit size, circuit depth, minimisation
How to Cite
Prihozhy, A. A. (2021). Synthesis of quantum circuits based on incompletely specified functions and if-decision diagrams. Journal of the Belarusian State University. Mathematics and Informatics, 3, 84-97. https://doi.org/10.33581/2520-6508-2021-3-84-97
Issue
No 3 (2021): Journal of the Belarusian State University. Mathematics and Informatics
Section
Theoretical Foundations of Computer Science

Copyright (c) 2021 Journal of the Belarusian State University. Mathematics and Informatics

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

The authors who are published in this journal agree to the following:

  1. The authors retain copyright on the work and provide the journal with the right of first publication of the work on condition of license Creative Commons Attribution-NonCommercial. 4.0 International (CC BY-NC 4.0).
  2. The authors retain the right to enter into certain contractual agreements relating to the non-exclusive distribution of the published version of the work (e.g. post it on the institutional repository, publication in the book), with the reference to its original publication in this journal.
  3. The authors have the right to post their work on the Internet (e.g. on the institutional store or personal website) prior to and during the review process, conducted by the journal, as this may lead to a productive discussion and a large number of references to this work. (See The Effect of Open Access.)