Skip navigation

DSpace

機構典藏 DSpace 系統致力於保存各式數位資料(如:文字、圖片、PDF)並使其易於取用。

點此認識 DSpace
DSpace logo
English
中文
  • 瀏覽論文
    • 校院系所
    • 出版年
    • 作者
    • 標題
    • 關鍵字
  • 搜尋 TDR
  • 授權 Q&A
    • 我的頁面
    • 接受 E-mail 通知
    • 編輯個人資料
  1. NTU Theses and Dissertations Repository
  2. 理學院
  3. 物理學系
請用此 Handle URI 來引用此文件: http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/88571
完整後設資料紀錄
DC 欄位值語言
dc.contributor.advisor管希聖zh_TW
dc.contributor.advisorHsi-Sheng Goanen
dc.contributor.author黃浩哲zh_TW
dc.contributor.authorHao-Che Huangen
dc.date.accessioned2023-08-15T16:53:11Z-
dc.date.available2023-11-09-
dc.date.copyright2023-08-15-
dc.date.issued2023-
dc.date.submitted2023-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.urihttp://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.abstractThe 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.provenanceSubmitted by admin ntu (admin@lib.ntu.edu.tw) on 2023-08-15T16:53:11Z
No. of bitstreams: 0
en
dc.description.provenanceMade available in DSpace on 2023-08-15T16:53:11Z (GMT). No. of bitstreams: 0en
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.isoen-
dc.title以模擬退火與模擬量子退火研究貨幣轉換的套利模型zh_TW
dc.titleStudy of Currency Conversion Arbitrage Models using Simulated Annealing and Simulated Quantum Annealingen
dc.typeThesis-
dc.date.schoolyear111-2-
dc.description.degree碩士-
dc.contributor.oralexamcommittee張慶瑞;洪士灏zh_TW
dc.contributor.oralexamcommitteeChing-Ruei Chang;Shi-Hao Hongen
dc.subject.keyword貨幣轉換問題 (CCP),套利,模擬量子退火 (SQA),二次無限制 二進制優化 (QUBO),pyQUBO,zh_TW
dc.subject.keywordCurrency Conversion Problem (CCP),Arbitrage,Simulated Quantum Annealing (SQA),Quadratic Unconstrained Binary Optimization (QUBO),pyQUBO,en
dc.relation.page84-
dc.identifier.doi10.6342/NTU202302568-
dc.rights.note未授權-
dc.date.accepted2023-08-07-
dc.contributor.author-college理學院-
dc.contributor.author-dept物理學系-
顯示於系所單位:物理學系

文件中的檔案:
檔案 大小格式 
ntu-111-2.pdf
  目前未授權公開取用
4.25 MBAdobe PDF
顯示文件簡單紀錄


系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。

社群連結
聯絡資訊
10617臺北市大安區羅斯福路四段1號
No.1 Sec.4, Roosevelt Rd., Taipei, Taiwan, R.O.C. 106
Tel: (02)33662353
Email: ntuetds@ntu.edu.tw
意見箱
相關連結
館藏目錄
國內圖書館整合查詢 MetaCat
臺大學術典藏 NTU Scholars
臺大圖書館數位典藏館
本站聲明
© NTU Library All Rights Reserved