Синтез квантовых схем на основе не полностью определенных функций и if-диаграмм решений

  • Анатолий Алексеевич Прихожий Белорусский национальный технический университет, пр. Независимости, 65, 220013, г. Минск, Беларусь
DOI: https://doi.org/10.33581/2520-6508-2021-3-84-97

Аннотация

Рассматривается задача синтеза и оптимизации логических обратимых и квантовых схем по функциональным описаниям, представленным диаграммами решений. Задача относится к ключевым проблемам, решаемым в целях создания квантовых компьютеров и технологий квантовых вычислений. Предлагается новый метод последовательной трансформации исходной функциональной спецификации в квантовую схему, предусматривающий следующие состояния проекта: сокращенную упорядоченную диаграмму двоичных решений, if-диаграмму решений, функциональную if-диаграмму решений, обратимую схему, квантовую схему. Новизна метода состоит в расширении разложений Шеннона и Давио булевой функции по отдельной переменной до разложений этой же функции по другой булевой функции с получением продуктов разложения, представленных не полностью определенными функциями. Неопределенность в продуктах разложения расширяет возможности по минимизации графового представления заданной функции. Вместо двух исходящих ветвей вершины двоичной диаграммы генерируются три исходящие ветви вершины if-диаграммы, что увеличивает уровень параллелизма в обратимых и квантовых схемах. Для каждого шага трансформации предложены свои правила отображения, сокращающие число линий и вентилей и глубину схемы. Сравнение новых результатов с результатами, полученными известным методом отображения вершин двоичных диаграмм решений на каскады обратимых и квантовых вентилей, показало, что использование предложенного метода позволит существенно улучшить параметры синтезируемых квантовых схем.

Биография автора

Анатолий Алексеевич Прихожий, Белорусский национальный технический университет, пр. Независимости, 65, 220013, г. Минск, Беларусь

доктор технических наук, профессор; профессор кафедры программного обеспечения информационных систем и технологий факультета информационных технологий и робототехники

Литература

  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.
Опубликован
2021-12-14
Поддерживающие организации обратимое вычисление, квантовая логическая схема, синтез, не полностью определенная функция, разложение функции, диаграмма решений, размер схемы, глубина схемы, минимизация
Как цитировать
Прихожий, А. А. (2021). Синтез квантовых схем на основе не полностью определенных функций и if-диаграмм решений. Журнал Белорусского государственного университета. Математика. Информатика, 3, 84-97. https://doi.org/10.33581/2520-6508-2021-3-84-97
Выпуск
№ 3 (2021): Журнал Белорусского государственного университета. Математика. Информатика
Раздел
Теоретические основы информатики

Copyright (c) 2021 Журнал Белорусского государственного университета. Математика. Информатика

Лицензия Creative Commons

Это произведение доступно по лицензии Creative Commons «Attribution-NonCommercial» («Атрибуция — Некоммерческое использование») 4.0 Всемирная.

Авторы, публикующиеся в данном журнале, соглашаются со следующим:

  1. Авторы сохраняют за собой авторские права на работу и предоставляют журналу право первой публикации работы на условиях лицензии Creative Commons Attribution-NonCommercial. 4.0 International (CC BY-NC 4.0).
  2. Авторы сохраняют право заключать отдельные контрактные договоренности, касающиеся неэксклюзивного распространения версии работы в опубликованном здесь виде (например, размещение ее в институтском хранилище, публикацию в книге) со ссылкой на ее оригинальную публикацию в этом журнале.
  3. Авторы имеют право размещать их работу в интернете (например, в институтском хранилище или на персональном сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению и большему количеству ссылок на данную работу. (См. The Effect of Open Access).