使用格羅弗演算法解決漢米爾頓循環問題

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：23

、訪客IP：18.117.184.93

姓名

高子豪(Tzu-Hao Kao) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

使用格羅弗演算法解決漢米爾頓循環問題
(Solving Hamiltonian Cycle Problem with Grover′s Algorithm)

相關論文

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

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

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

摘要(中)

漢米爾頓循環(Hamiltonian Cycle)問題一直以來都是一個引人關注的難題，因為它具有廣泛的應用，例如 : 公車路線規劃和基因作圖(gene mapping)等等。在許多領域中，尋找漢米爾頓循環或漢米爾頓路徑的解答都具有重要性，然而，漢米爾頓循環問題屬於NP困難(NP-hard)問題，意味著在傳統的古典演算法中解決此問題需要龐大的時間和空間複雜度。隨著量子電腦的崛起，格羅弗演算法(Grover′s algorithm)的出現為解決漢米爾頓循環問題提供了新的可能性。因為格羅弗演算法在解決非結構搜尋(unstructured search)問題時相較於古典窮舉演算法具有平方量級的加速，因而引發本論文利用格羅弗演算法解決漢米爾頓循環問題的動機。
本論文旨在提出更高效且節省量子位元的量子線路，以使用格羅弗演算法解決任意圖的漢米爾頓循環問題。所提出的量子線路使用三個依照漢米爾頓循環限制而建立的格羅弗演算法神諭(oracle)將正確的解標記為負相位，然後使用相位增幅器(diffuser)提高正確解的測量機率，並透過量子計數(quantum counting)演算法估計出的神諭迭代次數來迭代神諭以求出漢米爾頓循環問題的解答。為了驗證量子線路的正確性，透過IBM量子電腦模擬器及ibmq_mumbai 量子電腦來模擬執行或執行量子線路。本論文比較了所提出的量子線路在不同轉譯(transpiling)最佳化等級及佈局方式在量子電腦中執行的優劣，接著與幾個解決漢米爾頓循環問題的古典演算法進行比較。比較結果顯示所提出的方法只需較少的量子位元就可以達到與古典演算法相近的時間複雜度。

摘要(英)

Hamiltonian cycle problem has long been a challenging and intriguing problem due to its wide range of applications, such as bus route planning and gene mapping. Finding solutions to hamiltonian cycles or paths is of great importance in various fields. However, hamiltonian cycle problem belongs to the class of NP-hard problems, which means that solving it using traditional classical algorithms requires significant time and space complexity. With the rise of quantum computers, the emergence of Grover′s algorithm has provided new possibilities for solving hamiltonian cycle problem. Grover′s algorithm offers a quadratic speedup compared to classical brute-force algorithms in solving unstructured search problems, which has motivated this paper to explore the application of Grover′s algorithm to tackle the Hamiltonian cycle problem. In this paper, we propose a more efficient and resource-saving quantum circuit for solving the Hamiltonian cycle problem of arbitrary graphs using Grover′s algorithm. The proposed quantum circuit utilizes three Grover’s algorithm oracles based on Hamiltonian cycle constraints to mark the correct solution with a negative phase, and then uses a phase amplifier (diffuser) to increase the measurement probability of the correct solution. The proposed approach further utilizes the quantum counting algorithm to estimate the number of iterations required for the oracle, in order to find the solution to the Hamiltonian cycle problem. To validate the correctness of the quantum circuit, simulations or executions are conducted using the IBM quantum computer simulator and ibmq_mumbai quantum computer.Furthermore, this paper compares the performance of the proposed quantum circuit when transpiling at different optimization levels and layout methods on quantum computers, and then compares it with several classical algorithms for solving hamiltonian cycle problem. The comparison results demonstrate that the proposed method achieves a comparable time complexity to classical algorithms with fewer quantum bits required.

關鍵字(中)

★ 格羅弗演算法
★ 漢米爾頓循環問題
★ 神諭
★ 量子線路
★ 量子電腦
★ 量子計數器

