量子退火算法在貨幣交易市場的應用研究

葉永金 吳永政 蘭冰 汪士

摘要：近年來，量子計算飛速發展，對眾多行業，尤其是金融業產生變革性影響，外匯交易市場將是第一波受到量子科技沖擊的金融市場。我們提出一種量子套利優化方法，將貨幣交換轉化為二次無約束二值優化（QUBO）問題，利用量子退火算法，求解哈密頓量的最低能態，實現高效的套利分析。傳統的套利算法求解最佳套利交易路徑屬于NP難問題，引入量子退火算法之后，極大地降低了計算的時間復雜度，為這一類問題的解決提供了一條可行的路徑。該算法不僅可以得到最優解，還能求出所有有利可圖的交易路徑，讓交易者在不同交易路徑之間依據實際操作需要進行靈活選擇。

關鍵詞：套利；退火算法；量子計算

引 言

中共中央政治局于2020年10月16日下午就量子科技研究和應用前景舉行第二十四次集體學習。中共中央總書記習近平在主持學習時強調，“當今世界正經歷百年未有之大變局，科技創新是其中一個關鍵變量。要充分認識推動量子科技發展的重要性和緊迫性，加強量子科技發展戰略謀劃和系統布局，把握大趨勢，下好先手棋”。隨著量子科技時代的到來，量子計算、量子保密通信、量子測量等快速發展，其中量子計算以其超強的并行計算能力，不斷突破傳統計算的瓶頸，有望引領下一代科技革命。近幾年，國內外量子計算得到快速發展，量子算法作為量子計算的應用方向，涉及各行各業，其中就包括在金融市場上的應用。本文聚焦量子算法在金融市場的創新研究，著眼量子科技的大趨勢，下好量子金融的先手棋。

量子金融概述

金融市場每天產生海量的交易數據，如何快速而有效地處理，傳統計算面臨巨大挑戰。量子計算以量子比特作為基礎，利用量子比特的糾纏與疊加特性，表現出超強的并行計算能力，在一些特定問題的求解過程中，有巨大的加速效果。比如Shor算法在大數的質因數分解過程中的指數級加速[1]，Grover提出的查找算法，在無序集合查找問題上相對于經典算法的平方級加速[2]。于是人們希望將量子計算應用于金融領域，量子金融的概念產生，即量子計算在金融領域的應用。目前，量子計算在金融領域的應用主要集中于金融交易、風險評估和金融工程幾個方向。量子計算在金融交易領域的應用為通過引入量子計算指導金融交易，主要包括證券投資組合優化、股票價格預測以及本文討論的貨幣市場套利交易等。量子近似優化算法可以應用于證券投資組合，量子蒙特卡洛算法可以應用于股票價格預測，本文將量子退火算法應用于貨幣市場的套利交易。在風險評估領域主要是量子計算應用于信用評分和欺詐檢測。有Daniel J.Egger提出信用評分的量子算法，Nouhaila Innan提出的量子圖神經網絡應用于欺詐檢測[3]。量子金融工程主要指的是量子算法應用于金融衍生品的定價，其中包括期權定價等，量子蒙特卡洛算法也可以在這個方向發揮作用。

通過量子算法與金融市場的連接，將傳統的金融問題，轉化為特定的量子算法問題，利用量子計算機的特殊優勢，突破傳統計算的瓶頸，對于金融市場上的股票價格預測、投資優化組合、信用評估以及我們提出的外匯市場套利等金融問題，提供快速有效的解決方案。

量子退火算法與二次無約束二值優化問題（QUBO）

組合優化是在離散域或可簡化為離散域內計算函數的最大或最小值。日常生活中存在各種組合優化問題，例如商旅問題、交通流量、班次規劃等問題。此類問題通常包含非常多的可能解決方案，使得詳盡的搜索變得棘手，因此需要尋求更加快速高效的計算方法。

為了克服這種計算限制，研究人員開發了一種被稱為伊辛機的新型計算技術。伊辛機是求解伊辛模型問題的機器，即將特定的數學問題轉化為伊辛模型的結構，構建該問題的哈密頓量，然后引入量子退火原理，讓哈密頓量以絕熱演化的方式，讓系統從激發態逐漸向基態演化，尋找數學問題的最優解。許多利用伊辛機的研究已在各個領域進行：投資組合優化[4]、交通流量優化[5]、電子商務網站的項目列表優化[6]和材料設計[7]。本文將伊辛機的應用擴展到貨幣交易市場中的套利分析。

很多組合優化問題可以在數學上轉化為伊辛模型或者QUBO的結構，利用伊辛機進行快速求解。伊辛模型和QUBO是通過圖G（V， E）進行定義，其中V表示無向圖頂點，E表示邊。圖1就是貨幣套利交易的圖G（V， E）簡單展示，節點（V）表示幣種，邊（E）表示幣種之間的交易匯率，由于2個幣種交易匯率不對稱，所以該圖是有向圖。

