基於格羅弗演算法之頂點覆蓋問題量子線路設計

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：28

、訪客IP：18.191.31.104

姓名

顏暐翰(Wei-Han Yan) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

基於格羅弗演算法之頂點覆蓋問題量子線路設計
(Quantum Circuit Design for Vertex Cover Problem Based on Grover’s Algorithm)

相關論文

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

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

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

摘要(中)

量子計算(quantum computation)近年來逐漸成為計算機科學的一個重要研究領域，量子的疊加態(superposition)性質讓量子計算擁有超越古典計算的潛在能力，尤其在組合最佳化(combinatorial optimization)這類高複雜度的問題特別明顯，其中在2019年Google首次展現量子霸權(quantum supremacy)是最為顯著的一個里程碑。量子霸權實際驗證了量子電腦能夠進行超越古典電腦的計算，因此吸引更多研究學者投入量子計算與量子演算法的研究。在眾多量子演算法中，格羅弗演算法(Grover′s algorithm)是最著名的量子演算法之一，本篇論文設計出基於格羅弗演算法的量子線路用於求解頂點覆蓋(vertex cover)問題。頂點覆蓋問題屬於NP完全問題，這代表求解該類問題往往要花費指數時間複雜度(exponential time complexity)，而格羅弗演算法能以解決非結構搜尋(unstructured search)問題的方式以O(√(2^(|V|) ))時間複雜度解決|V|個頂點圖的頂點覆蓋問題，這相對於古典窮舉式演算法的O(2^(|V|))時間複雜度具有平方量級的加速。格羅弗演算法的核心是必需針對問題設計出對應的量子神諭(oracle)以標記出給定問題的解答，而設計一個高效的量子神諭為一個具有挑戰性的問題。本論文提出頂點覆蓋問題格羅弗演算法量子神諭線路設計，針對已有的量子計數器(quantum counter)設計進行改良以減少量子邏輯閘的使用數量，量子計數器能確保選取的頂點集合大小滿足頂點覆蓋問題的數量限制；並且提出量子號誌(quantum semaphore)量子線路設計，能夠標記選取頂點所連接的邊，以確認選取的頂點集合是一個頂點覆蓋。本篇論文使用 IBM Q 所提供的開源軟體開發工具包 Qiskit 進行實作，並在 IBM 的量子雲端平台使用量子電腦模擬器驗證演算法的正確性，結果顯示本論文所提演算法確實可求解頂點覆蓋問題。為了更進一步比較實驗結果，所提出的演算法也在屬於雜訊中等規模量子(NISQ)階段的IBMQ mumbai量子電腦上進行實驗，發現因為現階段量子電腦的雜訊(noise)過高會因而影響執行結果成功的機率。最後，本論文分析所提出演算法量子位元與量子邏輯閘使用數量，並與現存的古典演算法進行效能比較，而且針對未來可改進方向給出建議。

摘要(英)

Quantum computation has gradually become an important research field in computer science in recent years. The property of quantum superposition gives quantum computation the potential to surpass classical computation, especially in complex problems like combinatorial optimization. In 2019, Google demonstrated quantum supremacy for the first time, which was a significant milestone. Quantum supremacy validated that quantum computers can perform computations beyond the capabilities of classical computers, attracting more researchers to delve into quantum computation and quantum algorithms. Among numerous quantum algorithms, Grover’s algorithm is one of the most famous. This paper designs a quantum circuit based on Grover′s algorithm to solve the vertex cover problem. The vertex cover problem belongs to the class of NP-complete problems, which implies that solving such problems often requires exponential time complexity. However, Grover’s algorithm provides a quadratic speedup by solving the vertex cover problem for a graph with |V| vertices using O(√(2^(|V|) )) time complexity, compared to the exponential time complexity O(2^(|V|)) of classical exhaustive search algorithms. The core of Grover′s algorithm lies in designing the corresponding quantum oracle to mark the solutions to a given problem, which poses a challenging task to design an efficient quantum oracle. This paper proposes a quantum oracle circuit design for the vertex cover problem in Grover′s algorithm. It improves the design of existing quantum counters to reduce the usage of quantum logic gates. The quantum counter ensures that the size of the selected vertex set satisfies the quantity restriction of the vertex cover problem. Additionally, a quantum semaphore circuit design is introduced, which can mark the edges connected to the selected vertices to confirm whether the selected vertex set forms a vertex cover. The implementation of the proposed methods in this paper is carried out using the open-source software development toolkit Qiskit provided by IBM Q. The correctness of the algorithm is verified through simulations on IBM′s quantum cloud platform using a quantum computer simulator. The results demonstrate that the proposed algorithm can indeed solve the vertex cover problem. To further compare the experimental results, the proposed algorithm is also tested on IBM′s NISQ quantum computer, called IBMQ mumbai. However, it is observed that the high noise level in current quantum computers can affect the success probability of execution results. Finally, this paper analyzes the usage of quantum bits and quantum logic gates in the proposed algorithm and compares its performance with existing classical algorithms. It also provides suggestions for future improvement directions.