關鍵字(英)

★ Grover′s algorithm
★ hamiltonian cycle
★ oracle
★ quantum circuit
★ quantum computer
★ quantum counter

論文目次

中文摘要 i
Abstract ii
誌謝 iii
目錄 iv
圖目錄 vi
表目錄 viii
一、緒論 1
1.1研究背景與動機 1
1.2研究目的與方法 3
1.3論文架構 4
二、背景知識與相關研究 5
2.1 P、NP、NP-Hard、NP-Complete 問題 5
2.2漢米爾頓循環問題 5
2.3量子運算 6
2.3.1量子疊加 6
2.3.2狄拉克符號 7
2.3.3量子邏輯閘 8
2.4通用型量子電腦及其模擬器 10
2.5格羅弗演算法 11
2.6量子計數 14
2.7量子相關研究 15
2.7.1使用格羅弗演算法求解K-著色問題 15
2.7.2使用格羅弗演算法求解圖著色問題 16
2.7.3使用格羅弗演算法求解最大完全子圖問題 18
2.7.4使用格羅弗演算法求解列表著色問題 20
2.7.5使用格羅弗演算法找出在圖形博弈中的納許均衡點 21
2.7.6使用格羅弗演算法求解最大可滿足性問題 22
2.7.7使用格羅弗演算法求解漢米爾頓循環問題 23
2.7.8使用格羅弗演算法進行藥物專利分析 24
2.7.9量子計數器 25
2.7.10量子搜尋的嚴格界限 25
2.8古典相關研究 26
2.8.1使用動態規劃演算法解決漢米爾頓循環問題 26
2.8.2使用奇偶校驗法解決漢米爾頓循環問題 27
2.8.3使用改良Eppstein’s演算法解決漢米爾頓循環問題 27
2.8.4使用蒙特卡洛法解決漢米爾頓循環問題 28
三、研究方法 29
3.1範圍計數器 29
3.2研究方法介紹 30
3.2.1初始化量子位元 31
3.2.2建立神諭 32
3.2.2.1使用三個限制建立神諭 32
3.2.2.2相位回擊 35
3.2.2.3建立反向神諭 35
3.2.3振幅放大 38
3.3格羅弗演算法迭代次數計算 39
四、實驗結果與討論 41
4.1實驗環境與設備 41
4.2實驗結果 42
4.2.1使用Aer模擬器模擬結果 42
4.2.2使用Aer模擬器計算神諭迭代次數 45
4.2.3使用量子電腦執行所提出的方法 47
4.3相關研究文獻比較 48
4.4模擬器及量子電腦實驗結果與心得 49
五、結論與未來展望 51
參考文獻 52
附錄 55

參考文獻

