Budou jednou kvantové počítače řídit devizové rezervy? (díl 3)
Finanční sektor patří mezi odvětví, které historicky silně závisí na výpočetní technice – od prostého vedení záznamů o peněžních tocích po sofistikované modely snažící se předpovědět budoucí vývoj na finančních trzích. V příspěvcích z prosince 2021 a března 2022 jsme se seznámili s novým výpočetním nástrojem, kvantovým počítačem, který by mohl nalézt uplatnění právě také ve finančnictví. Zjistili jsme, že prozatím se většina teoretických návrhů, ať již jde o měření rizik nebo řešení soustav lineárních rovnic, pro praxi příliš nehodí. Důvodem nejsou nedostatky samotných algoritmů, ale i přes rapidní pokrok, stále nízká úroveň vývoje kvantových procesorů. Nehledě na tyto počáteční nesnáze jsme ale došli k závěru, že v jedné oblasti by kvantové počítače mohly své uplatnění pro „téměř praktické“ úlohy nalézt již nyní. Konkrétně jde o tzv. kvadratickou binární optimalizaci bez omezujících podmínek, jež může být využita při hledání optimálního portfolia. Právě toto zjištění motivovalo další výzkum možných aplikací kvantových optimalizačních algoritmů v bankovnictví obecně, a v našem případě konkrétně ve spojení s řízením devizových rezerv.
V tomto článku se tedy nejprve podíváme na klasický postup, kterým lze optimalizovat portfolio, poté popíšeme některé kvantové optimalizační techniky, dále přejdeme k jejich nasazení při hledání optimální měnové struktury devizových rezerv a na závěr se podíváme na další perspektivy kvantové optimalizace ve finančním světě. Zde však musíme upozornit, že námi získané výsledky nebyly uvedeny do praxe, neboť naše úloha má čistě výzkumný a vzdělávací charakter. Samotný proces volby měnové kompozice devizových rezerv je komplexní úloha zahrnující množství expertních vstupů a rozhodně se nelze spoléhat pouze na čistě technický pohled ať již klasických či kvantových algoritmů.
Publikováno v rámci Working Paper 1/2023.
Jak najít optimální portfolio?
Před tím než se pustíme do popisu kvantových optimalizačních technik, krátce se zastavíme u optimalizace portfolia jako takové. V roce 1952 Harry Markowitz navrhl techniku založenou na kvadratickém programování [1]. Jeho snahou bylo nalézt optimální kompromis mezi výnosem, který je reprezentován váženým součtem výnosů jednotlivých aktiv v portfoliu, a rizikem daným kolísavostí (volatilitou) těchto výnosů a jejich vzájemnou korelací.[1] Právě člen popisující riziko je kvadratický, proto je využito kvadratické programování. Ačkoliv Markowitzem navržená technika zavádí řadu omezení na vstupní data[2], stala se standardním nástrojem pro hledání optimální struktury portfolia.
Nevýhodou kvadratického programování je ale v obecném případě vysoká výpočetní náročnost [3].[3] I když je tento nejhorší případ v praxi poměrně řídký, je motivací pro hledání technik, které by jej dokázaly účinně potlačit. Navíc jakékoliv dodatečné zrychlení výpočtů, i v případě příznivých případů, určitě využijí „vysokofrekvenční“ obchodníci. Vznikla proto řada studií snažících se odpovědět na otázku, zda by nebylo možné pro Markowitzovu optimalizaci portfolia využít také kvantové počítače [4,5,6,7].
Užití kvantových počítačů sebou ale nese nutnost převést optimalizační úlohu do binární podoby. To znamená, že váha aktiva je vyjádřena jako řetězec binárních proměnných, tj. takových, jež nabývají pouze hodnoty 0 či 1. Pokud chceme získat dostatečnou přesnost, počet proměnných bude značný. Navíc binární podoba kvadratického programování je výpočetně velmi náročná.[4] Nicméně výkon kvantových počítačů by měl být takový, že i toto „umělé ztížení“ úlohy nakonec povede k rychlejšímu nalezení optimální struktury portfolia ve srovnání s klasickým přístupem.
Jak pomohou kvantové počítače?
Nyní již můžeme přejít k popisu jednotlivých kvantových algoritmů, jejichž schopnosti jsme posuzovali. První skupinou kvantových optimalizačních algoritmů jsou variační algoritmy. Společným jmenovatelem těchto algoritmů je snaha o převod optimalizační úlohy na simulaci kvantového systému. Konec konců, právě pro tento účel byl kvantový počítač vůbec navržen. Kvantových systémů existuje v přírodě velké množství, nicméně kvadratické binární optimalizaci jsou nejpodobnější tzv. spinová skla, což je speciální třída magnetických materiálů stojících na pomezí mezi feromagnetiky (např. železo) a paramagnetiky (např. měď). [5]
Každý kvantový systém, tedy včetně spinového skla, je popsán tzv. Hamiltoniánem, jež říká, v jakých energických hladinách se může kvantový systém nacházet. Při zkoumání kvantového systému nás zajímá především stav s nejnižší energií (tzv. základní stav). Zde je již jasně vidět vazba na optimalizační úlohu – základní stav je ztotožněn s optimálním řešením. Jakmile tedy máme k naší optimalizační úloze přiřazen kvantový systém, můžeme se pustit do jeho simulace a najít optimální řešení úlohy.
Samotnou simulaci lze provést pomocí několika různých přístupů. Algoritmy Quantum Approximate Optimization Algorithm (QAOA) [8] a Variational Quantum Eigensolver (VQE) [9] je možné provozovat na univerzálních kvantových počítačích jako je např. IBM QuantumTM [10]. Zatímco první algoritmus je určen výhradně pro simulace spinových skel, druhý je obecnější a umožňuje pracovat i s dalšími kvantovými systémy. Oba algoritmy mají ovšem společné to, že jsou iterativní a kombinují kvantový přístup (vlastní simulace kvantového systému) a klasický přístup (výpočet energie kvantových stavů).
Vedle univerzálních kvantových počítačů je možné simulaci spinových skel provádět na tzv. kvantových annealerech, které poskytuje kanadská společnost D-Wave Systems [11]. Jedná se o jednoúčelové kvantové počítače, které v podstatě fyzicky implementují simulaci spinových skel. Kvantové annealery lze navíc kombinovat s klasickými algoritmy (tzv. hybridní řešiče). V tomto případě je úloha rozdělena na menší, které jsou řešeny „kvantově“ a následně zkombinovány zpět „klasicky“. Případně může být výstup klasického algoritmu použit jako vstup do kvantového, který jej dále zpřesní. Dodejme, že podrobný popis algoritmu QAOA a teoretického základu variačních algoritmů je uveden v našem předchozím příspěvku.
Zcela jiný přístup k řešení kvadratických binárních optimalizačních úloh je založen na Groverově algoritmu [12,13]. Jedná se o algoritmus, který byl původně navržen pro rychlé vyhledávání v neuspořádaných databázích pomocí kvantového počítače.[6] V navržené modifikaci je databáze nahrazena hodnotami optimalizované funkce, které jsou zakódovány do kvantové superpozice [14]. Z nich je pak sérií kvantových operací vybrána co možná nejnižší hodnota této funkce a měřením výstupu kvantového počítače získáno optimální řešení. Dojdeme však, že kvantový výpočet je opět iterativní, přičemž v každé iteraci dochází ke zlepšení hodnoty optimalizované funkce.
Podívejme se ještě, jaké teoretické zrychlení popsané kvantové algoritmy nabízí oproti klasickému přístupu. Variační algoritmy jsou heuristiky, což znamená, že negarantují nalezení optimálního řešení a rigorózně pro ně bylo dokázáno žádné zrychlení. Nicméně řada studií naznačuje, že v případě některých specifických úloh jsou výkonnější než klasické algoritmy [7,15,16,17]. Na druhé straně přístup založený na Groverově algoritmu má teoreticky dokázané tzv. kvadratické zrychlení. Zjednodušeně řečeno, namísto 10 000 operací v klasickém případě postačí 100 v kvantovém případě. Výhodou variačních algoritmů je ale menší náchylnost na šum kvantových procesorů, což je naopak problémem pro Groverův algoritmus. Groverův algoritmus pro řešení určité úlohy vyžaduje také větší počet qubitů než variační algoritmy (např. pro 6 proměnných variační algoritmy potřebují 6 qubitů, Groverův přístup v našem případě vyžadoval 13 qubitů).
Jakou úlohu jsme konkrétně řešili?
Výše popsané algoritmy jsme použili při hledání optimální měnové struktury devizových rezerv. Cílem byla maximalizace zisku rezerv v korunovém vyjádření, přičemž současně měla být minimalizována volatilita tohoto zisku. Naše úloha byla navíc tzv. dynamickou optimalizací portfolia. Jinými slovy, hledali jsme optimální složení portfolia v různých časových obdobích. V našem cvičení byla tato období vymezena konci významných globálních krizí, které obvykle znamenají změnu tržního režimu čili tzv. „nový normál“. Pro účely naší úlohy byly za tyto krize zvoleny Velká kreditní krize v letech 2007 až 2009, dluhová krize eurozóny během let 2011 až 2013 a krize vyvolaná pandemií koronaviru covid-19 v letech 2020 a 2021. Dynamická podoba optimalizační úlohy si vyžádala vedle maximalizace zisku při minimální volatilitě další dodatečné optimalizační kritérium, totiž minimalizaci transakčních nákladů spojených se změnou měnové kompozice mezi obdobími. Dodejme, že do optimalizace byly zahrnuty všechny měny, které se nyní nachází v devizových rezervách, tedy AUD, CAD, CNY, EUR, GBP, JPY, SEK, USD a zlato.
V binární podobě měla výše uvedená úloha celkově 378 binárních proměnných[7]. Jelikož ne každý kvantový algoritmus je schopen s takovýmto počtem proměnných pracovat, vytvořili jsme také jednoduší verzi zahrnující pouze jedno období (konkrétně Velkou kreditní krizi), ale zároveň všech devět jmenovaných měn. Pro účely testování počítače IBM QuantumTM jsme úlohu museli dále zjednodušit pouze na tři měny (AUD, CAD a zlato). Zároveň jsme snížili požadavky na přesnost vah měn. V prvém případě tak počet binárních proměnných klesl na 90, v druhém na pouhých 6 (od IBM máme k dispozici procesory pouze se sedmi kvantovými bity).
Dodejme, že pro účely porovnání schopnosti najít optimální řešení úlohy a rychlosti nalezení tohoto řešení jsme nejprve provedli optimalizaci pomocí klasické spojité gradientní metody [18] implementované v MS Excel.[8] Binární formu úlohy jsme pak řešili s pomocí klasických exaktních, a také heuristických algoritmů. Zástupcem exaktních algoritmů je metoda větví a mezí [19], která se snaží prohledávat prostor možných řešení úlohy tak, aby eliminovala řešení mající hodnotu účelové funkce horší než dosud nalezená.[9] Tímto přístupem je ušetřen čas, neboť není nutné testovat všechna možná řešení úlohy.[10] Z heuristických algoritmů založených na náhodném hledání řešení jsme využili simulované žíhání [20], tedy metodu založenou na simulaci chladnutí materiálu, a genetickou optimalizaci [21] vycházející ze simulace evolučních procesů. Tím jsme získali srovnávací základnu pro posouzení schopností kvantových algoritmů.
Co jsme zjistili?
Začněme s výsledky algoritmů určených pro univerzální kvantové počítače. Veškeré výpočty jsme prováděli na kvantovém počítači IBM QuantumTM. Dobrou zprávou je, že jak VQE, tak QAOA jsou schopné najít řešení naší úlohy. Nicméně vzhledem k malému počtu qubitů (využili jsme procesory s kódovými jmény Nairobi a Oslo, které mají pouze sedm qubitů), jsme byli schopni otestovat pouze velmi zjednodušenou verzi úlohy se třemi měnami. Řešič založený na Groverově algoritmu bylo možné spustit pouze na simulátoru, neboť v našem případě by vyžadoval 13 qubitů. Nicméně simulovaný výpočet dospěl k optimálnímu řešení. V principu je tedy tento řešič použitelný. Úlohu se třemi měnami jsme řešili také s pomocí annealeru D-Wave jak v čistě kvantové, tak hybridní podobě. Také tento přístup dokázal nalézt optimum.
Z hlediska času zpracování si ale nejlépe vedlo klasické simulované žíhání, následované annealerem
D-Wave, genetickou optimalizací, řešičem v MS Excel a metodou větví a mezí. Hybridní řešič D-Wave skončil předposlední. Poslední místo patří algoritmům VQE a QAOA. Nicméně řešení úlohy o pouhých 6 binárních proměnných má stěží dostatečnou vypovídací hodnotu pro posouzení chování algoritmů v „praktických rozměrech“ úloh. Algoritmy pro univerzální kvantové počítače typu IBM tak bude možné lépe otestovat v momentě, kdy budeme mít dostupné procesory s více qubity.
Nehledě na omezení daná nedokonalostmi univerzálních kvantových procesorů, kvantový svět nám stejně může pomoci s naší optimalizací portfolia. Kvantové annealery jsou totiž schopné pracovat i s několika stovkami binárními proměnnými již nyní. Vyzkoušeli jsme tedy annealer D-Wave nasadit na úloze s jednou časovou periodou, ale devíti měnami. Samotný kvantový annealer byl od optima ještě relativně daleko, ale v kombinaci s klasickými algoritmy (tedy v hybridní formě) se optimu již velmi přiblížil a navíc překonal klasické simulované žíhání, genetickou optimalizaci i metodu větví a mezí. Z hlediska doby běhu byl ale výrazně lepší řešič v MS Excel (cca 13x rychlejší).
V případě „plné“ úlohy, tedy se třemi časovými obdobími, jsme porovnali výstup MS Excelu, metody větví a mezí, simulovaného žíhání a hybridního řešiče od D-Wave. Ostatní algoritmy byly totiž od optima „extrémně“ daleko. MS Excel nabídl opět lepší řešení a v kratším čase než D-Wave. Rozdíl mezi řešením získaným pomocí D-Wave a řešiče v Excelu ale nebyl výrazný. Časový náskok Excelu také poklesl, konkrétně byl „pouze“ 3x rychlejší. Simulované žíhání zůstalo beznadějně vzadu s takřka 1 000 krát delší doba běhu než v případě D-Wave a značnou vzdáleností nabídnutého řešení od optima. Metoda větví a mezí poskytla přibližně stejné výsledky jako D-Wave ale za cenu doby běhu v řádu hodin, kdežto D-Wave zvládl najít řešení během sekund.
Jaké jsou perspektivy kvantové optimalizace portfolia?
Celkově se tedy může zdát, že v dané chvíli kvantový počítač nemá v optimalizaci portfolia své místo, protože si bez potíží vystačíme s MS Excelem dostupným na jakémkoliv kancelářském počítači. Nicméně tento závěr by byl příliš kategorický.
Za prvé, z výsledků výše vidíme, že s rostoucím rozměrem úlohy se nůžky mezi klasickým a kvantovým, resp. hybridním, přístupem uzavírají. V případě velmi jednoduché úlohy s šesti proměnnými je hybridní řešič prakticky „na chvostu“. Jak ale proměnných přibývá, tento řešič si vede stále lépe.
Za druhé, je nutné vzít v potaz, jak jsme již uváděli výše, že „binarizace“ optimalizační úlohy ji do značné míry ztíží. Pokud však srovnáme algoritmy čistě na poli binární optimalizace, jasným vítězem je hybridní přístup. Podobně obtížné úlohy jako námi řešená, byť by neměly přímé praktické uplatnění, mohou sloužit jako dobré testovací příklady pro nově vyvíjené kvantové počítače, ať již univerzální stroje, tak jednoúčelové annealery.
Za třetí, ačkoliv kvantové annealery jsou ve srovnání s univerzální kvantovými počítači výrazně pokročilejší, do značné míry se také jedná o experimentální zařízení. Z tohoto důvodu budeme vývoj průběžně sledovat a další testy provedeme až v delším časovém horizontu.
Celkově pro naše účely v ČNB, minimálně v souvislosti s řízením devizových rezerv, prozatím postačí klasické počítače. Nicméně komerční banky a další finanční instituce se o oblast kvantových počítačů zajímají, musíme proto mít o této nové technologii přehled, a být si vědomi jejích schopností a omezení.
Zdroje
[1] MARKOWITZ, H. (1952): “Portfolio Selection.” The Journal of Finance, 7(1):77-91.
[2] MANDELBROT, B (1963). “New methods in statistical economics.” Journal of political economy
71(5): 421-
[3] VAVASIS, S. A. (1990): “Quadratic programming is in NP.” Information Processing Letters, 36 (2):73-77.
[4] ELSOKKARY, N., F. S. KHAN, D. L. TORRE, T. S. HUMBLE, AND J. GOTTLIEB (2017): “Financial Portfolio Management using D-Wave Quantum Optimizer: The Case of Abu Dhabi Securities Exchange.” IEEE High-performance Extreme Computing 2017 Conference Proceedings.
[5] ROSENBERG, G., P. HAGHNEGAHDAR, P. GODDARD, P. CARR, K. WU, AND M. L. DE PRADO (2016): “Solving the Optimal Trading Trajectory Problem Using a Quantum Annealer.” IEEE Journal of Selected Topics in Signal Processing, 10(6):1053-1060.
[6] PALMER, S., S. SAHIN, R. HERNÁNDEZ, S. MUGEL, AND R. ORÚS (2021): “Quantum Portfolio Optimization with Investment Bands and Target Volatility.” arXiv:2106.06735v3 [q-fin.PM].
[7] MUGEL, S., C. KUCHKOVSKY, E. SÁNCHEZ, S. FERNÁNDEZ-LORENZO, J. LUIS-HITA, E. LIZASO, AND R. ORÚS (2022): “Dynamic Portfolio Optimization with Real Datasets using Quantum Processors and Quantum-Inspired Tensor Networks.” Physical Review Research, 4(1):013006.
[8] FARHI, E., J. GOLDSTONE, AND S. GUTMANN (2014): “A Quantum Approximate Optimization Algorithm.” arXiv:1411.4028v1 [quant-ph].
[9] PERUZZO, A., J. MCCLEAN, P. SHADBOLT, M.-H. YUNG, X.-Q. ZHOU, P. J. LOVE, A. ASPURU-GUZIK, AND J. L. O’BRIEN (2014): “A Variational Eigenvalue Solver on a Photonic Quantum Processor.” Nature Communications, 5(5):4213.
[10]https://quantum-computing.ibm.com/
[12]GROVER, L. K. (1996): “A Fast Quantum Mechanical Algorithm for Database Search.” Proceedings, 28th Annual ACM Symposium on the Theory of Computing (STOC), 212-219.
[13]GROVER, L. K. (2001): “From Schrödinger’s Equation to the Quantum Search Algorithm.” Pramana: Journal of Physics, 56(2):333-348.
[14]GILLIAM, A., S. WOERNER, AND C. GONCIULEA (2021): “Grover Adaptive Search for Constrained Polynomial Binary Optimization.” Quantum, 5:428.
[15]DING, Y., J. GONZALEZ-CONDE, L. LAMATA, J. D. MARTÍN-GUERRERO, E. LIZASO, S. MUGEL, X. CHEN, R. ORÚS, E. SOLANO, AND M. SANZ (2019): “Towards Prediction of Financial Crashes with a D-Wave Quantum Computer.” arXiv:1904.05808v3 [quant-ph].
[16]HARWOOD, S., C. GAMBELLA, D. TRENEV, A. SIMONETTO, D. BERNAL, AND D. GREENBERG (2021): “Formulating and Solving Routing Problems on Quantum Computers.” IEEE Transactions on Quantum Engineering, 2:1-
[17]EGGER, D. J., J. MAREČEK, AND S. WOERNER (2021): “Warm-Starting Quantum Optimization.” Quantum, 5:479.
[18]LEMARÉCHAL, C. (2012): “Cauchy and the gradient method.” Documenta Mathematica, Extra Vol. Optimization Stories:251-254.
[19]LAND, A. H. AND A. G. DOIG (1960): “An Automatic Method of Solving Discrete Programming Problems.” Econometrica, 28(3):497–520.
[20]CORANA, A., M. MARCHESI, C. MARTINI, AND S. RIDELLA (1987): “Minimizing Multimodal Functions of Continuous Variables with the Simulated Annealing Algorithm.” ACM Transactions on Mathematical Software, 13(3):262-280.
[21]KATOCH, S., S. S. CHAUHAN, AND V. KUMAR (2021): “A Review on Genetic Algorithm: Past, Present, and Future.” Springer: Multimedia Tools and Applications, 50(5):8091-8126.
Klíčová slova
Devizové rezervy, kvadratická binární optimalizace, kvantové počítače, optimalizace portfolia
Klasifikace JEL
C61, C63, G11
[1] Matematicky řečeno -rTw + λwTCw → MIN, jde o tuto úlohu , kde w jsou váhy aktiv, r očekávané výnosy, C je kovariační matice a λ > 0 je míra sklonu k riziku.
[2] Předpokládá např. normální rozdělení výnosů aktiv, což kritizoval známý matematik Benoit Mandelbrot [2].
[3] Jde obecně o tzv. NP obtížnou úlohu. Počet nezbytných operací roste v počtu proměnných exponenciálně.
[4] Úloha kvadratického binárního programování je vždy NP obtížná.
[5] Feromagnetikum si po odstranění z magnetického pole zachovává magnetizaci, paramagnetikum ji exponenciálně rychle ztrácí. Magnetizace spinových skel vykazuje lineární pokles magnetizace.
[6] Neuspořádaná databáze nemá index. To znamená, že při vyhledávání musíme procházet jednu položku za druhou. Dobrou analogií neuspořádané databáze je hromada dokumentů bez jakékoliv vazby mezi sebou, a v níž hledáme jeden konkrétní např. podle čísla na deskách.
[7] Předpokládejme, že bychom procházeli jedno řešení za druhým (tzv. metoda hrubé síly). Dále uvažme, že ověření, zda je dané řešení lepší než dosud nalezené bude trvat jednu nanosekundu (cca odpovídá taktu procesoru v řádu GHz), pak bude trvat nalezení optima 1099 let. Nicméně doba trvání vesmíru je pouze 13,77x109 let. Zde je tedy zjevné, že pro řešení takovýchto úloh potřebujeme sofistikované exaktní algoritmy či heuristiky, ať již klasické nebo kvantové.
[8] Můžete si vyzkoušet sami, jelikož jde o běžně používaný „solver“ v Excelu: Data => Analýza => Řešitel.
[9] Poznamenejme, že jsme využili implementaci metody větví a mezí v optimalizačním softwarovém nástroji IBM CPLEX Studio, které je v dostupné zdarma pro řešení úloh majících méně než 1 000 proměnných.
[10] Nicméně v nejhorším případě může metoda větví a mezí zdegenerovat do metody hrubé síly.