Quantum walk-based portfolio optimisation

N. Slate, E. Matwiejew, S. Marsh, and J. B. Wang

Department of Physics, The University of Western Australia, Perth WA 6009, Australia

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

This paper proposes a highly efficient quantum algorithm for portfolio optimisation targeted at near-term noisy intermediate-scale quantum computers. Recent work by Hodson et al. (2019) explored potential application of hybrid quantum-classical algorithms to the problem of financial portfolio rebalancing. In particular, they deal with the portfolio optimisation problem using the Quantum Approximate Optimisation Algorithm and the Quantum Alternating Operator Ansatz. In this paper, we demonstrate substantially better performance using a newly developed Quantum Walk Optimisation Algorithm in finding high-quality solutions to the portfolio optimisation problem.

► BibTeX data

► References

[1] P. W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Sci. Comput., 26 (5): 1484–1509, 1997. 10.1137/​s0097539795293172.
https:/​/​doi.org/​10.1137/​s0097539795293172

[2] M. A. Nielsen and I. L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, Cambridge, 2010. 10.1017/​CBO9780511976667.
https:/​/​doi.org/​10.1017/​CBO9780511976667

[3] J. Preskill. Quantum computing in the NISQ era and beyond. Quantum, 2: 79, 2018. 10.22331/​q-2018-08-06-79.
https:/​/​doi.org/​10.22331/​q-2018-08-06-79

[4] P. Rebentrost and S. Lloyd. Quantum computational finance: quantum algorithm for portfolio optimization, 2018. URL https:/​/​arxiv.org/​abs/​1811.03975.
arXiv:1811.03975

[5] P. Rebentrost, B. Gupt, and T. R. Bromley. Quantum computational finance: Monte Carlo pricing of financial derivatives. Phys. Rev. A, 98: 022321, 2018. 10.1103/​PhysRevA.98.022321.
https:/​/​doi.org/​10.1103/​PhysRevA.98.022321

[6] R. Orús, S. Mugel, and E. Lizaso. Quantum computing for finance: Overview and prospects. Rev. Phys., 4: 100028, 2019. 10.1016/​j.revip.2019.100028.
https:/​/​doi.org/​10.1016/​j.revip.2019.100028

[7] S. Woerner and D. J. Egger. Quantum risk analysis. npj Quantum Inf., 5 (1), 2019. 10.1038/​s41534-019-0130-6.
https:/​/​doi.org/​10.1038/​s41534-019-0130-6

[8] M. Hodson, B. Ruck, H. Ong, D. Garvin, and S. Dulman. Portfolio rebalancing experiments using the Quantum Alternating Operator Ansatz, 2019. URL https:/​/​arxiv.org/​abs/​1911.05296.
arXiv:1911.05296

[9] H. Markowitz. Portfolio selection. J. Finance, 7 (1): 77–91, 1952. 10.1111/​j.1540-6261.1952.tb01525.x.
https:/​/​doi.org/​10.1111/​j.1540-6261.1952.tb01525.x

[10] A. Palczewski. LP algorithms for portfolio optimization: The PortfolioOptim package. R J., 10: 308–327, 2018. 10.32614/​RJ-2018-028.
https:/​/​doi.org/​10.32614/​RJ-2018-028

[11] R. Mansini and M. G. Speranza. Heuristic algorithms for the portfolio selection problem with minimum transaction lots. Eur. J. Oper. Res., 114 (2): 219–233, 1999. 10.1016/​S0377-2217(98)00252-5.
https:/​/​doi.org/​10.1016/​S0377-2217(98)00252-5

[12] T. F. Coleman, Y. Li, and J. Henniger. Minimizing tracking error while restricting the number of assets. J. Risk, 8: 33, 2006. 10.21314/​JOR.2006.134.
https:/​/​doi.org/​10.21314/​JOR.2006.134

[13] J. Cook, S. Eidenbenz, and A. Bärtschi. The Quantum Alternating Operator Ansatz on max-k vertex cover, 2019. URL https:/​/​arxiv.org/​abs/​1910.13483. 10.1109/​QCE49297.2020.00021.
https:/​/​doi.org/​10.1109/​QCE49297.2020.00021
arXiv:1910.13483

[14] E. Farhi and A. W. Harrow. Quantum supremacy through the Quantum Approximate Optimization Algorithm, 2016. URL https:/​/​arxiv.org/​abs/​1602.07674.
arXiv:1602.07674

