Open Access iconOpen Access

ARTICLE

crossmark

Novel Quantum Algorithms to Minimize Switching Functions Based on Graph Partitions

Peng Gao*, Marek Perkowski, Yiwei Li, Xiaoyu Song

Department of Electrical and Computer Engineering, Portland State University, Portland, Oregon, 97201, USA

* Corresponding Author: Peng Gao. Email: email

Computers, Materials & Continua 2022, 70(3), 4545-4561. https://doi.org/10.32604/cmc.2022.020483

Abstract

After Google reported its realization of quantum supremacy, Solving the classical problems with quantum computing is becoming a valuable research topic. Switching function minimization is an important problem in Electronic Design Automation (EDA) and logic synthesis, most of the solutions are based on heuristic algorithms with a classical computer, it is a good practice to solve this problem with a quantum processer. In this paper, we introduce a new hybrid classic quantum algorithm using Grover’s algorithm and symmetric functions to minimize small Disjoint Sum of Product (DSOP) and Sum of Product (SOP) for Boolean switching functions. Our method is based on graph partitions for arbitrary graphs to regular graphs, which can be solved by a Grover-based quantum searching algorithm we proposed. The Oracle for this quantum algorithm is built from Boolean symmetric functions and implemented with Lattice diagrams. It is shown analytically and verified by simulations on a quantum simulator that our methods can find all solutions to these problems.

Keywords


Cite This Article

APA Style
Gao, P., Perkowski, M., Li, Y., Song, X. (2022). Novel quantum algorithms to minimize switching functions based on graph partitions. Computers, Materials & Continua, 70(3), 4545-4561. https://doi.org/10.32604/cmc.2022.020483
Vancouver Style
Gao P, Perkowski M, Li Y, Song X. Novel quantum algorithms to minimize switching functions based on graph partitions. Comput Mater Contin. 2022;70(3):4545-4561 https://doi.org/10.32604/cmc.2022.020483
IEEE Style
P. Gao, M. Perkowski, Y. Li, and X. Song "Novel Quantum Algorithms to Minimize Switching Functions Based on Graph Partitions," Comput. Mater. Contin., vol. 70, no. 3, pp. 4545-4561. 2022. https://doi.org/10.32604/cmc.2022.020483

Citations




cc This work is licensed under a Creative Commons Attribution 4.0 International License , which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
  • 1854

    View

  • 1123

    Download

  • 0

    Like

Share Link