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

NCUIR > College of Electrical Engineering & Computer Science > Graduate Institute of Computer Science and Information Engineering > Electronic Thesis & Dissertation > Item 987654321/89953

Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/89953

Title:	用量子退火解決NP困難問題的QUBO分類;Classification of QUBO for Solving NP-hard Problem with Quantum Annealing
Authors:	朱俊瑋;CHU, CHUN-WEI
Contributors:	資訊工程學系
Keywords:	量子計算;量子退火;NP困難問題;易辛模型;二次無約束二元最佳化;quantum computing;quantum annealing;NP-hard problems;Ising model;quadratic unconstrained binary optimization (QUBO)
Date:	2022-08-16
Issue Date:	2022-10-04 12:05:45 (UTC+8)
Publisher:	國立中央大學
Abstract:	近年來量子計算（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.
Appears in Collections:	[Graduate Institute of Computer Science and Information Engineering] Electronic Thesis & Dissertation

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	35	View/Open

社群 sharing

Loading...