[1]Graph Algorithms in Bioinformatics Retrieved March 1, 2023, from https://cseweb.ucsd.edu/classes/wi12/cse282-a/Lecture06_Ch08_GraphsDNAseq.pdf
[2]Karp, R. M. (1972). Reducibility among combinatorial problems. In Complexity of computer computations (pp. 85-103). Springer, Boston, MA.
[3]Preskill, J. (2018). Quantum computing in the NISQ era and beyond. Quantum, 2, 79.
[4]Rigetti Computing, Inc. (2021, March 10). Rigetti investor presentation. Retrieved February 6, 2023, from https://investors.rigetti.com/node/7141/html
[5]International Business Machines Corporation(n.d.)The IBM Quantum Development Roadmap. Retrieved February 6, 2023, from https://www.ibm.com/quantum/roadmap
[6]科技產業資訊室 (iKnow) (2021年5月14日)。主要16國家量子科技政策預算超過246億美元。2023年2月6日，取自:https://iknow.stpi.narl.org.tw/Post/Read.aspx?PostID=17799
[7]Shor, P. W. (1994, November). Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th annual symposium on foundations of computer science (pp. 124-134). Ieee.
[8]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).
[9]Wekipedia：Hamiltonian path problem. Retrieved March 1, 2023, from https://en.wikipedia.org/wiki/Hamiltonian_path_problem
[10]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.
[11]Building a useful quantum computer Retrieved Jun 7, 2023, from https://quantumai.google/qecmilestone
[12]IBM Qiskit Retrieved Jun 7, 2023, from https://qiskit.org/
[13]Baldwin, C. H., Mayer, K., Brown, N. C., Ryan-Anderson, C., & Hayes, D. (2022). Re-examining the quantum volume test: Ideal distributions, compiler optimizations, confidence intervals, and scalable resource estimations. Quantum, 6, 707.
[14]Transpiler Passes and Pass Manager Retrieved Jun 7, 2023, from https://github.com/Qiskit/qiskit-tutorials/blob/master/tutorials/circuits_advanced/04_transpiler_passes_and_passmanager.ipynb
[15]Murali, P., Baker, J. M., Javadi-Abhari, A., Chong, F. T., & Martonosi, M. (2019, April). Noise-adaptive compiler mappings for noisy intermediate-scale quantum computers. In Proceedings of the twenty-fourth international conference on architectural support for programming languages and operating systems (pp. 1015-1029).
[16]Li, G., Ding, Y., & Xie, Y. (2019, April). Tackling the qubit mapping problem for NISQ-era quantum devices. In Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems (pp. 1001-1014).
[17]AerSimulator Retrieved Jun 7, 2023, from https://qiskit.org/ecosystem/aer/stubs/qiskit_aer.AerSimulator.html
[18]江振瑞(2022)。輕鬆學量子程式設計 -- 從量子位元到量子演算法。桃園市:碁峰資訊。
[19]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.
[20]Fawly(2021, June) Wekipedia：Grover′s algorithm. Retrieved March 1, 2023,from https://en.wikipedia.org/wiki/Grover%27s_algorithm#/media/File:Grover′s_algorithm_circuit.svg
[21]Nielsen, M.A. and Chuang, I.L. Quantum computation and quantum information. Cambridge University Press, 2000. Chapter 6.
[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. Master Thesis, California Polytechnic State University.
[24]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.
[25]Mukherjee, S. (2022). A grover search-based algorithm for the list coloring problem. IEEE Transactions on Quantum Engineering, 3, 1-8.
[26]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.
[27]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.
[28]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.
[29]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.
[30]Heidari, S., & Farzadnia, E. (2017). A novel quantum LSB-based steganography method using the Gray code for coloured quantum images. Quantum Information Processing, 16(10), 242.
[31]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.
[32]Held, M., & Karp, R. M. (1962). A dynamic programming approach to sequencing problems. Journal of the Society for Industrial and Applied mathematics, 10(1), 196-210.
[33]Björklund, A., & Husfeldt, T. (2013, October). The parity of directed Hamiltonian cycles. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science (pp. 727-735). IEEE.
[34]Iwama, K., & Nakashima, T. (2007, July). An improved exact algorithm for cubic graph TSP. In International Computing and Combinatorics Conference (pp. 108-117). Springer, Berlin, Heidelberg.
[35]Eppstein, D. (2007). The traveling salesman problem for cubic graphs. J. Graph Algorithms Appl., 11(1), 61-81.
[36]Bjorklund, A. (2014). Determinant sums for undirected hamiltonicity. SIAM Journal on Computing, 43(1), 280-299.
[37]Nation, P., & Johnson, B. (2021). How to measure and reset a qubit in the middle of a circuit execution. IBM Research Blog, 11.
[38]Mastriani, M. (2019). Non-ambiguity quantum teleportation protocol. arXiv preprint arXiv:2001.05832.
[39]IBM Quantum, https://quantum-computing.ibm.com/ (accessed May
26, 2023).
[40]Mao, Y., Shresthamali, S., & Kondo, M. (2023). Quantum Circuit Fidelity Improvement with Long Short-Term Memory Networks. arXiv preprint arXiv:2303.17523.

指導教授

江振瑞(Jehn-Ruey Jiang)

審核日期

2023-7-25

推文