Design of Low-Complexity Quantum Grover Algorithm for Resource Allocation 


Vol. 45,  No. 12, pp. 2046-2054, Dec.  2020
10.7840/kics.2020.45.12.2046


PDF
  Abstract

In this paper we propose a technique to solve the problem of graph coloring, which is a problem corresponding to channel allocation problem, with a low complexity quantum Grover algorithm. The Grover algorithm, a quantum algorithm for solving NP problems, has a quadratic speed up effect compared to digital algorithm when finding answers in N databases so research has been actively carried out. In general, it is evaluated to have strengths in optimizing the base of optimal path exploration, small factor resolution, and mass data exploration. The study on multi-coloring problem using digital algorithm has solved the problem of coloring by replacing the graph with simple graph to applying the algorithm or reducing the number of nodes. Despite these efforts, however, the digital algorithm that solves the coloring problem studied so far has not achieved satisfactory performance by some limitations. Therefore, in order to overcome these limitations, this paper shows the result of reducing complexity in solving multi-coloring problem by reducing input state dimension of Grover Search Algorithm.

  Statistics
Cumulative Counts from November, 2022
Multiple requests among the same browser session are counted as one view. If you mouse over a chart, the values of data points will be shown.


  Cite this article

[IEEE Style]

G. Min and J. Heo, "Design of Low-Complexity Quantum Grover Algorithm for Resource Allocation," The Journal of Korean Institute of Communications and Information Sciences, vol. 45, no. 12, pp. 2046-2054, 2020. DOI: 10.7840/kics.2020.45.12.2046.

[ACM Style]

Gun-sik Min and Jun Heo. 2020. Design of Low-Complexity Quantum Grover Algorithm for Resource Allocation. The Journal of Korean Institute of Communications and Information Sciences, 45, 12, (2020), 2046-2054. DOI: 10.7840/kics.2020.45.12.2046.

[KICS Style]

Gun-sik Min and Jun Heo, "Design of Low-Complexity Quantum Grover Algorithm for Resource Allocation," The Journal of Korean Institute of Communications and Information Sciences, vol. 45, no. 12, pp. 2046-2054, 12. 2020. (https://doi.org/10.7840/kics.2020.45.12.2046)

Search
(IN TITLE, AUTHOR, ABSTRACT,KEYWORDS)

Advanced Search ▼

POPULAR KEYWORDS
(TOP 10 KEYWORDS)

Recent Publications
(LAST 3 YEARS)






pISSN : 1226 - 4717
eISSN : 2287 - 3880