[15] S. Marsh and J. B. Wang. Combinatorial optimization via highly efficient quantum walks. Phys. Rev. Research, 2: 023302, 2020. 10.1103/​PhysRevResearch.2.023302.
https:/​/​doi.org/​10.1103/​PhysRevResearch.2.023302

[16] M. C. Steinbach. Markowitz revisited: Mean-variance models in financial portfolio analysis. SIAM Rev., 43 (1): 31–85, 2001. 10.1137/​S0036144500376650.
https:/​/​doi.org/​10.1137/​S0036144500376650

[17] K. P. Anagnostopoulos and G. Mamanis. The mean–variance cardinality constrained portfolio optimization problem: An experimental evaluation of five multiobjective evolutionary algorithms. Expert Syst. Appl., 38 (11): 14208–14217, 2011. 10.1016/​j.eswa.2011.04.233.
https:/​/​doi.org/​10.1016/​j.eswa.2011.04.233

[18] M. Bióna. Handbook of enumerative combinatorics. CRC Press, Boca Raton, 2015. 10.1201/​b18255.
https:/​/​doi.org/​10.1201/​b18255

[19] S. Hadfield, Z. Wang, B. O’Gorman, E. Rieffel, D. Venturelli, and R. Biswas. From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz. Algorithms, 12 (2): 34, 2019. 10.3390/​a12020034.
https:/​/​doi.org/​10.3390/​a12020034

[20] E. Farhi and S. Gutmann. Quantum computation and decision trees. Phys. Rev. A, 58: 915–928, 1998. 10.1103/​PhysRevA.58.915.
https:/​/​doi.org/​10.1103/​PhysRevA.58.915

[21] K. Manouchehri and J. B. Wang. Physical implementation of quantum walks. Springer, Heidelberg, 2014. 10.1007/​978-3-642-36014-5.
https:/​/​doi.org/​10.1007/​978-3-642-36014-5

[22] X. Qiang, T. Loke, A. Montanaro, K. Aungskunsiri, X. Zhou, J. L. O'Brien, J. B. Wang, and J. C. F. Matthews. Efficient quantum walk on a quantum processor. Nat. Commun., 7 (1): 11511, 2016. 10.1038/​ncomms11511.
https:/​/​doi.org/​10.1038/​ncomms11511

[23] A. Mahasinghe and J. B. Wang. Efficient quantum circuits for Toeplitz and Hankel matrices. J. Phys. A, 49 (27): 275301, 2016. 10.1088/​1751-8113/​49/​27/​275301.
https:/​/​doi.org/​10.1088/​1751-8113/​49/​27/​275301

[24] S. S. Zhou, T. Loke, J. A. Izaac, and J. B. Wang. Quantum Fourier transform in computational basis. Quantum Inf. Process., 16 (3): 82, 2017. 10.1007/​s11128-017-1515-0.
https:/​/​doi.org/​10.1007/​s11128-017-1515-0

[25] S. S. Zhou and J. B. Wang. Efficient quantum circuits for dense circulant and circulant-like operators. R. Soc. Open Sci., 4 (5, May): 160906, 12, 2017. 10.1098/​rsos.160906.
https:/​/​doi.org/​10.1098/​rsos.160906

[26] T. Loke and J. B. Wang. Efficient quantum circuits for Szegedy quantum walks. Ann. Phys., 382: 64–84, 2017a. 10.1016/​j.aop.2017.04.006.
https:/​/​doi.org/​10.1016/​j.aop.2017.04.006

[27] T. Loke and J. B. Wang. Efficient quantum circuits for continuous-time quantum walks on composite graphs. J. Phys. A, 50 (5): 055303, 2017b. 10.1088/​1751-8121/​aa53a9.
https:/​/​doi.org/​10.1088/​1751-8121/​aa53a9

[28] X. Qiang, X. Zhou, J. Wang, C. M. Wilkes, T. Loke, S. O'Gara, L. Kling, G. D. Marshall, R. Santagati, T. C. Ralph, J. B. Wang, J. L. O'Brien, M. G. Thompson, and J. C. F. Matthews. Large-scale silicon quantum photonics implementing arbitrary two-qubit processing. Nat. Photonics, 12 (9): 534–539, 2018. 10.1038/​s41566-018-0236-y.
https:/​/​doi.org/​10.1038/​s41566-018-0236-y

