以基於格羅弗演算法的量子線路解決精確覆蓋問題

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：71

、訪客IP：3.144.41.200

姓名

王昱傑(Yu-Jie Wang) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

以基於格羅弗演算法的量子線路解決精確覆蓋問題
(Quantum Circuit Based on Grover′s Algorithm to Solve Exact Cover Problem)

相關論文

★ 以IEEE 802.11為基礎行動隨意無線網路之混合式省電通訊協定	★ 以范諾圖為基礎的對等式網路虛擬環境相鄰節點一致性研究
★ 行動隨意網路可調適及可延展之位置服務協定	★ 同儕式網路虛擬環境高效率互動範圍群播
★ 巨量多人線上遊戲之同儕網路互動範圍語音交談	★ 基於范諾圖之同儕式網路虛擬環境狀態管理
★ 利用多變量分析之多人線上遊戲信任使用者選擇	★ 無位置資訊無線感測網路之覆蓋及連通維持
★ 同儕網路虛擬環境3D串流同儕選擇策略	★ 一個使用802.11與RFID技術的無所不在導覽系統U-Guide之設計與實作
★ 同儕式三維資料串流	★ IM Finder: 透過即時通訊網路線上使用者找尋解答
★ 無位置資訊無線感測網路自走車有向天線導航與協調演算法	★ 多匯點無線感測網路省能及流量分散事件輪廓追蹤
★ 頻寬感知同儕式3D串流	★ 無線感測網路旋轉指向天線定位法

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

至系統瀏覽論文 (2025-8-1以後開放)

摘要(中)

近年來，量子計算(quantum computing)由於強大的計算能力在學術界和工業界都引起了廣泛的關注和研究。學術界的研究推動了理論和技術的發展，而工業界的參與加速了量子計算技術的實際應用和商業化進程。巨擘科技如IBM、Google、Microsoft，都已經投入了大量資源和人力進行量子計算的研究和開發，推出了自己的量子計算平台或套件，並開放給研究機構和開發者使用，以促進量子計算技術的應用和驗證。本論文聚焦於在 IBM 提供的量子電腦(quantum computer)及量子模擬器(quantum simulator)上，以格羅弗演算法(Grover’s algorithm)解決屬於 NPC 問題的精確覆蓋(exact cover)問題。其中使用 IBM Qiskit 套件建構量子線路(quantum circuit)，所提方法以受控量子計數器實現精確覆蓋問題的神諭(oracle)，計算宇集內的元素被集合收集(collection of sets)覆蓋的次數，及使用相位回擊(phase kickback)之機制反轉給定問題中可行解的相位，並藉由擴散器(diffuser)放大可行解的機率振幅。最後，以 IBM 公司提供的量子模擬器 ibmq_qasm_simulator 及量子電腦 ibmq_kolkata 執行量子線路並進行測量以得到問題解答，並與現存解決精確覆蓋的古典演算法進行比較。本文所提出之用於解決精確覆蓋問題之量子線路與古典電腦中的窮舉搜索法相比具有平方量級的加速，意即，古典電腦需以O(2^|S|)的時間複雜度計算，而所提出方法的量子線路僅需O(sqrt(2^|S|)) 即可解決相同的問題，其中 |S| 為精確覆蓋中集合收集 S 的大小。

摘要(英)

In recent years, quantum computing has gained widespread attention and research in both the academic and industrial sectors. Academic research has driven the development of theories and technologies, while industrial involvement has accelerated the practical applications and commercialization of quantum computing. Big Tech such as IBM, Google, and Microsoft have invested significant resources and manpower into quantum computing research and development. They have introduced their own quantum computing platforms or packages and made them available to research institutions and developers to promote the application and validation of quantum computing technology.This article focuses on solving the Exact Cover problem using Grover′s algorithm on the quantum computer and quantum simulator provided by IBM. The approach utilizes the IBM Qiskit package to construct a quantum circuit. The proposed method employs a controlled quantum counter as an implicit oracle to calculate the number of times elements in a universal set are covered by a collection of sets. It utilizes the mechanism of phase kickback to flip the phase of feasible solutions in the given problem and amplifies the phase amplitudes of feasible solutions through a diffuser. Finally, measurements are performed using IBM′s quantum simulator, ibmq_qasm_simulator, and quantum computer, ibmq_kolkata, and compared with existing classical algorithms for Exact Cover.The quantum circuit proposed in this article for solving the Exact Cover problem is compared to the exhaustive search method in classical computers and demonstrates a quadratic speedup. In other words, while classical computers require a time complexity of O(2^|S|) for solving Exact Cover problem, the proposed method can solve the same problem in just O(sqrt(2^|S|)) time, where |S| represents the size of the collection of sets S in the Exact Cover problem.

