{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T02:50:41Z","timestamp":1780368641834,"version":"3.54.1"},"reference-count":34,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2020,8,13]],"date-time":"2020-08-13T00:00:00Z","timestamp":1597276800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>We study the practical performance of quantum-inspired algorithms for recommendation systems and linear systems of equations. These algorithms were shown to have an exponential asymptotic speedup compared to previously known classical methods for problems involving low-rank matrices, but with complexity bounds that exhibit a hefty polynomial overhead compared to quantum algorithms. This raised the question of whether these methods were actually useful in practice. We conduct a theoretical analysis aimed at identifying their computational bottlenecks, then implement and benchmark the algorithms on a variety of problems, including applications to portfolio optimization and movie recommendations. On the one hand, our analysis reveals that the performance of these algorithms is better than the theoretical complexity bounds would suggest. On the other hand, their performance as seen in our implementation degrades noticeably as the rank and condition number of the input matrix are increased. Overall, our results indicate that quantum-inspired algorithms can perform well in practice provided that stringent conditions are met: low rank, low condition number, and very large dimension of the input matrix. By contrast, practical datasets are often sparse and high-rank, precisely the type that can be handled by quantum algorithms.<\/jats:p>","DOI":"10.22331\/q-2020-08-13-307","type":"journal-article","created":{"date-parts":[[2020,8,13]],"date-time":"2020-08-13T04:55:47Z","timestamp":1597294547000},"page":"307","source":"Crossref","is-referenced-by-count":91,"title":["Quantum-inspired algorithms in practice"],"prefix":"10.22331","volume":"4","author":[{"given":"Juan Miguel","family":"Arrazola","sequence":"first","affiliation":[{"name":"Xanadu, Toronto, Ontario, M5G 2C8, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alain","family":"Delgado","sequence":"additional","affiliation":[{"name":"Xanadu, Toronto, Ontario, M5G 2C8, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bhaskar Roy","family":"Bardhan","sequence":"additional","affiliation":[{"name":"Xanadu, Toronto, Ontario, M5G 2C8, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Seth","family":"Lloyd","sequence":"additional","affiliation":[{"name":"Xanadu, Toronto, Ontario, M5G 2C8, Canada"},{"name":"Massachusetts Institute of Technology, Department of Mechanical Engineering, 77 Massachusetts Avenue, Cambridge, Massachusetts 02139, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"9598","published-online":{"date-parts":[[2020,8,13]]},"reference":[{"key":"0","unstructured":"Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, and John Wright. Beating the random assignment on constraint satisfaction problems of bounded degree. arXiv:1505.03424, 2015. URL https:\/\/arxiv.org\/abs\/1505.03424."},{"key":"1","doi-asserted-by":"publisher","unstructured":"Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd. Quantum machine learning. Nature, 549 (7671): 195, 2017. 10.1038\/nature23474.","DOI":"10.1038\/nature23474"},{"key":"2","doi-asserted-by":"publisher","unstructured":"L Chakhmakhchyan, NJ Cerf, and R Garcia-Patron. Quantum-inspired algorithm for estimating the permanent of positive semidefinite matrices. Physical Review A, 96 (2): 022329, 2017. 10.1103\/PhysRevA.96.022329.","DOI":"10.1103\/PhysRevA.96.022329"},{"key":"3","unstructured":"Nai-Hui Chia, Han-Hsuan Lin, and Chunhao Wang. Quantum-inspired sublinear classical algorithms for solving low-rank linear systems. arXiv:1811.04852, 2018. URL https:\/\/arxiv.org\/abs\/1811.04852."},{"key":"4","unstructured":"Nai-Hui Chia, Tongyang Li, Han-Hsuan Lin, and Chunhao Wang. Quantum-inspired classical sublinear-time algorithm for solving low-rank semidefinite programming via sampling approaches. arXiv:1901.03254, 2019. URL https:\/\/arxiv.org\/abs\/1901.03254."},{"key":"5","doi-asserted-by":"publisher","unstructured":"AV Abs da Cruz, Marley Maria Bernardes Rebuzzi Vellasco, and Marco Aur\u00e9lio Cavalcanti Pacheco. Quantum-inspired evolutionary algorithm for numerical optimization. In Hybrid evolutionary algorithms, pages 19\u201337. Springer, 2007. 10.1007\/978-3-540-73297-6_2.","DOI":"10.1007\/978-3-540-73297-6_2"},{"key":"6","doi-asserted-by":"publisher","unstructured":"Yogesh Dahiya, Dimitris Konomis, and David P Woodruff. An empirical evaluation of sketching for numerical linear algebra. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 1292\u20131300. ACM, 2018. 10.1145\/3219819.3220098.","DOI":"10.1145\/3219819.3220098"},{"key":"7","doi-asserted-by":"publisher","unstructured":"Petros Drineas, Ravi Kannan, and Michael W Mahoney. Fast monte carlo algorithms for matrices ii: Computing a low-rank approximation to a matrix. SIAM Journal on computing, 36 (1): 158\u2013183, 2006. 10.1137\/S0097539704442696.","DOI":"10.1137\/S0097539704442696"},{"key":"8","doi-asserted-by":"publisher","unstructured":"Alan Frieze, Ravi Kannan, and Santosh Vempala. Fast monte-carlo algorithms for finding low-rank approximations. Journal of the ACM (JACM), 51 (6): 1025\u20131041, 2004. 10.1145\/1039488.1039494.","DOI":"10.1145\/1039488.1039494"},{"key":"9","unstructured":"Andr\u00e1s Gily\u00e9n, Seth Lloyd, and Ewin Tang. Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension. arXiv:1811.04909, 2018. URL https:\/\/arxiv.org\/abs\/1811.04909."},{"key":"10","doi-asserted-by":"publisher","unstructured":"Nathan Halko, Per-Gunnar Martinsson, and Joel A Tropp. Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions. SIAM review, 53 (2): 217\u2013288, 2011. 10.1137\/090771806.","DOI":"10.1137\/090771806"},{"key":"11","doi-asserted-by":"publisher","unstructured":"Kuk-Hyun Han and Jong-Hwan Kim. Quantum-inspired evolutionary algorithm for a class of combinatorial optimization. IEEE transactions on evolutionary computation, 6 (6): 580\u2013593, 2002. 10.1109\/TEVC.2002.804320.","DOI":"10.1109\/TEVC.2002.804320"},{"key":"12","doi-asserted-by":"publisher","unstructured":"F Maxwell Harper and Joseph A Konstan. The movielens datasets: History and context. ACM Transactions on Interactive Intelligent Systems (TIIS), 5 (4): 19, 2016. 10.1145\/2827872.","DOI":"10.1145\/2827872"},{"key":"13","doi-asserted-by":"publisher","unstructured":"Aram W Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for linear systems of equations. Physical Review Letters, 103 (15): 150502, 2009. 10.1103\/PhysRevLett.103.150502.","DOI":"10.1103\/PhysRevLett.103.150502"},{"key":"14","doi-asserted-by":"publisher","unstructured":"Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-SAT. Journal of Computer and System Sciences, 62 (2): 367\u2013375, 2001. 10.1006\/jcss.2000.1727.","DOI":"10.1006\/jcss.2000.1727"},{"key":"15","unstructured":"Iordanis Kerenidis and Anupam Prakash. Quantum recommendation systems. arXiv:1603.08675, 2016. URL https:\/\/arxiv.org\/abs\/1603.08675."},{"key":"16","doi-asserted-by":"publisher","unstructured":"Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. Quantum principal component analysis. Nature Physics, 10 (9): 631, 2014. 10.1038\/nphys3029.","DOI":"10.1038\/nphys3029"},{"key":"17","doi-asserted-by":"crossref","unstructured":"Harry Markowitz. Portfolio selection. The Journal of Finance, 7 (1): 77\u201391, 1952.","DOI":"10.1111\/j.1540-6261.1952.tb01525.x"},{"key":"18","doi-asserted-by":"publisher","unstructured":"Per-Gunnar Martinsson, Vladimir Rokhlin, and Mark Tygert. A randomized algorithm for the decomposition of matrices. Applied and Computational Harmonic Analysis, 30 (1): 47\u201368, 2011. 10.1016\/j.acha.2007.12.002.","DOI":"10.1016\/j.acha.2007.12.002"},{"key":"19","doi-asserted-by":"publisher","unstructured":"Ajit Narayanan and Mark Moore. Quantum-inspired genetic algorithms. In Evolutionary Computation, 1996., Proceedings of IEEE International Conference on, pages 61\u201366. IEEE, 1996. 10.1109\/ICEC.1996.542334.","DOI":"10.1109\/ICEC.1996.542334"},{"key":"20","unstructured":"Cam Nugent. S and P 500 stock data. 2018. URL https:\/\/www.kaggle.com\/camnugent\/sandp500."},{"key":"21","unstructured":"Patrick Rebentrost and Seth Lloyd. Quantum computational finance: quantum algorithm for portfolio optimization. arXiv:1811.03975, 2018. URL https:\/\/arxiv.org\/abs\/1811.03975."},{"key":"22","doi-asserted-by":"publisher","unstructured":"Patrick Rebentrost, Masoud Mohseni, and Seth Lloyd. Quantum support vector machine for big data classification. Physical Review Letters, 113 (13): 130503, 2014. 10.1103\/PhysRevLett.113.130503.","DOI":"10.1103\/PhysRevLett.113.130503"},{"key":"23","doi-asserted-by":"publisher","unstructured":"Vladimir Rokhlin and Mark Tygert. A fast randomized algorithm for overdetermined linear least-squares regression. Proceedings of the National Academy of Sciences, 105 (36): 13212\u201313217, 2008. 10.1073\/pnas.0804869105.","DOI":"10.1073\/pnas.0804869105"},{"key":"24","doi-asserted-by":"publisher","unstructured":"Vladimir Rokhlin, Arthur Szlam, and Mark Tygert. A randomized algorithm for principal component analysis. SIAM Journal on Matrix Analysis and Applications, 31 (3): 1100\u20131124, 2009. 10.1137\/080736417.","DOI":"10.1137\/080736417"},{"key":"25","doi-asserted-by":"publisher","unstructured":"Troels F R\u00f8nnow, Zhihui Wang, Joshua Job, Sergio Boixo, Sergei V Isakov, David Wecker, John M Martinis, Daniel A Lidar, and Matthias Troyer. Defining and detecting quantum speedup. Science, 345 (6195): 420\u2013424, 2014. 10.1126\/science.1252319.","DOI":"10.1126\/science.1252319"},{"key":"26","doi-asserted-by":"publisher","unstructured":"Tamas Sarlos. Improved approximation algorithms for large matrices via random projections. In Foundations of Computer Science, 2006. FOCS'06. 47th Annual IEEE Symposium on, pages 143\u2013152. IEEE, 2006. 10.1109\/FOCS.2006.37.","DOI":"10.1109\/FOCS.2006.37"},{"key":"27","doi-asserted-by":"publisher","unstructured":"Jianhong Shen. On the singular values of Gaussian random matrices. Linear Algebra and its Applications, 326 (1): 1 \u2013 14, 2001. ISSN 0024-3795. 10.1016\/S0024-3795(00)00322-0.","DOI":"10.1016\/S0024-3795(00)00322-0"},{"key":"28","doi-asserted-by":"publisher","unstructured":"Allan Sly and Nike Sun. The computational hardness of counting in two-spin models on d-regular graphs. In Foundations of Computer Science (FOCS), 2012 IEEE 53rd Annual Symposium on, pages 361\u2013369. IEEE, 2012. 10.1109\/FOCS.2012.56.","DOI":"10.1109\/FOCS.2012.56"},{"key":"29","unstructured":"Ewin Tang. Quantum-inspired classical algorithms for principal component analysis and supervised clustering. arXiv:1811.00414, 2018. URL https:\/\/arxiv.org\/abs\/1811.00414."},{"key":"30","doi-asserted-by":"publisher","unstructured":"Ewin Tang. A quantum-inspired classical algorithm for recommendation systems. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 217\u2013228, 2019. 10.1145\/3313276.3316310.","DOI":"10.1145\/3313276.3316310"},{"key":"31","doi-asserted-by":"publisher","unstructured":"Leslie G Valiant. Holographic algorithms. SIAM Journal on Computing, 37 (5): 1565\u20131594, 2008. 10.1137\/070682575.","DOI":"10.1137\/070682575"},{"key":"32","doi-asserted-by":"publisher","unstructured":"David P Woodruff et al. Sketching as a tool for numerical linear algebra. Foundations and Trends\u00ae in Theoretical Computer Science, 10 (1\u20132): 1\u2013157, 2014. 10.1561\/0400000060.","DOI":"10.1561\/0400000060"},{"key":"33","doi-asserted-by":"publisher","unstructured":"Franco Woolfe, Edo Liberty, Vladimir Rokhlin, and Mark Tygert. A fast randomized algorithm for the approximation of matrices. Applied and Computational Harmonic Analysis, 25 (3): 335\u2013366, 2008. 10.1016\/j.acha.2007.12.002.","DOI":"10.1016\/j.acha.2007.12.002"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2020-08-13-307\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,8,13]],"date-time":"2020-08-13T04:55:58Z","timestamp":1597294558000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2020-08-13-307\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,13]]},"references-count":34,"URL":"https:\/\/doi.org\/10.22331\/q-2020-08-13-307","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,8,13]]},"article-number":"307"}}