[29] C.-H. Yu, F. Gao, C. Liu, D. Huynh, M. Reynolds, and J. Wang. Quantum algorithm for visual tracking. Phys. Rev. A, 99: 022301, 2019. 10.1103/​PhysRevA.99.022301.
https:/​/​doi.org/​10.1103/​PhysRevA.99.022301

[30] R. Cleve and J. Watrous. Fast parallel circuits for the quantum Fourier transform. In Proceedings of SFCS 41, pages 526–536, 2000. 10.1109/​SFCS.2000.892140.
https:/​/​doi.org/​10.1109/​SFCS.2000.892140

[31] G. R. Ahokas. Improved algorithms for approximate quantum Fourier transforms and sparse Hamiltonian simulations. Master's thesis, University of Calgary, 2004. URL https:/​/​dx.doi.org/​10.11575/​PRISM/​22839.
https:/​/​doi.org/​10.11575/​PRISM/​22839

[32] E. Matwiejew. QuOp_MPI: Parallel distributed memory simulation of Quantum Approximate Optimization Algorithms, 2020. URL https:/​/​doi.org/​10.5281/​zenodo.3681801.
https:/​/​doi.org/​10.5281/​zenodo.3681801

[33] E. Matwiejew and J. B. Wang. QSW_MPI: A framework for parallel simulation of quantum stochastic walks. Comput. Phys. Commun., 260: 107724, 2021. 10.1016/​j.cpc.2020.107724.
https:/​/​doi.org/​10.1016/​j.cpc.2020.107724

[34] W. McKinney. Data Structures for Statistical Computing in Python. In Proceedings of the 9th Python in Science Conference, pages 56–61, 2010. 10.25080/​Majora-92bf1922-00a.
https:/​/​doi.org/​10.25080/​Majora-92bf1922-00a

[35] L. Han and M. Neumann. Effect of dimensionality on the Nelder–Mead simplex method. Optim. Methods Softw., 21 (1): 1–16, 2006. 10.1080/​10556780512331318290.
https:/​/​doi.org/​10.1080/​10556780512331318290

[36] C. Zalka. Grover's quantum searching algorithm is optimal. Phys. Rev. A, 60: 2746–2751, 1999. 10.1103/​PhysRevA.60.2746.
https:/​/​doi.org/​10.1103/​PhysRevA.60.2746

[37] A. M. Childs and J. Goldstone. Spatial search by quantum walk. Phys. Rev. A, 70: 022314, 2004. 10.1103/​PhysRevA.70.022314.
https:/​/​doi.org/​10.1103/​PhysRevA.70.022314

[38] J. Roland and N. J. Cerf. Quantum-circuit model of Hamiltonian search algorithms. Phys. Rev. A, 68: 062311, 2003. 10.1103/​PhysRevA.68.062311.
https:/​/​doi.org/​10.1103/​PhysRevA.68.062311

[39] D. L. Applegate, R. E. Bixby, V. Chvatal, and W. J. Cook. The Traveling Salesman Problem: A Computational Study. Princeton University Press, USA, 2007. 10.1515/​9781400841103.
https:/​/​doi.org/​10.1515/​9781400841103

Cited by

[1] Mathieu Roget and Giuseppe Di Molfetta, Communications in Computer and Information Science 2021, 72 (2024) ISBN:978-3-031-56942-5.

[2] Dengke Qu, Edric Matwiejew, Kunkun Wang, Jingbo Wang, and Peng Xue, "Experimental implementation of quantum-walk-based portfolio optimization", Quantum Science and Technology 9 2, 025014 (2024).

[3] Edric Matwiejew and Jingbo B. Wang, "QuOp_MPI: A framework for parallel simulation of quantum variational algorithms", Journal of Computational Science 62, 101711 (2022).

[4] Benjamin C B Symons, David Galvin, Emre Sahin, Vassil Alexandrov, and Stefano Mensa, "A practitioner’s guide to quantum algorithms for optimisation problems", Journal of Physics A: Mathematical and Theoretical 56 45, 453001 (2023).

[5] Lydia Fernandes, Mugdha Kulkarni, and Mandaar B. Pande, 2023 IEEE Pune Section International Conference (PuneCon) 1 (2023) ISBN:979-8-3503-2420-4.

