用量子退火解決NP困難問題的QUBO分類

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：23

、訪客IP：3.133.152.151

姓名

朱俊瑋(CHUN-WEI CHU) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

用量子退火解決NP困難問題的QUBO分類
(Classification of QUBO for Solving NP-hard Problem with Quantum Annealing)

相關論文

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

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

近年來量子計算（quantum computing）技術蓬勃發展的趨勢日漸明顯，其強大的運算潛能逐漸受到重視，並在諸多領域有突破性的應用，涵蓋金融（finance）、製藥（pharmaceutical）、物流（logistics）、通訊（communication）等各種領域。世界各地許多公司如 D-Wave、IBM 及 Google …等也都爭相積極投入量子計算技術的研發。可預期的，新興的量子計算機，在不久的將來可以解決傳統古典計算機無法在可行時間內解決的大規模複雜問題，達成量子霸權（quantum supremacy）。本論文聚焦於在 D-Wave 量子退火機（quantum annealer）上使用量子退火（quantum annealing）演算法解決 NP 困難（NP-hard）問題。要在D-Wave量子退火機解決問題，我們要先將問題表述為目標函數（objective function），目標函數需為易辛模型（Ising model）或是二次無約束二元最佳化（quadratic unconstrained binary optimization, QUBO）的形式，其中目標函數的最小值代表欲求問題的最佳解。透過Ising模型或是 QUBO 可以將問題嵌入量子處理器（quantum process unit, QPU）進行量子退火，最後再進行採樣，讀取代表問題解決方案的低能量狀態。本論文針對量子退火演算法的 QUBO 進行分類，依照演算法將問題表述為目標函數後的不同形式將 QUBO 分為四個類別。每個 QUBO 類別都舉兩個以上的量子退火演算法為例解決常見的 NP 困難問題。本論文並採用公開資料集的問題實例進行實驗，比較量子退火演算法與在古典計算機上執行的古典演算法的效能。結果顯示，使用量子退火演算法解決 NP 困難問題，在解決問題時間及達成的解答品質方面是具有競爭力的。最後，本論文綜合比較四個類別QUBO的各種特性，並給出各類別的使用建議。

摘要(英)

In recent years, the booming development trend of quantum computing has become more and more obvious, and its powerful computing potential has gradually attracted much attention. Quantum computing has many potential applications in different fields, covering finance, pharmacy, logistics, and communications. Many companies around the world, such as D-Wave, IBM, and Google, are actively investing in the research and development of quantum computing technology. It is expected that emerging quantum computers can soon solve large-scale and complex problems that traditional classical computers cannot solve within a feasible time, and achieve “quantum supremacy”. This thesis focuses on solving NP-hard problems with quantum annealing algorithms running on the D-Wave quantum annealer. The quantum annealing algorithm formulates a problem as an objective function, which is an Ising model or a quadratic unconstrained binary optimization (QUBO) formula. The minimum value of the objective function corresponds to the optimal solution to the problem. Through the Ising model or the QUBO formula, the problem is embedded into a quantum process unit (QPU) for quantum annealing. The sampling procedure is employed to read the low-energy state that corresponds to the solution to the problem. This thesis classifies QUBOs of quantum annealing algorithms into four categories. Two quantum annealing algorithms solving specific NP-hard problems are demonstrated as examples for each QUBO category. Public datasets of NP-hard problems are used to evaluate and compare the performance of quantum annealing algorithms and classical algorithms running on classical computers. The comparison results show that solving NP-hard problems with quantum annealing algorithms using QUBOs is competitive in terms of the time to the solution and the quality of the solution. Finally, this thesis comprehensively compares various characteristics of the four categories of QUBOs, and gives suggestions for the use of each of them.

關鍵字(中)

★ 量子計算
★ 量子退火
★ NP困難問題
★ 易辛模型
★ 二次無約束二元最佳化

關鍵字(英)

★ quantum computing
★ quantum annealing
★ NP-hard problems
★ Ising model
★ quadratic unconstrained binary optimization (QUBO)

論文目次