伊辛模型

在圖G（V， E）伊辛模型哈密頓量表達式為：

其中si是頂點i∈V上的自旋變量，hi是作用在i∈V上的外磁場，Jij是邊（i，j）∈E上的兩個頂點之間的耦合強度。

二次無約束二值優化問題（QUBO）

QUBO表示的是二次無約束二值優化問題，損失函數僅由一次項和二次項組成，具體表達式為：

其中xi為第i個二元變量，ai和bij都為實數。通過與伊辛模型比較，可以看出伊辛模型中的二元變量取值為si∈{-1，1}，QUBO的變量取值為xi∈{0，1}，由于變量都是二元結構，伊辛模型和QUBO在本質上是一致的，可以通過系數相互轉換。

貨幣套利分析

貨幣套利指的是從不同市場上同一貨幣的不同價格交易中獲利的方式。如圖1所示，圖中匯率為2023年11月27日的實時匯率數據，例如，100人民幣兌換成美元，美元兌換成歐元，歐元再兌換成人民幣，兌換后的人民幣面值為100×（1/7.144）×（1/1.094）×7.824≈100.11，經過一個循環交易，人民幣面值由100變為100.11，人民幣面值升值了0.11%，說明這個循環有套利空間，相反則沒有套利空間。

傳統套利分析是通過套利檢測算法實現，即通過定義如圖2所示的有向圖，對于有向圖中的任意一個圓環，計算在該圓環內的匯率乘積，然后取對數，再乘以-1，即-log（∏Rij），其中Rij表示由幣種i兌換成幣種j的實時匯率，當（∏Rij）>1時，認為該循環內有利可圖，存在套利空間，相反則沒有套利空間。在有套利空間的閉環中-log（∏Rij）的取值則為負數，簡稱負循環，套利檢測算法就是搜索圖中存在的負循環，并且在首次搜索到負循環之后就停止繼續搜索。傳統套利檢測算法可以在多項式時間內解決，如使用時間復雜度為O（|V||E|）（其中|V|是節點數，|E|是邊數）的Bellman-Ford算法，以及時間復雜度為O（|V|3）的Floyd-Warshall算法，這些算法的特點都是在首次發現負循環后就會終止搜索。相比之下，要找到最有利可圖的套利機會，則需要對圖內所有循環進行遍歷搜索，遍歷搜索的時間復雜度為O（|V|?。?，這屬于NP難問題。

實際交易過程中，交易者會對交易模式更感興趣，會綜合考慮交易方式、市場流動性、更短的交易閉環、更少的風險等。例如，存在兩個交易方案，一個是微利，一個是暴利，一般傳統的交易算法，如Bellman-Ford算法、Floyd-Warshall算法，在找到第一個有利可圖的交易方案后就停止繼續搜索。本文我們提供的量子退火算法，不僅可以找到最有利可圖的交易方案，而且可以依據有利可圖的順序依次給出其他多個交易方案，供交易者在實際交易過程中選擇最可行的交易路徑。

對于一般情況，假設有N個幣種，構建有N個節點（V），N×（N-1）條邊（E）的有向圖。用Rij表示由幣種i兌換成幣種j的匯率，實際交易過程中需要考慮匯兌交易中間費用，可以把居間費用成本折算進匯率中去，本文由于僅討論算法的有效性，暫不考慮居間成本。定義二元變量xij：

該優化問題的目標是希望找到有向圖中最有利可圖的交易閉環。即在一個閉環內，經過一次循環交易，選取出∏Rij（閉環內所有的Rij）的最大值。對于更一般的表示，需要引入二元變量xij，即找出∏[（Rij-1） xij+1]的最大值，連乘在數學上可以通過取對數改為連加，所以我們的目標函數簡化為：

由于我們交易必須是在一個閉環內完成，需要滿足閉環的兩個條件：首先，在圖中的節點，如果在交易循環內，則會有一個貨幣兌換輸入和一個貨幣兌換輸出，數學上表達為：

如果圖中的節點不在閉環中，則輸入輸出數都為0，上式也自動滿足。其次，在圖中的節點，如果在閉環內，則有且只有一個兌換輸出，即滿足，如果節點不在閉環內，則沒有與任何其他節點的貨幣兌換，即滿足，綜合這兩項得到第二個約束條件：

通過目標函數的確定和兩個約束條件，就可以構建系統的目標哈密頓量。由于量子退火算法的固有特性是從激發態通過絕熱演化尋找系統的基態，所以對上面的目標函數乘以-1，加入兩個約束條件，得到該系統的哈密頓量為：

H=-∑xijlog（Rij）+α（xij-xji）2+βxij （xij-1）

其中α和β為系統哈密頓量的超參數，取值為正數，當參數取值越大，在退火演化過程中約束性越強，具體數值在程序運行過程中，可以依據運行效率和結果進行適當調整。

確定了系統的哈密頓量，然后利用前面介紹的伊辛機去模擬量子退火過程，就可以快速求解出該系統的最低能態，即優化問題的最優解。