關鍵字(中)

★ 量子計算
★ 量子線路
★ 精確覆蓋
★ 格羅弗演算法
★ 量子計數
★ 量子模擬器
★ 量子電腦

關鍵字(英)

★ Quantum computing
★ Quantum circuit
★ Exact Cover
★ Grover’s algorithm
★ Quantum counting
★ Quantum simulator
★ Quantum computer

論文目次

中文摘要 i
Abstract ii
誌謝 iii
目錄 iv
圖目錄 vi
表目錄 viii
一、緒論 1
1.1 研究背景與動機 1
1.2 研究目的與方法 4
1.3 論文架構 5
二、背景知識和相關研究 6
2.1 量子位元 6
2.2 量子閘 7
2.3 量子電腦及量子模擬器 13
2.4 P、NP、NP-Complete、NP-Hard Problem 14
2.5 以通用型量子電腦求解問題之相關研究 14
2.5.1 格羅弗演算法 15
2.5.2 量子計數 16
2.5.3 基於格羅弗演算法的量子線路求解各種 NP-Hard 問題 17
2.5.3.1 漢米爾頓循環問題 17
2.5.3.2 著色問題 18
2.5.3.3 最大團圖問題 20
2.5.3.4 最大可滿足性問題 22
2.5.3.5 賽局理論問題 23
2.5.4 基於格羅弗演算法的量子線路求解藥物專利分析問題 24
2.6 精確覆蓋之問題定義 24
2.7 以古典演算法求解精確覆蓋問題之研究 26
2.7.1 以 X 演算法求解精確覆蓋問題之研究 26
2.7.2 以加權分治法求解精確覆蓋問題 27
三、提出方法 29
3.1 研究方法流程架構 29
3.2 研究方法線路架構 29
3.3 量子線路初始化 30
3.4 受控計數器 31
3.5 相位回擊 34
3.6 用於求解精確覆蓋問題之量子線路 36
3.6.1 神諭 38
3.6.2 反向神諭 39
3.6.3 格羅弗擴散器 40
四、實驗結果與分析 41
4.1 實驗環境及設備 41
4.2 實驗結果 42
4.2.1 以量子模擬器求解精確覆蓋問題 42
4.2.2 以量子電腦 ibmq_kolkata 求解精確覆蓋問題 48
4.3 實驗分析 51
4.3.1 所提方法量子位元、量子閘數量及線路深度之分析 51
4.3.2 結果比較 54
4.3.3 實驗討論 55
五、結論與未來展望 56
參考文獻 58

參考文獻

