以模擬退火與模擬量子退火研究貨幣轉換的套利模型

Abstract

貨幣轉換問題（CCP）是一個容易理解的套利模型，然而傳統電腦對於計算此問題所需的高時間複雜性，使人們即使容易理解其性質，也無法有效進行套利，雖然使用窮舉法進行計算可以找出所有可能的解，但實際上還需要考慮計算速度和成本。最近在Ising模型解決方案上的發展，如量子退火、數字退火和模擬量子退火系統呈現了許多有趣的特徵，可能比傳統的電腦更有效地解決二次無限制二進制優化（QUBO）問題，例如，最大切割問題、旅行推銷員問題等。 因此，在這篇論文中，我們將CCP轉換為兩種可行的QUBO模型，並加入懲罰項進行模型建構、模型修改和參數優化。這兩種模型稱為直線型和邊長型模型，是對過往文獻中的模型進行修正的版本。每個模型中的懲罰項來自於將CCP強加的約束或條件轉換成優化的成本（目標）函數。然後我們將QUBO問題轉換為尋找Ising Hamiltonian基態能量的問題，我們使用Python模擬退火（SA）陣列求解器pyQUBO，以及國立臺灣大學開發的模擬量子退火（SQA）機器，計算CCP的兩個QUBO問題，並研究不同退火機器解決問題的速度。我們也研究了懲罰項的係數對於CCP兩種模型的解決品質、正確率和時間的影響。我們使用SA和SQA以及傳統的窮舉方法，對邊長型CCP模型進行多貨幣測試，並顯示SQA在解決優化時間上優於SA和傳統的窮舉方法。最後，我們提出我們的結論，並給出未來研究的展望和可能的方向。

The currency conversion problem (CCP) is an easily understood arbitrage model. However, due to the high time complexity required by classical computers to calculate this problem, one, despite understanding its nature easily, cannot effectively arbitrage. Using brute force method for calculations to exhaust all possible solutions would require computational speed and cost considerations in practice. Recent development in Ising model solvers, such as quantum annealing, digital annealing, and simulated quantum annealing systems presents many interesting features that may solve quadratic unconstrained binary optimization (QUBO) problems, e.g., the max cut problem, traveling salesman problem, etc. more efficiently than classical computers. Thus, in this thesis, we formulate the CCP into two viable models in QUBO form with penalty terms, and carry out model construction, model modification, and parameter optimization. The two models called straight-line base and edge base models, are correctly revised version from the model in the literature. The penalty terms in each model come from converting the constraints or conditions imposed by the CCP into the cost (objective) function for optimization. We then transform the QUBO problems into problems of finding the ground state energy of an Ising Hamiltonian. We calculate the two QUBO problems of of the CCP using pyQUBO, a Python simulated annealing (SA) array solver, and the simulated quantum annealing (SQA) machine developed at the National Taiwan University, and study the speeds of different annealing machines to solve the problems. We also investigate the values of the coefficients of the penalty terms on the solution quality, accuracy and time for the two models of the CCP. We test the edge base CCP model with multi-currencies using SA and SQA and classical exhaustive method, and show that SQA outperforms SA and classical exhaustive method in solution optimization time. Finally, we present our conclusion and give prospects and possible directions for future research.