結果討論

本文使用DWave公司開發的PyQUBO的模擬退火模塊來實現量子退火模擬運算。根據前面的介紹，只要給出二元二次的哈密頓量，就可以通過PyQUBO完成量子退火的模擬計算。本文使用2023年11月27日的人民幣、歐元、美元、加元和日元5種貨幣的實時匯率數據進行模擬計算輸入，如圖2所示。圖中數字為當日的匯率，圖中僅標示出了一半的匯率數據，另一半取倒數即可（如USD→CNY的匯率7.144，CNY→USD的匯率為1/7.144）。

通過量子退火算法的計算，該系統的最低能級對應的量子態就是我們需要的最優解結果。表1列出了最低的五個系統能級，對應最優的5條交易路徑，最優解在圖2中用紅色箭頭表示。表1中的能量為系統哈密頓量所對應的能級。通過量子退火算法，我們找到了一條最有利可圖的交易路徑，即“JPY→CAD→CNY→USD→EUR→JPY”，通過該路徑進行交易，一次交易閉環收益0.151%。該方法不僅可以提供最優交易路徑，還給出其他交易路徑，包含系統絕熱演化過程中經歷的所有交易路徑，這里為了便于展示，僅列出收益前5的交易路徑。所有有利可圖路徑的求解便于讓交易者依據實際交易過程中的交易成本、市場流動性、更短的閉環等進行靈活選擇。

表1展示的是在5種貨幣中尋找出最有利可圖的交易路徑。實際的外匯交易市場有100多種主權貨幣，傳統的套利檢測算法在搜索到有利可圖的交易路徑之后就停止繼續搜索，無法確保該路徑是獲利最多的一條交易路徑，要尋找到最有利可圖的交易路徑需要遍歷搜索，時間復雜度為O（N！），這屬于NP難問題。由于Bellman-Ford算法與Floyd-Warshall算法在首次搜索到有利可圖的循環之后就停止了搜索，搜索能力受到極大的限制。為了更好地展現量子退火算法的優越性，本文將具有相同搜索能力的遍歷搜索、退火算法和量子退火算法進行了比較，其中退火算法和量子退火算法屬于近似優化算法，退火算法的時間復雜度為O（eN），量子退火算法的時間復雜度為O（e）[8]。圖3展示的是三種算法的時間復雜度比較，由于三種不同的算法時間復雜度差異巨大，筆者對縱軸（時間復雜度）取了對數，隨著被交易貨幣幣種數量的增加，不同算法的時間復雜度變化有巨大的差異。通過比較可以看出，通過引入量子退火算法，時間復雜度顯著下降，為解決傳統NP難問題，提供了一條可行的路徑。

結語

本文將量子退火算法的應用推廣到貨幣交易市場，對傳統NP難問題利用量子算法的超強并行計算能力進行解決，為貨幣交易市場打開了一扇新的大門。隨著金融科技的發展，量子計算在金融領域的大量應用，傳統金融市場將會受到沖擊，有些傳統范圍內無法解決的問題可能會被量子計算所突破，從而帶來金融領域的全新變革。我們走在大時代的前沿，將量子科技引入金融領域，將會給我們帶來一個嶄新的金融世界。

【參考文獻】

[1]Shor PW.Algorithms for Quantum Computation： Discrete Logarithms and Factoring [J]. Proceedings 35th Annual Symposium on Foundations of Computer Science， 1994：124-134.

[2]Grover LK.A Fast Quantum Mechanical Algorithm for Database Search [J]. Proceedings of the 28th Annual ACM Symposium on Theory of Computing， 1996：212-219

[3]Nouhaila Innan， Abhishek Sawaika， Ashim Dhor， et al. Financial Fraud Detection using Quantum Graph Neural Networks[J]. 2023.

[4]G. Rosenberg， P. Haghnegahdar， P. Goddard，et al. Solving the Optimal Trading Trajectory Problem using a Quantum Annealer[J]. IEEE Journal of Selected Topics Signal Processing， 2016， 10（6）：1053-1060.

[5]F. Neukart， G. Compostella， C. Seidel，et al.Traffic Fow Optimization using a Quantum Annealer [J]. Frontiers in ICT， 2017， 4：1-6.

[6]N. Nishimura， K. Tanahashi， K. Suganuma， et al. Item Listing Optimization for E-commerce Websites Based on Diversity[J]. Frontiers in Computer Science， 2019.

[7]K. Kitai， J. Guo， S. Ju， Tanaka， et al. Designing Metamaterials with Quantum Annealing and Factorization Machines[J]. Physical Review Research， 2020，2（1）：0133191-01331910.

[8]Mukherjee S， Chakrabarti B. Multivariable optimization： Quantum Annealing and Computation[J]. The European Physical Journal Special Topics. 2015. 224（1）：17-24.

（作者單位：中國電子科技集團公司第三十二研究所）