[1] IBM Roadmap。2023 年 6 月 12 日，取自 https://www.ibm.com/quantum/roadmap
[2] Hassija, V., Chamola, V., Saxena, V., Chanana, V., Parashari, P., Mumtaz, S., & Guizani, M. (2020). Present landscape of quantum computing. IET Quantum Communication, 1(2), 42-48.
[3] Bayerstadler, A., Becquin, G., Binder, J., Botter, T., Ehm, H., Ehmer, T., ... & Winter, F. (2021). Industry quantum computing applications. EPJ Quantum Technology, 8(1), 25.
[4] MacQuarrie, E. R., Simon, C., Simmons, S., & Maine, E. (2020). The emerging commercial landscape of quantum computing. Nature Reviews Physics, 2(11), 596-598.
[5] Karp, R. M. (1972). Reducibility among combinatorial problems. In Complexity of computer computations (pp. 85-103). Springer, Boston, MA.
[6] IBM Osprey 。 2023 年 6 月 12 日，取自https://newsroom.ibm.com/2022-11-09-IBM-Unveils-400-Qubit-Plus-Quantum-Processor-and-Next-Generation-IBM-Quantum-System-Two
[7] IBM Eagle 。 2023 年 6 月 12 日，取自
https://research.ibm.com/blog/127-qubit-quantum-processor-eagle
[8] IBM Qiskit 。 2023 年 6 月 12 日，取自
https://qiskit.org/
[9] 江振瑞(2022), 輕鬆學量子程式設計 -- 從量子位元到量子演算法, 碁峰資訊, ISBN: 9786263242715
[10] Wikipedia : Bloch sphere。2023 年 6 月 12 日，取自 https://zh.wikipedia.org/zh-tw/%E5%B8%83%E6%B4%9B%E8%B5%AB%E7%90%83%E9%9D%A2
[11] IBM Quantum Lab。2023 年 6 月 12 日，取自 https://quantum-computing.ibm.com/
[12] Qiskit : Transpiler 。2023 年 6 月 12 日，取自
https://qiskit.org/documentation/apidoc/transpiler.html
[13] IBM : Quantum Volume。2023 年 6 月 12 日，取自 https://research.ibm.com/blog/quantum-volume-256
[14] Cook, S. A. (1971, May). The complexity of theorem-proving procedures. In Proceedings of the third annual ACM symposium on Theory of computing (pp. 151-158).
[15] Grover, L. K. (1996, July). A fast quantum mechanical algorithm for database search. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing (pp. 212-219).
[16] Lavor, C., Manssur, L. R. U., & Portugal, R. (2003). Grover′s algorithm: Quantum database search. arXiv preprint quant-ph/0301079.
[17] Chen, G., Fulling, S. A., Lee, H., & Scully, M. O. (2001). Grover’s algorithm for multiobject search in quantum computing. In Directions in Quantum Optics: A Collection of Papers Dedicated to the Memory of Dan Walls Including Papers Presented at the TAMU-ONR Workshop Held at Jackson, Wyoming, USA, 26–30 July 1999 (pp. 165-175). Springer Berlin Heidelberg.
[18] Boyer, M., Brassard, G., Høyer, P., & Tapp, A. (1998). Tight bounds on quantum searching. Fortschritte der Physik: Progress of Physics, 46(4‐5), 493-505.
[19] Brassard, G., Høyer, P., & Tapp, A. (1998, July). Quantum counting. In International Colloquium on Automata, Languages, and Programming (pp. 820-831). Springer, Berlin, Heidelberg.
[20] Michael A. Nielsen and Isaac L. Chuang. 2011. Quantum Computation and Quantum Information: 10th Anniversary Edition (10th ed.). Cambridge University Press, New York, NY, USA.
[21] Jehn-Ruey Jiang, "Quantum Circuit Based on Grover Algorithm to Solve Hamiltonian Cycle Problem," accepted to present at IEEE Eurasia Conference on IOT, Communication and Engineering (IEEE ECICE 2022), 2022.
[22] Saha, A., Saha, D., & Chakrabarti, A. (2020, December). Circuit design for k-coloring problem and its implementation on near-term quantum devices. In 2020 IEEE International Symposium on Smart Electronic Systems (iSES)(Formerly iNiS) (pp. 17-22). IEEE.
[23] Lutze, D. (2021). Solving Chromatic Number with Quantum Search and Quantum Counting.
[24] Mukherjee, S. (2022). A grover search-based algorithm for the list coloring problem. IEEE Transactions on Quantum Engineering, 3, 1-8.
[25] Haverly, A., & López, S. (2021, July). Implementation of Grover’s Algorithm to Solve the Maximum Clique Problem. In 2021 IEEE Computer Society Annual Symposium on VLSI (ISVLSI) (pp. 441-446). IEEE.
[26] Alasow, A., & Perkowski, M. (2022, May). Quantum Algorithm for Maximum Satisfiability. In 2022 IEEE 52nd International Symposium on Multiple-Valued Logic (ISMVL) (pp. 27-34). IEEE
[27] Roch, C., Castillo, S. L., & Linnhoff-Popien, C. (2022, March). A Grover based Quantum Algorithm for Finding Pure Nash Equilibria in Graphical Games. In 2022 IEEE 19th International Conference on Software Architecture Companion (ICSA-C) (pp. 147-151). IEEE.
[28] Wang, P. H., Chen, J. H., & Tseng, Y. J. (2022). Intelligent pharmaceutical patent search on a near-term gate-based quantum computer. Scientific Reports, 12(1), 175.
[29] Knuth, D. E. (2000). Dancing links. arXiv preprint cs/0011047.
[30] Fomin, F. V., Grandoni, F., & Kratsch, D. (2005, July). Measure and conquer: Domination–a case study. In International Colloquium on Automata, Languages, and Programming (pp. 191-203). Springer, Berlin, Heidelberg.
[31] HU Qin, NING Ai-bing, GOU Hai-wen, ZHANG Hui-zhen. Measure and Conquer Algorithm for Exact Cover Problem. Operations Research and Management Science, 2020, 29(4): 179-186.

指導教授

江振瑞(Jehn-Ruey Jiang)

審核日期

2023-7-25

推文