請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/88571
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 管希聖 | zh_TW |
dc.contributor.advisor | Hsi-Sheng Goan | en |
dc.contributor.author | 黃浩哲 | zh_TW |
dc.contributor.author | Hao-Che Huang | en |
dc.date.accessioned | 2023-08-15T16:53:11Z | - |
dc.date.available | 2023-11-09 | - |
dc.date.copyright | 2023-08-15 | - |
dc.date.issued | 2023 | - |
dc.date.submitted | 2023-08-02 | - |
dc.identifier.citation | [1] Liu, Y. (1991). A Study of Spot Foreign Exchange Rates in Terms of Arbitrager’s Views.
[2] Schrijver, Alexander (2003). Combinatorial Optimization: Polyhedra and Efficiency. Algorithms and Combinatorics. Vol. 24. Springer. ISBN 9783540443896. [3] Lucas, A. "Ising formulations of many NP problems," Front. Phys. Vol. 2 (2014)p.4, [10.3389/fphy.2014.00005] [4] How Quantum Annealing Works in D-Wave QPUs. (n.d.). D Wave System. https://docs.dwavesys.com/docs/latest/c_gs_2.html [5] Aramon, M., Rosenberg, gili, & Valiante, E. (2019). Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer. Front. Phys. [6] Chung, Y. (2022, May 20). Accelerating Simulated Quantum Annealing with GPU and Tensor Cores. https://yi-huaaa.github.io/2022/05/10/Accelerating%20Simulated%20Quantum%20Annealing%20with%20GPU%20and%20Tensor%20Cores/ [7] H. M. Waidyasooriya and M. Hariyama, "A GPU-Based Quantum Annealing Simulator for Fully-Connected Ising Models Utilizing Spatial and Temporal Parallelism," in IEEE Access, vol. 8, pp. 67929-67939, 2020, doi: 10.1109/ACCESS.2020.2985699 [8] Index of /~yyye/Yyye/Gset. (2003, September 11). Gset. https://web.stanford.edu/~yyye/yyye/Gset/ [9] Floating Point and IEEE 754 Compliance for NVIDIA GPUs. (2023, April 19). CUDA Floating-Point Index. https://docs.nvidia.com/cuda/floating-point/index.html [10] Let’s Get Practical*: D-Wave Details Product Expansion & Cross Platform Roadmap. (2021, October 5). DWAVE. https://www.dwavesys.com/company/newsroom/press-release/let-s-get-practical-d-wave-details-product-expansion-cross-platform-roadmap/ [11] Rosenberg, G. (2016). Finding Optimal Arbitrage Opportunities Using a Quantum Annealer. 1Qbit. [12] Soheil, M., & Tseng, M. c. (2023). Spot Arbitrage in FX Market and Algorithmic Trading: Speed Is Not of the Essence. World Scientific. https://doi.org/10.1142/S2382626620500112 [13] Brooks, M. (2019). Beyond Quantum Supremacy: The Hunt for Useful Quantum Computers. Nature, 574. https://doi.org/https://doi.org/10.1038/d41586-019-02936-3 [14] Pathria, P. k., & Beale, P. d. (2017). Statistical Mechanics (3rd ed.). 高等教育出版社. [15] Aramon, M., Rosenberg, G., & Valiante, E. (2022). Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer. Frontiers in Physics. https://doi.org/10.3389/fphy.2019.00048 [16] Mega international commercial bank (Ed.). 外幣匯率. 即期/現金匯率. https://www.megabank.com.tw/personal/foreign-service/forex [17] Liu, C. TRIANGULAR ARBITRAGE STRATEGY USED IN THE EMPIRICAL STUDY OF INTELLIGENT AUTOMATED FOREX TRADING. [18] Mahajan, P., Jadhav, V., & Salian, Y. (2020). Currency Arbitrage Detection. International. [19] Chung, YH., Shih, CJ., Hung, SH. (2022). Accelerating Simulated Quantum Annealing with GPU and Tensor Cores. In: Varbanescu, AL., Bhatele, A., Luszczek, P., Marc, B. (eds) High Performance Computing. ISC High Performance 2022. Lecture Notes in Computer Science, vol 13289. Springer, Cham. https://doi.org/10.1007/978-3-031-07312-0_9 [20] R. Bellman, Dynamic Programming, Princeton University Press, 1957 R. Bellman, The Theory of Dynamic Programming, Bull. Amer. Math. Soc., 60, 503-515 (1954) | - |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/88571 | - |
dc.description.abstract | 貨幣轉換問題(CCP)是一個容易理解的套利模型,然而傳統電腦對於計算此問題所需的高時間複雜性,使人們即使容易理解其性質,也無法有效進行套利,雖然使用窮舉法進行計算可以找出所有可能的解,但實際上還需要考慮計算速度和成本。最近在Ising模型解決方案上的發展,如量子退火、數字退火和模擬量子退火系統呈現了許多有趣的特徵,可能比傳統的電腦更有效地解決二次無限制二進制優化(QUBO)問題,例如,最大切割問題、旅行推銷員問題等。
因此,在這篇論文中,我們將CCP轉換為兩種可行的QUBO模型,並加入懲罰項進行模型建構、模型修改和參數優化。這兩種模型稱為直線型和邊長型模型,是對過往文獻中的模型進行修正的版本。每個模型中的懲罰項來自於將CCP強加的約束或條件轉換成優化的成本(目標)函數。然後我們將QUBO問題轉換為尋找Ising Hamiltonian基態能量的問題,我們使用Python模擬退火(SA)陣列求解器pyQUBO,以及國立臺灣大學開發的模擬量子退火(SQA)機器,計算CCP的兩個QUBO問題,並研究不同退火機器解決問題的速度。我們也研究了懲罰項的係數對於CCP兩種模型的解決品質、正確率和時間的影響。我們使用SA和SQA以及傳統的窮舉方法,對邊長型CCP模型進行多貨幣測試,並顯示SQA在解決優化時間上優於SA和傳統的窮舉方法。最後,我們提出我們的結論,並給出未來研究的展望和可能的方向。 | zh_TW |
dc.description.abstract | 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. | en |
dc.description.provenance | Submitted by admin ntu (admin@lib.ntu.edu.tw) on 2023-08-15T16:53:11Z No. of bitstreams: 0 | en |
dc.description.provenance | Made available in DSpace on 2023-08-15T16:53:11Z (GMT). No. of bitstreams: 0 | en |
dc.description.tableofcontents | 致謝 i
摘要 ii ABSTRACT iii CONTENTS v LIST OF FIGURES vii LIST OF TABLES xii LIST OF ALGORITHMS xiv Chapter 1 Introduction 1 Chapter 2 QUBO Model and Ising Model in SA and SQA 4 2.1 Introduction to the Annealing Machine 4 2.2 Introduction to the Ising Model and QUBO Model 10 2.2.1 Introduction to the Ising Model 10 2.2.2 Introduction to the QUBO Model 12 2.3 Introduction to the Constraint by using Penalty Term 13 2.3.1 Compare the Constraint Method and the Penalty Term Method 13 2.3.2 Application Scenarios 14 Chapter 3 Transform the QUBO Model to the Ising Model 19 3.1 The Structure of the QUBO Model 19 3.2 The structure of the Ising model 20 3.3 Conversion the QUBO Model to the Ising Model 23 Chapter 4 The CCPs in the QUBO models 26 4.1 Straight-line base CCP model 26 4.2 Edge base CCP model 35 4.3 Penalty Tuning 41 4.3.1 Penalty Tuning for the Straight-line base CCP Model 41 4.3.2 Penalty Tuning for the Edge base CCP Model 45 Chapter 5 Results and Discussion 50 5.1 Experimental Data 50 5.1.1 Straight-line base CCP Model Testing Using SA 50 5.1.2 Straight-line base CCP Model Testing Using SQA 55 5.1.3 Edge base CCP Model Testing Using SA 55 5.1.4 Edge base CCP Model Testing Using SQA 62 5.1.5 Result After Penalty Selection 68 5.2 Comparing Time Spent on SA, SQA, and Classical Exhaustive Method 70 5.3 Real-World Currency Scenarios 75 Chapter 6 Conclusion 78 Appendix A Automatic Python program for QUBO to Ising (for SQA) 80 BIBLIOGRAPHY 82 | - |
dc.language.iso | en | - |
dc.title | 以模擬退火與模擬量子退火研究貨幣轉換的套利模型 | zh_TW |
dc.title | Study of Currency Conversion Arbitrage Models using Simulated Annealing and Simulated Quantum Annealing | en |
dc.type | Thesis | - |
dc.date.schoolyear | 111-2 | - |
dc.description.degree | 碩士 | - |
dc.contributor.oralexamcommittee | 張慶瑞;洪士灏 | zh_TW |
dc.contributor.oralexamcommittee | Ching-Ruei Chang;Shi-Hao Hong | en |
dc.subject.keyword | 貨幣轉換問題 (CCP),套利,模擬量子退火 (SQA),二次無限制 二進制優化 (QUBO),pyQUBO, | zh_TW |
dc.subject.keyword | Currency Conversion Problem (CCP),Arbitrage,Simulated Quantum Annealing (SQA),Quadratic Unconstrained Binary Optimization (QUBO),pyQUBO, | en |
dc.relation.page | 84 | - |
dc.identifier.doi | 10.6342/NTU202302568 | - |
dc.rights.note | 未授權 | - |
dc.date.accepted | 2023-08-07 | - |
dc.contributor.author-college | 理學院 | - |
dc.contributor.author-dept | 物理學系 | - |
顯示於系所單位: | 物理學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-111-2.pdf 目前未授權公開取用 | 4.25 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。