關鍵字(中)

★ 量子計算
★ 格羅弗演算法
★ 頂點覆蓋問題
★ 量子神諭
★ 雜訊中等規模量子硬體

關鍵字(英)

★ quantum computing
★ Grover’s Algorithm
★ Vertex cover problems
★ quantum oracle
★ near-term intermediate-scale quantum (NISQ) hardware

論文目次

中文摘要 i
Abstract ii
誌謝 iii
目錄 iv
圖目錄 vi
表目錄 viii
一、緒論 1
1.1 研究背景與動機 1
1.2 研究目的與方法 3
1.3 論文架構 4
二、背景知識與相關研究 5
2.1 頂點覆蓋問題 5
2.2 P、NP、NP-Hard、NP-Complete Problem 5
2.3 量子計算演算法 7
2.3.1 格羅弗演算法 7
2.3.2 量子計數演算法 8
2.3.3 Boyer’s 演算法 9
2.4 狄拉克記號 10
2.5 量子位元 12
2.6 量子邏輯閘 14
2.7 通用型量子電腦與量子電腦模擬器 19
2.7.1 通用型量子電腦 19
2.7.2 量子電腦模擬器 20
2.8 以古典演算法求解頂點覆蓋問題相關研究 21
2.8.1 頂點覆蓋問題相關研究介紹 21
2.8.2 以正確解演算法求解特定圖的頂點覆蓋問題 21
2.8.3 以固定參數演算法求解頂點覆蓋問題 23
2.9 以量子演算法求解NP-困難問題相關研究 25
2.9.1 以格羅弗演算法求解 K-著色問題 25
2.9.2 以格羅弗演算法與量子計數演算法求解圖著色問題 27
2.9.3 以格羅弗演算法求解列表著色問題 29
2.9.4 以格羅弗演算法求解納許均衡點問題 30
2.9.5 以格羅弗演算法求解最大可滿足性問題 32
2.9.6 以格羅弗演算法求解最大完全子圖問題 33
2.9.7 以格羅弗演算法求解漢米爾頓循環問題 37
2.9.8 以格羅弗演算法求解藥物專利搜尋問題 39
三、研究方法 41
3.1 無向圖輸入方法 41
3.2 頂點覆蓋問題之格羅弗演算法神諭建構方法 43
3.2.1 選取到的頂點集合大小是否等於 k ? 43
3.2.2 記錄無向圖中的邊是否被標記過? 47
3.2.3 相位回擊 50
3.3 頂點覆蓋問題之演算法流程圖 54
四、實驗結果與分析 56
4.1 實驗環境 56
4.2 實驗結果 56
4.2.1 使用IBM量子電腦模擬器進行實驗 56
4.2.2 使用IBM量子電腦進行實驗 61
4.3 實驗分析 64
4.4 實驗結果與討論 66
五、結論與未來展望 68
參考文獻 69
附錄 73
附錄一本論文可使用的量子電腦計算資源 73

參考文獻