[6] Shree Hari Sureshbabu, Dylan Herman, Ruslan Shaydulin, Joao Basso, Shouvanik Chakrabarti, Yue Sun, and Marco Pistoia, "Parameter Setting in Quantum Approximate Optimization of Weighted Problems", Quantum 8, 1231 (2024).

[7] Sebastian Brandhofer, Daniel Braun, Vanessa Dehn, Gerhard Hellstern, Matthias Hüls, Yanjun Ji, Ilia Polian, Amandeep Singh Bhatia, and Thomas Wellens, "Benchmarking the performance of portfolio optimization with QAOA", Quantum Information Processing 22 1, 25 (2022).

[8] Teague Tomesh, Zain H. Saleem, Michael A. Perlin, Pranav Gokhale, Martin Suchara, and Margaret Martonosi, 2023 IEEE International Conference on Quantum Computing and Engineering (QCE) 1 (2023) ISBN:979-8-3503-4323-6.

[9] Debbie Lim and Patrick Rebentrost, "A quantum online portfolio optimization algorithm", Quantum Information Processing 23 3, 63 (2024).

[10] Zichang He, Ruslan Shaydulin, Shouvanik Chakrabarti, Dylan Herman, Changhao Li, Yue Sun, and Marco Pistoia, "Alignment between initial state and mixer improves QAOA performance for constrained optimization", npj Quantum Information 9 1, 121 (2023).

[11] Dylan Herman, Ruslan Shaydulin, Yue Sun, Shouvanik Chakrabarti, Shaohan Hu, Pierre Minssen, Arthur Rattew, Romina Yalovetzky, and Marco Pistoia, "Constrained optimization via quantum Zeno dynamics", Communications Physics 6 1, 219 (2023).

[12] Ioannis Kolotouros and Petros Wallden, "Evolving objective function for improved variational quantum optimization", Physical Review Research 4 2, 023225 (2022).

[13] T. Bennett, E. Matwiejew, S. Marsh, and J. B. Wang, "Quantum Walk-Based Vehicle Routing Optimisation", Frontiers in Physics 9, 730856 (2021).

[14] Ginés Carrascal, Paula Hernamperez, Guillermo Botella, and Alberto del Barrio, "Backtesting Quantum Computing Algorithms for Portfolio Optimization", IEEE Transactions on Quantum Engineering 5, 1 (2024).

[15] Edric Matwiejew, Jason Pye, and Jingbo B Wang, "Quantum optimisation for continuous multivariable functions by a structured search", Quantum Science and Technology 8 4, 045013 (2023).

[16] Yehui Tang, Junchi Yan, Guoqiang Hu, Baohua Zhang, and Jinzan Zhou, "Recent progress and perspectives on quantum computing for finance", Service Oriented Computing and Applications 16 4, 227 (2022).

[17] Justus Shunza, Mary Akinyemi, and Chika Yinka-Banjo, "Application of quantum computing in discrete portfolio optimization", Journal of Management Science and Engineering 8 4, 453 (2023).

[18] Yue Ruan, Zhiqiang Yuan, Xiling Xue, and Zhihao Liu, "Quantum approximate optimization for combinatorial problems with constraints", Information Sciences 619, 98 (2023).

[19] 薛鹏 Xue Peng and 王坤坤 Wang Kunkun, " 量子行走", Acta Optica Sinica 44 2, 0200001 (2024).

[20] Aranya Bhattacharya, Himanshu Sahu, Ahmadullah Zahed, and Kallol Sen, "Complexity for one-dimensional discrete-time quantum walk circuits", Physical Review A 109 2, 022223 (2024).

[21] Sanjeet Swaroop Panda, P. A. Ameen Yasir, and C. M. Chandrashekar, "Quantum direct communication protocol using recurrence in k -cycle quantum walks", Physical Review A 107 2, 022611 (2023).

[22] Tavis Bennett, Edric Matwiejew, Sam Marsh, and Jingbo B. Wang, "Quantum walk-based vehicle routing optimisation", arXiv:2109.14907, (2021).

The above citations are from Crossref's cited-by service (last updated successfully 2024-07-15 16:56:12) and SAO/NASA ADS (last updated successfully 2024-07-15 16:56:13). The list may be incomplete as not all publishers provide suitable and complete citation data.