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.
Featured image: The historic and projected expected returns for an optimised financial portfolio using the quantum walk-based optimisation algorithm.
► 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
Could not fetch Crossref cited-by data during last attempt 2021-07-28 10:24:54: Could not fetch cited-by data for 10.22331/q-2021-07-28-513 from Crossref. This is normal if the DOI was registered recently. On SAO/NASA ADS no data on citing works was found (last attempt 2021-07-28 10:24:55).
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.
PlatoAi. Web3 Reimagined. Data Intelligence Amplified.
Click here to access.
Source: https://quantum-journal.org/papers/q-2021-07-28-513/