[1] Gusev, V. V. (2020). The vertex cover game: Application to transport networks. Omega, 97, 102102.
[2] Our quantum computing journey.[Online]. Available:
https://quantumai.google/learn/map
[3] Scheidsteger, T., Haunschild, R., Bornmann, L., & Ettl, C. (2021). Bibliometric analysis in the field of quantum technology. Quantum Reports, 3(3), 549-575.
[4] Shor, P. W. (1999). Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM review, 41(2), 303-332.
[5] Grover, L. K. (1998, May). A framework for fast quantum mechanical algorithms. In Proceedings of the thirtieth annual ACM symposium on Theory of computing (pp. 53-62).
[6] Karp, R. M. (1972). Reducibility among combinatorial problems. In Complexity of computer computations (pp. 85-103). Springer, Boston, MA.
[7] Vertex Cover Examples. url : https://commons.wikimedia.org/wiki/File:Minimum-vertex-cover.svg,
Miym, CC BY-SA 3.0 <https://creativecommons.org/licenses/by-sa/3.0>, via Wikimedia Commons.
[8] 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).
[9] Relative NPC chart. url :
https://commons.wikimedia.org/wiki/File:Relative_NPC_chart.svg, Gian Luca RuggeroActam, Public domain, via Wikimedia Commons.
[10] 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).
[11] Brassard, G., Høyer, P., & Tapp, A. (1998). Quantum counting. In Automata, Languages and Programming: 25th International Colloquium, ICALP′98 Aalborg, Denmark, July 13–17, 1998 Proceedings 25 (pp. 820-831). Springer Berlin Heidelberg.
[12] 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 (pp. 165-175). Springer, Berlin, Heidelberg.
[13] Nielsen, M.A. and Chuang, I.L. Quantum computation and quantum information. Cambridge University Press, 2000. Chapter 6.
[14] 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.
[15] Dirac, P. A. M. (1939, July). A new notation for quantum mechanics. In Mathematical Proceedings of the Cambridge Philosophical Society (Vol. 35, No. 3, pp. 416-418). Cambridge University Press.
[16] Ezratty, O. (2021). Understanding Quantum Technologies. le lab quantique.
[17] Kockum, A. F. (2014). Quantum optics with artificial atoms. Chalmers Tekniska Hogskola (Sweden).
[18] 江振瑞, 輕鬆學量子程式設計--從量子位元到量子演算法, 碁峰資
訊出版, ISBN: 786263242715, 2022.
[19] API Reference,Qiskit. [Online]. Available:
https://qiskit.org/documentation/apidoc/transpiler.html#scheduling-stage
[20] Simulators overview,Qiskit. [Online]. Available:
https://quantum-computing.ibm.com/lab/docs/iql/manage/simulator
[21] Fake Provider,Qiskit. [Online]. Available:
https://qiskit.org/documentation/apidoc/providers_fake_provider.html
[22] Cross, A. W., Bishop, L. S., Smolin, J. A., & Gambetta, J. M. (2017). Open quantum assembly language. arXiv preprint arXiv:1707.03429.
[23] Zhang, Y., Deng, H., Li, Q., Song, H., & Nie, L. (2019, July). Optimizing quantum programs against decoherence: Delaying qubits into quantum superposition. In 2019 International Symposium on Theoretical Aspects of Software Engineering (TASE) (pp. 184-191). IEEE.
[24] Tu, J. (2022). A Survey on the k-Path Vertex Cover Problem.
[25]Biggs, N., Lloyd, E. K., & Wilson, R. J. (1986). Graph Theory, 1736-1936. Oxford University Press.pp. 203–207
[26] Koenigs theorem graph. url :
https://commons.wikimedia.org/wiki/File:Koenigs-theorem-graph.svg, David Eppstein, Public domain, via Wikimedia Commons,access
[27] Hopcroft, J. E., & Karp, R. M. (1973). An n^5/2 algorithm for maximum matchings in bipartite graphs. SIAM Journal on computing, 2(4), 225-231.
[28] Introduction to Algorithms Lecture 21: Dynamic Programming IV. Available:
http://courses.csail.mit.edu/6.006/spring11/lectures/lec21.pdf
[29] Downey, R. G., Fellows, M. R., & Stege, U. (1999). Parameterized complexity: A framework for systematically confronting computational intractability. In Contemporary trends in discrete mathematics: From DIMACS and DIMATIA to the future (Vol. 49, pp. 49-99).
[30] Chen, J., Kanj, I. A., & Xia, G. (2010). Improved upper bounds for vertex cover. Theoretical Computer Science, 411(40-42), 3736-3756.
[31] Hüffner, F., Niedermeier, R., & Wernicke, S. (2008). Techniques for practical fixed-parameter algorithms. The Computer Journal, 51(1), 7-25.
[32] 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.
[33] Graph with all three colourings. url :
https://commons.wikimedia.org/wiki/File:Graph_with_all_three-colourings_2.svg, Arbor at English Wikipedia (PNG file), Booyabazooka at English Wikipedia (corrections + SVG conversion), CC BY-SA 3.0
[34] Lutze, D. (2021). Solving Chromatic Number with Quantum Search and Quantum Counting.
[35] Mukherjee, S. (2022). A grover search-based algorithm for the list coloring problem. IEEE Transactions on Quantum Engineering, 3, 1-8.
[36] 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.
[37] Graphical Game Example. url :
https://commons.wikimedia.org/wiki/File:GraphicalGameExample.png , shiraabr, CC BY-SA 3.0 <https://creativecommons.org/licenses/by-sa/3.0>, via Wikimedia Commons
[38] H. Abraham, AduOffei, R. Agarwal, I. Y. Akhalwaya, G. Aleksandrowicz, T. Alexander, M. Amy, E. Arbel, Arijit02, A. Asfaw, A. Avkhadiev, C. Azaustre, AzizNgoueya, A. Banerjee, A. Bansal, P. Barkoutsos, A. Barnawal, G. Barron, G. S. Barron, ..., and M. Cepulkovskis, “Qiskit: ˇ An open-source framework for quantum computing,” 2019.
[39] 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.
[40] 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.
[41] Complete Subgraph. url :
https://web.ntnu.edu.tw/~algo/CompleteGraph.html
[42] 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.
[43] Hamiltonian path. url :
https://commons.wikimedia.org/wiki/File:Hamiltonian_path.svg,Christoph Sommer, CC BY-SA 3.0 <http://creativecommons.org/licenses/by-sa/3.0/>, via Wikimedia Commons.
[44] 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.
[45] Salman, T., & Baram, Y. (2012). Quantum set intersection and its application to associative memory. The Journal of Machine Learning Research, 13(1), 3177-3206.
[46] Draper, T. G. (2000). Addition on a quantum computer. arXiv preprint quant-ph/0008033.
[47] Jakhodia, S., Singh, D., & Jajodia, B. (2022). Experimental Evaluation of QFT Adders on IBM QX Hardware. In Emerging Technologies for Computing, Communication and Smart Cities: Proceedings of ETCCS 2021 (pp. 419-435). Singapore: Springer Nature Singapore.
[48] Heidari, S., & Farzadnia, E. (2017). A novel quantum LSB-based steganography method using the Gray code for colored quantum images. Quantum Information Processing, 16(10), 1-28.
[49] Dijkstra, E. W. (2002). Cooperating sequential processes (pp. 65-138). Springer New York.
[50] Kaye, P., Laflamme, R., & Mosca, M. (2006). An introduction to quantum computing. OUP Oxford.
[51] Release Notes,Version History. [Online]. Available: https://qiskit.org/documentation/release_notes.html
[52] Cross, A. W., Bishop, L. S., Sheldon, S., Nation, P. D., & Gambetta, J. M. (2019). Validating quantum computers using randomized model circuits. Physical Review A, 100(3), 032328.
[53] Measuring Quantum Volume. [Online]. Available:
https://learn.qiskit.org/course/quantum-hardware/measuring-quantum-volume
[54] Quantum volume. [Online]. Available:
https://pennylane.ai/qml/demos/quantum_volume#cross
[55] Bennett, C. H., Bernstein, E., Brassard, G., & Vazirani, U. (1997). Strengths and weaknesses of quantum computing. SIAM journal on Computing, 26(5), 1510-1523.

指導教授

江振瑞(Jehn-Ruey Jiang)

審核日期

2023-7-25

推文