Reducing Iterations of Grover Search Algorithm for N-Queen Problem U sing Quantum Permutation States

Jinyoung Ha; Jun Heo

doi:10.1109/ICTC55196.2022.9952402

Reducing Iterations of Grover Search Algorithm for N-Queen Problem U sing Quantum Permutation States

Jinyoung Ha, Jun Heo

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

In this paper, we propose a construction method of Grover's algorithm to solve the N-Queen problem. Quantum permutation state was designed and applied to the initialization and amplitude amplification process in Grover's algorithm. An oracle-level quantum circuit was constructed using Boolean algebraic expressions. We reduced the number of iterations of the Grover's algorithm by decreasing the number of superposed inputs in the initialize step using quantum permutation state. We show that our algorithm has less time complexity compared to previous study that solved the N -Queen problem using Grover's algorithm with W state as a input.

Original language	English
Title of host publication	ICTC 2022 - 13th International Conference on Information and Communication Technology Convergence
Subtitle of host publication	Accelerating Digital Transformation with ICT Innovation
Publisher	IEEE Computer Society
Pages	329-331
Number of pages	3
ISBN (Electronic)	9781665499392
DOIs	https://doi.org/10.1109/ICTC55196.2022.9952402
Publication status	Published - 2022
Event	13th International Conference on Information and Communication Technology Convergence, ICTC 2022 - Jeju Island, Korea, Republic of Duration: 2022 Oct 19 → 2022 Oct 21

Publication series

Name	International Conference on ICT Convergence
Volume	2022-October
ISSN (Print)	2162-1233
ISSN (Electronic)	2162-1241

Conference

Conference	13th International Conference on Information and Communication Technology Convergence, ICTC 2022
Country/Territory	Korea, Republic of
City	Jeju Island
Period	22/10/19 → 22/10/21

Bibliographical note