中文摘要 i
Abstract ii
目錄 iii
圖目錄 iv
表目錄 v
一、緒論 1
1.1 研究背景與動機 1
1.2 研究目的與方法 2
1.3 論文架構 4
二、背景知識 5
2.1 P、NP、NP-hard、NP-complete 5
2.2 量子現象 6
2.2.1 量子疊加與量子糾纏 6
2.2.2 量子穿隧 8
2.3 QUBO 和 Ising 模型 8
2.4 量子退火演算法 10
2.4.1 量子退火硬體 10
2.4.2 量子退火流程 11
三、研究方法 16
3.1 研究方法介紹 16
3.2 8 個 NP 困難問題 17
四、實驗結果 21
4.1 實驗環境 21
4.2 實驗結果與比較 22
五、結論與未來展望 32
參考文獻 33

參考文獻

[1]Mamta. (2014). History of P versus NP Problem. International Journal of Scientific & Engineering Research, Volume 5(Issue 4).
[2]Fortnow, L., & Homer, S. (2003). A short history of computational complexity. Bulletin of the EATCS, 80(01), 2003.
[3]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.
[4]量子革命來了！未來科技生活即將翻天覆地。2022年6月22日，取自
https://www.sancode.org.tw/activities_info.php?type=3&nid=75
[5]A Preview of Bristlecone, Google’s New Quantum Processor。2022年6月22日，取自
https://ai.googleblog.com/2018/03/a-preview-of-bristlecone-googles-new.html
[6]量子電腦是什麼？一文詳解讓Google、Intel、IBM與微軟都趨之若鶩的關鍵技術。2022年6月22日，取自
https://www.bnext.com.tw/article/54171/quantum-computer-google-intel-ibm
[7]Dean, W. (2015). Computational complexity theory.
[8]Knuth, D. E. (2014). Art of computer programming, volume 2: Seminumerical algorithms. Addison-Wesley Professional.
[9]Floyd, R. W. (1967). Nondeterministic algorithms. Journal of the ACM (JACM), 14(4), 636-644.
[10]M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-completeness. W. H. Freeman, New York, 1979.
[11]ID 141481955 © Nutkinsj | Dreamstime.com
[12]Schrödinger, E. (1935, October). Discussion of probability relations between separated systems. In Mathematical Proceedings of the Cambridge Philosophical Society (Vol. 31, No. 4, pp. 555-563). Cambridge University Press.
[13]What is quantum entanglement?。2022年6月22日，取自
https://www.livescience.com/what-is-quantum-entanglement.html
[14]Razavy, M. (2013). Quantum theory of tunneling. World Scientific.
[15]Quantum-Mechanical Tunneling。2022年6月22日，取自
https://chem.libretexts.org/Courses/University_of_California_Davis/UCD_Chem_107B%3A_Physical_Chemistry_for_Life_Scientists/Chapters/4%3A_Quantum_Theory/4.09%3A_Quantum-Mechanical_Tunneling,CC BY-NC 4.0; Ümit Kaya
[16]Tavares, G. (2008). New algorithms for Quadratic Unconstrained Binary Optimization (QUBO) with applications in engineering and social sciences. Rutgers The State University of New Jersey-New Brunswick.
[17]Glover, F., Kochenberger, G., & Du, Y. (2018). A tutorial on formulating and using QUBO models. arXiv preprint arXiv:1811.11538.
[18]Glover, F., Kochenberger, G., & Du, Y. (2018). A tutorial on formulating and using QUBO models. arXiv preprint arXiv:1811.11538.
[19]Wald, S. S. (2017). Thermalisation and Relaxation of Quantum Systems (Doctoral dissertation, Université de Lorraine).
[20]Yarkoni, S., Raponi, E., Schmitt, S., & Bäck, T. (2021). Quantum Annealing for Industry Applications: Introduction and Review. arXiv preprint arXiv:2112.07491.
[21]維基百科：退火。2022年6月22日，取自
https://zh.m.wikipedia.org/zh-tw/%E9%80%80%E7%81%AB
[22]Lucas, A. (2014). Ising formulations of many NP problems. Frontiers in physics, 5.
[23]Fang, Y. L., & Warburton, P. A. (2020). Minimizing minor embedding energy: an application in quantum annealing. Quantum Information Processing, 19(7), 1-29.
[24]D-Wave:What is Quantum Annealing?。2022年6月22日，取自
https://docs.dwavesys.com/docs/latest/c_gs_2.html
[25]Venturelli, D., Marchand, D. J., & Rojo, G. (2015). Quantum annealing implementation of job-shop scheduling. arXiv preprint arXiv:1506.08479.
[26]SUBSET_SUM:Data for the Subset Sum Problem。2022年6月22日，取自
https://people.sc.fsu.edu/~jburkardt/datasets/subset_sum/subset_sum.html
[27]Helmberg, C., & Rendl, F. (1998). Solving quadratic (0, 1)-problems by semidefinite programs and cutting planes. Mathematical programming, 82(3), 291-315.
[28]Meta-Analytics:Max Cut Benchmarks。2022年6月22日，取自
http://meta-analytics.net/index.php/max-cut-benchmarks/
[29]NETWORK REPOSITORY A SCIENTIFIC NETWORK DATA REPOSITORY WITH INTERACTIVE VISUALIZATION AND MINING TOOLS。2022年6月22日，取自https://networkrepository.com/index.php
[30]Wang, L., Hu, S., Li, M., & Zhou, J. (2019). An exact algorithm for minimum vertex cover problem. Mathematics, 7(7), 603.
[31]Mahfouz, K., Ali, S., Al-Betar, M. A., & Awadallah, M. A. (2021, September). Solving 0–1 Knapsack Problems Using Sine-Cosine Algorithm. In 2021 Palestinian International Conference on Information and Communication Technology (PICICT) (pp. 45-51). IEEE.
[32]Meringer, M. (1999). Fast generation of regular graphs and construction of cages. Journal of Graph Theory, 30(2), 137-146.
[33]Torralbo Lezana, M. (2021). A Python implementation of the Snakes and Ladders for solving the Hamiltonian cycle problem using a graphical interface. 2022年6月22日，取自
https://addi.ehu.es/handle/10810/53293
[34]Graph Coloring Instances。2022年6月22日，取自https://mat.tepper.cmu.edu/COLOR/instances.html#XXDSJ
[35]Dokeroglu, T., & Sevinc, E. (2021). Memetic Teaching–Learning-Based Optimization algorithms for large graph coloring problems. Engineering Applications of Artificial Intelligence, 102, 104282.
[36]Reinhelt, G. (2014). {TSPLIB}: a library of sample instances for the TSP (and related problems) from various sources and of various types. URL: http://comopt. ifi. uniheidelberg. de/software/TSPLIB95.
[37]Welcome to OR-Library。2022年6月22日，取自http://people.brunel.ac.uk/~mastjjb/jeb/info.html
[38]Zbinden, S., Bärtschi, A., Djidjev, H., & Eidenbenz, S. (2020, June). Embedding algorithms for quantum annealers with chimera and pegasus connection topologies. In International Conference on High Performance Computing (pp. 187-206). Springer, Cham.
[39]Okada, S., Ohzeki, M., Terabe, M., & Taguchi, S. (2019). Improving solutions by embedding larger subproblems in a D-Wave quantum annealer. Scientific reports, 9(1), 1-10.
[40]Choi, V. (2008). Minor-embedding in adiabatic quantum computation: I. The parameter setting problem. Quantum Information Processing, 7(5), 193-209.
[41]The D-Wave 2000Q™ Quantum Computer。2022年6月22日，取自
https://dwavejapan.com/app/uploads/2019/10/D-Wave-2000Q-Tech-Collateral_1029F.pdf
[42]Bass, G., Henderson, M., Heath, J., & Dulny, J. (2021). Optimizing the optimizer: decomposition techniques for quantum annealing. Quantum Machine Intelligence, 3(1), 1-14.
[43]Pelofske, E., Hahn, G., & Djidjev, H. N. (2022). Solving Larger Optimization Problems Using Parallel Quantum Annealing. arXiv preprint arXiv:2205.12165.
[44]Amazon Braket Pricing。2022年6月22日，取自https://aws.amazon.com/tw/braket/pricing/

指導教授

江振瑞(Jehn-Ruey Jiang)

審核日期

2022-8-16

推文