Quantum walk-based portfolio optimisation

N. Slate; E. Matwiejew; S. Marsh; J. B. Wang

doi:10.22331/q-2021-07-28-513

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

Published:	2021-07-28, volume 5, page 513
Eprint:	arXiv:2011.08057v3
Doi:	https://doi.org/10.22331/q-2021-07-28-513
Citation:	Quantum 5, 513 (2021).

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.

Featured image: The historic and projected expected returns for an optimised financial portfolio using the quantum walk-based optimisation algorithm.

► BibTeX data

@article{Slate2021quantumwalkbased,
  doi = {10.22331/q-2021-07-28-513},
  url = {https://doi.org/10.22331/q-2021-07-28-513},
  title = {Quantum walk-based portfolio optimisation},
  author = {Slate, N. and Matwiejew, E. and Marsh, S. and Wang, J. B.},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {5},
  pages = {513},
  month = jul,
  year = {2021}
}

► 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] 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).

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

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

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

[5] 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).

[6] 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).

[7] 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).

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

[9] 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).

[10] 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).

[11] 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 2023-09-21 23:10:52) and SAO/NASA ADS (last updated successfully 2023-09-21 23:10:53). The list may be incomplete as not all publishers provide suitable and complete citation data.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.