Funding Information:
ACKNOWLEDGMENT This research was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (No.2019R1A2C2010061). This work was supported by the ICT R&D program of MSIT/IITP. [2021-0-01810, Development of elemental technologies for Ultra-secure Quantum Internet.

Funding Information:
This research was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (No.2019R1A2C2010061). This work was supported by the ICT R&D program of MSIT/IITP. [2021-0-01810, Development of elemental technologies for Ultra-secure Quantum Internet.

Publisher Copyright:
© 2022 IEEE.

Keywords

Grover's algorithm
N-Queen problem
Quan-tum computing
Quantum algorithm
W state

ASJC Scopus subject areas

Information Systems
Computer Networks and Communications

Access to Document

10.1109/ICTC55196.2022.9952402

Cite this

Ha, J., & Heo, J. (2022). Reducing Iterations of Grover Search Algorithm for N-Queen Problem U sing Quantum Permutation States. In ICTC 2022 - 13th International Conference on Information and Communication Technology Convergence: Accelerating Digital Transformation with ICT Innovation (pp. 329-331). (International Conference on ICT Convergence; Vol. 2022-October). IEEE Computer Society. https://doi.org/10.1109/ICTC55196.2022.9952402

Reducing Iterations of Grover Search Algorithm for N-Queen Problem U sing Quantum Permutation States. / Ha, Jinyoung; Heo, Jun.
ICTC 2022 - 13th International Conference on Information and Communication Technology Convergence: Accelerating Digital Transformation with ICT Innovation. IEEE Computer Society, 2022. p. 329-331 (International Conference on ICT Convergence; Vol. 2022-October).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Ha, J & Heo, J 2022, Reducing Iterations of Grover Search Algorithm for N-Queen Problem U sing Quantum Permutation States. in ICTC 2022 - 13th International Conference on Information and Communication Technology Convergence: Accelerating Digital Transformation with ICT Innovation. International Conference on ICT Convergence, vol. 2022-October, IEEE Computer Society, pp. 329-331, 13th International Conference on Information and Communication Technology Convergence, ICTC 2022, Jeju Island, Korea, Republic of, 22/10/19. https://doi.org/10.1109/ICTC55196.2022.9952402

Ha J, Heo J. Reducing Iterations of Grover Search Algorithm for N-Queen Problem U sing Quantum Permutation States. In ICTC 2022 - 13th International Conference on Information and Communication Technology Convergence: Accelerating Digital Transformation with ICT Innovation. IEEE Computer Society. 2022. p. 329-331. (International Conference on ICT Convergence). doi: 10.1109/ICTC55196.2022.9952402

Ha, Jinyoung ; Heo, Jun. / Reducing Iterations of Grover Search Algorithm for N-Queen Problem U sing Quantum Permutation States. ICTC 2022 - 13th International Conference on Information and Communication Technology Convergence: Accelerating Digital Transformation with ICT Innovation. IEEE Computer Society, 2022. pp. 329-331 (International Conference on ICT Convergence).

@inproceedings{04a0abcfb4834201b34649bb5cae4afd,

title = "Reducing Iterations of Grover Search Algorithm for N-Queen Problem U sing Quantum Permutation States",

abstract = "In this paper, we propose a construction method of Grover's algorithm to solve the N-Queen problem. Quantum permutation state was designed and applied to the initialization and amplitude amplification process in Grover's algorithm. An oracle-level quantum circuit was constructed using Boolean algebraic expressions. We reduced the number of iterations of the Grover's algorithm by decreasing the number of superposed inputs in the initialize step using quantum permutation state. We show that our algorithm has less time complexity compared to previous study that solved the N -Queen problem using Grover's algorithm with W state as a input.",

keywords = "Grover's algorithm, N-Queen problem, Quan-tum computing, Quantum algorithm, W state",

author = "Jinyoung Ha and Jun Heo",

note = "Funding Information: ACKNOWLEDGMENT This research was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (No.2019R1A2C2010061). This work was supported by the ICT R&D program of MSIT/IITP. [2021-0-01810, Development of elemental technologies for Ultra-secure Quantum Internet. Funding Information: This research was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (No.2019R1A2C2010061). This work was supported by the ICT R&D program of MSIT/IITP. [2021-0-01810, Development of elemental technologies for Ultra-secure Quantum Internet. Publisher Copyright: {\textcopyright} 2022 IEEE.; 13th International Conference on Information and Communication Technology Convergence, ICTC 2022 ; Conference date: 19-10-2022 Through 21-10-2022",

year = "2022",

doi = "10.1109/ICTC55196.2022.9952402",

language = "English",

series = "International Conference on ICT Convergence",

publisher = "IEEE Computer Society",

pages = "329--331",

booktitle = "ICTC 2022 - 13th International Conference on Information and Communication Technology Convergence",

}

TY - GEN

T1 - Reducing Iterations of Grover Search Algorithm for N-Queen Problem U sing Quantum Permutation States

AU - Ha, Jinyoung

AU - Heo, Jun

N1 - Funding Information: ACKNOWLEDGMENT This research was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (No.2019R1A2C2010061). This work was supported by the ICT R&D program of MSIT/IITP. [2021-0-01810, Development of elemental technologies for Ultra-secure Quantum Internet. Funding Information: This research was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education (No.2019R1A2C2010061). This work was supported by the ICT R&D program of MSIT/IITP. [2021-0-01810, Development of elemental technologies for Ultra-secure Quantum Internet. Publisher Copyright: © 2022 IEEE.

PY - 2022

Y1 - 2022

N2 - In this paper, we propose a construction method of Grover's algorithm to solve the N-Queen problem. Quantum permutation state was designed and applied to the initialization and amplitude amplification process in Grover's algorithm. An oracle-level quantum circuit was constructed using Boolean algebraic expressions. We reduced the number of iterations of the Grover's algorithm by decreasing the number of superposed inputs in the initialize step using quantum permutation state. We show that our algorithm has less time complexity compared to previous study that solved the N -Queen problem using Grover's algorithm with W state as a input.

AB - In this paper, we propose a construction method of Grover's algorithm to solve the N-Queen problem. Quantum permutation state was designed and applied to the initialization and amplitude amplification process in Grover's algorithm. An oracle-level quantum circuit was constructed using Boolean algebraic expressions. We reduced the number of iterations of the Grover's algorithm by decreasing the number of superposed inputs in the initialize step using quantum permutation state. We show that our algorithm has less time complexity compared to previous study that solved the N -Queen problem using Grover's algorithm with W state as a input.

KW - Grover's algorithm

KW - N-Queen problem

KW - Quan-tum computing

KW - Quantum algorithm

KW - W state

UR - http://www.scopus.com/inward/record.url?scp=85143254453&partnerID=8YFLogxK

U2 - 10.1109/ICTC55196.2022.9952402

DO - 10.1109/ICTC55196.2022.9952402

M3 - Conference contribution

AN - SCOPUS:85143254453

T3 - International Conference on ICT Convergence

SP - 329

EP - 331

BT - ICTC 2022 - 13th International Conference on Information and Communication Technology Convergence

PB - IEEE Computer Society

T2 - 13th International Conference on Information and Communication Technology Convergence, ICTC 2022

Y2 - 19 October 2022 through 21 October 2022

ER -

Reducing Iterations of Grover Search Algorithm for N-Queen Problem U sing Quantum Permutation States

Abstract

Publication series

Conference

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this