Quantum Circuit Based on Grover's Algorithm to Solve Exact Cover Problem

Jehn Ruey Jiang, Yu Jie Wang

研究成果: 書貢獻/報告類型會議論文篇章同行評審

3 引文 斯高帕斯(Scopus)

摘要

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.

原文???core.languages.en_GB???
主出版物標題Proceedings - 2023 VTS Asia Pacific Wireless Communications Symposium, APWCS 2023
發行者Institute of Electrical and Electronics Engineers Inc.
ISBN(電子)9798350316803
DOIs
出版狀態已出版 - 2023
事件2023 VTS Asia Pacific Wireless Communications Symposium, APWCS 2023 - Tainan City, Taiwan
持續時間: 23 8月 202325 8月 2023

出版系列

名字Proceedings - 2023 VTS Asia Pacific Wireless Communications Symposium, APWCS 2023

???event.eventtypes.event.conference???

???event.eventtypes.event.conference???2023 VTS Asia Pacific Wireless Communications Symposium, APWCS 2023
國家/地區Taiwan
城市Tainan City
期間23/08/2325/08/23

指紋

深入研究「Quantum Circuit Based on Grover's Algorithm to Solve Exact Cover Problem」主題。共同形成了獨特的指紋。

引用此