@inproceedings{8c0c852b013c46588db018eaa70a89a0,
title = "Quantum Circuit Based on Grover's Algorithm to Solve Exact Cover Problem",
abstract = "In this paper, we propose a quantum circuit based on Grover's algorithm to solve the exact cover problem (ECP), which is NP-hard. A novel controlled counter is designed and used to implement the ECP oracle to check if every element is covered by a set exactly once. If so, a feasible solution is found. The phase of the qubit state representing a feasible solution is flipped by calling the oracle, and the state's amplitude is amplified through the diffusion operator o(2n) times, where n is the number of sets given in the ECP. Thanks to Grover's algorithm, the proposed quantum circuit achieves quadratic speedup compared with the classical algorithm that needs to call the oracle O(2n) times. To validate our approach, we execute the proposed quantum circuit using the IBM Quantum Lab service.",
keywords = "exact cover problem, Grover's algorithm, quantum circuit, quantum oracle",
author = "Jiang, {Jehn Ruey} and Wang, {Yu Jie}",
note = "Publisher Copyright: {\textcopyright} 2023 IEEE.; 2023 VTS Asia Pacific Wireless Communications Symposium, APWCS 2023 ; Conference date: 23-08-2023 Through 25-08-2023",
year = "2023",
doi = "10.1109/APWCS60142.2023.10234054",
language = "???core.languages.en_GB???",
series = "Proceedings - 2023 VTS Asia Pacific Wireless Communications Symposium, APWCS 2023",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
booktitle = "Proceedings - 2023 VTS Asia Pacific Wireless Communications Symposium, APWCS 2023",
}