Even after decades of quantum computing development, examples of generally useful quantum algorithms with exponential speedups over classical counterparts are scarce. Recent progress in quantum algorithms for linear-algebra positioned quantum machine learning (QML) as a potential source of such useful exponential improvements. Yet, in an unexpected development, a recent series of "dequantization" results has equally rapidly removed the promise of exponential speedups for several QML algorithms. This raises the critical question whether exponential speedups of other linear-algebraic QML algorithms persist. In this paper, we study the quantum-algorithmic methods behind the algorithm for topological data analysis of Lloyd, Garnerone and Zanardi through this lens. We provide evidence that the problem solved by this algorithm is classically intractable by showing that its natural generalization is as hard as simulating the one clean qubit model – which is widely believed to require superpolynomial time on a classical computer – and is thus very likely immune to dequantizations. Based on this result, we provide a number of new quantum algorithms for problems such as rank estimation and complex network analysis, along with complexity-theoretic evidence for their classical intractability. Furthermore, we analyze the suitability of the proposed quantum algorithms for near-term implementations. Our results provide a number of useful applications for full-blown, and restricted quantum computers with a guaranteed exponential speedup over classical methods, recovering some of the potential for linear-algebraic QML to become one of quantum computing's killer applications.
Motivated by these events we address the vital question: can we show that certain linear-algebraic quantum machine learning methods are immune to such dequantizations, and offer guaranteed and useful quantum speedups? We provide strong evidence to the affirmative.
We study the linear-algebraic methods underlying the quantum algorithm for topological data analysis and provide complexity-theoretic evidence that these methods are as hard as simulating the one clean qubit model – which is widely believed to be beyond the reach of classical computers – and are thus very likely immune to dequantizations. Building on these results, we provide new quantum algorithms for an important problem in machine learning called ‘rank estimation’ and for methods in ‘complex network analysis’, all of which achieve exponential speedups over classical methods, with similar theoretical guarantees.
Our work identifies a family of possibly useful quantum algorithms which can be a basis of near- and far-term quantum killer applications.
 Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd. ``Quantum machine learning''. Nature 549, 195–202 (2017). arXiv:1611.09347.
 Aram W Harrow, Avinatan Hassidim, and Seth Lloyd. ``Quantum algorithm for linear systems of equations''. Physical review letters 103, 150502 (2009). arXiv:0811.3171.
 Vojtěch Havlíček, Antonio D Córcoles, Kristan Temme, Aram W Harrow, Abhinav Kandala, Jerry M Chow, and Jay M Gambetta. ``Supervised learning with quantum-enhanced feature spaces''. Nature 567, 209–212 (2019). arXiv:1804.11326.
 Maria Schuld, Alex Bocharov, Krysta M Svore, and Nathan Wiebe. ``Circuit-centric quantum classifiers''. Physical Review A 101, 032308 (2020). arXiv:1804.00633.
 Marcello Benedetti, Erika Lloyd, Stefan Sack, and Mattia Fiorentini. ``Parameterized quantum circuits as machine learning models''. Quantum Science and Technology 4, 043001 (2019). arXiv:1906.07682.
 Ewin Tang. ``A quantum-inspired classical algorithm for recommendation systems''. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (2019). arXiv:1807.04271.
 Nai-Hui Chia, András Gilyén, Tongyang Li, Han-Hsuan Lin, Ewin Tang, and Chunhao Wang. ``Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning''. Proceedings of the 52nd Annual ACM SIGACT symposium on theory of computing (2020). arXiv:1910.06151.
 Iordanis Kerenidis and Anupam Prakash. ``Quantum recommendation systems''. Proceedings of the 8th Innovations in Theoretical Computer Science Conference (2017). arXiv:1603.08675.
 Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. ``Quantum principal component analysis''. Nature Physics 10, 631–633 (2014). arXiv:1307.0401.
 Ryan Babbush, Jarrod McClean, Craig Gidney, Sergio Boixo, and Hartmut Neven. ``Focus beyond quadratic speedups for error-corrected quantum advantage''. Physical review X Quantum (2021). arXiv:2011.04149.
 Seth Lloyd, Silvano Garnerone, and Paolo Zanardi. ``Quantum algorithms for topological and geometric analysis of data''. Nature communications 7, 1–7 (2016). arXiv:1408.3106.
 Kiya W Govek, Venkata S Yamajala, and Pablo G Camara. ``Clustering-independent analysis of genomic data using spectral simplicial theory''. PLoS computational biology (2019).
 Guang Hao Low and Isaac L Chuang. ``Optimal hamiltonian simulation by quantum signal processing''. Physical review letters 118, 010501 (2017). arXiv:1606.02685.
 Timothy E Goldberg. ``Combinatorial laplacians of simplicial complexes''. Master's thesis. Bard College. (2002).
 Anna Gundert and May Szedláky. ``Higher dimensional discrete Cheeger inequalities''. Proceedings of the 13th annual symposium on Computational Geometry (2014). arXiv:1401.2290.
 Jianer Chen, Xiuzhen Huang, Iyad A Kanj, and Ge Xia. ``Strong computational lower bounds via parameterized complexity''. Journal of Computer and System Sciences 72, 1346–1367 (2006).
 Brielin Brown, Steven T Flammia, and Norbert Schuch. ``Computational difficulty of computing the density of states''. Physical review letters (2011). arXiv:1010.3060.
 Michał Adamaszek and Juraj Stacho. ``Complexity of simplicial homology and independence complexes of chordal graphs''. Computational Geometry 57, 8–18 (2016).
 András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. ``Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics''. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (2019). arXiv:1806.01838.
 Emanuel Knill and Raymond Laflamme. ``Power of one bit of quantum information''. Physical Review Letters (1998). arXiv:quant-ph/9802037.
 Peter W Shor and Stephen P Jordan. ``Estimating Jones polynomials is a complete problem for one clean qubit''. Quantum Information & Computation 8, 681–714 (2008). arXiv:0707.2831.
 Tomoyuki Morimae. ``Hardness of classically sampling the one-clean-qubit model with constant total variation distance error''. Physical Review A (2017). arXiv:1704.03640.
 Tomoyuki Morimae, Keisuke Fujii, and Joseph F Fitzsimons. ``Hardness of classically simulating the one-clean-qubit model''. Physical review letters (2014). arXiv:1312.2496.
 Chris Cade and Ashley Montanaro. ``The quantum complexity of computing Schatten $ p $-norms''. 13th Conference on the Theory of Quantum Computation, Communication and Cryptography (2018). arXiv:1706.09279.
 Andrew M Childs, David Gosset, and Zak Webb. ``The Bose-Hubbard model is QMA-complete''. International Colloquium on Automata, Languages, and Programming (2014). arXiv:1311.3297.
 Bryan O'Gorman, Sandy Irani, James Whitfield, and Bill Fefferman. ``Electronic structure in a fixed basis is qma-complete''. Physical review X Quantum (2021). arXiv:2103.08215.
 Danijela Horak and Jürgen Jost. ``Spectra of combinatorial Laplace operators on simplicial complexes''. Advances in Mathematics 244, 303–336 (2013). arXiv:1105.2712.
 Rui Wang, Duc Duy Nguyen, and Guo-Wei Wei. ``Persistent spectral graph''. International journal for numerical methods in biomedical engineering 36, e3376 (2020). arXiv:1912.04135.
 Hamed Ahmadi and Pawel Wocjan. ``On the quantum complexity of evaluating the Tutte polynomial''. Journal of Knot Theory and its Ramifications 19, 727–737 (2010).
 Shashanka Ubaru, Yousef Saad, and Abd-Krim Seghouane. ``Fast estimation of approximate matrix ranks using spectral densities''. Neural computation 29, 1317–1351 (2017). arXiv:1608.05754.
 Ho Yee Cheung, Tsz Chiu Kwok, and Lap Chi Lau. ``Fast matrix rank algorithms and applications''. Journal of the ACM (JACM) 60, 1–25 (2013). arXiv:1203.6705.
 Edoardo Di Napoli, Eric Polizzi, and Yousef Saad. ``Efficient estimation of eigenvalue counts in an interval''. Numerical Linear Algebra with Applications 23, 674–692 (2016). arXiv:1308.4275.
 David Cohen-Steiner, Weihao Kong, Christian Sohler, and Gregory Valiant. ``Approximating the spectrum of a graph''. Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (2018). arXiv:1712.01725.
 Sayan Mukherjee and John Steenbergen. ``Random walks on simplicial complexes and harmonics''. Random structures & algorithms 49, 379–405 (2016). arXiv:1310.5099.
 Ori Parzanchevski and Ron Rosenthal. ``Simplicial complexes: spectrum, homology and random walks''. Random Structures & Algorithms 50, 225–261 (2017). arXiv:1211.6775.
 J.W. Moon and Moser L. ``On a problem of turan''. Publ. Math. Inst. Hung. Acad. Sci. (1962).
 Johan Ugander, Lars Backstrom, and Jon Kleinberg. ``Subgraph frequencies: Mapping the empirical and extremal geography of large graph collections''. Proceedings of the 22nd international conference on World Wide Web (2013). arXiv:1304.1548.
 Talya Eden, Dana Ron, and Will Rosenbaum. ``Almost Optimal Bounds for Sublinear-Time Sampling of k-Cliques in Bounded Arboricity Graphs''. 49th International Colloquium on Automata, Languages, and Programming – ICALP (2022). arXiv:2012.04090.
 Nathan Halko, Per-Gunnar Martinsson, and Joel A Tropp. ``Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions''. SIAM review 53, 217–288 (2011). arXiv:0909.4061.
 Iordanis Kerenidis and Anupam Prakash. ``Quantum gradient descent for linear systems and least squares''. Physical Review A 101, 022316 (2020). arXiv:1704.04992.
 Shantanav Chakraborty, András Gilyén, and Stacey Jeffery. ``The power of block-encoded matrix powers: Improved regression techniques via faster hamiltonian simulation''. 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) (2019). arXiv:1804.01973.
 Braxton Osting, Sourabh Palande, and Bei Wang. ``Spectral sparsification of simplicial complexes for clustering and label propagation''. Journal of Computational Geometry (2017). arXiv:1708.08436.
 Art Duval, Caroline Klivans, and Jeremy Martin. ``Simplicial matrix-tree theorems''. Transactions of the American Mathematical Society 361, 6073–6114 (2009). arXiv:0802.2576.
 András Gilyén and Tongyang Li. ``Distributional property testing in a quantum world''. 11th Innovations in Theoretical Computer Science Conference (ITCS 2020) (2020). arXiv:1902.00814.
 Jacob Biamonte, Mauro Faccin, and Manlio De Domenico. ``Complex networks from classical to quantum''. Communications Physics 2, 1–10 (2019). arXiv:1702.08459.
 Manlio De Domenico and Jacob Biamonte. ``Spectral entropies as information-theoretic tools for complex network comparison''. Physical Review X 6 (2016). arXiv:1609.01214.
 Filippo Passerini and Simone Severini. ``Quantifying complexity in networks: the von Neumann entropy''. International Journal of Agent Technologies and Systems (IJATS) 1, 58–67 (2009). arXiv:0812.2597.
 David Simmons, Justin Coon, and Animesh Datta. ``The quantum Theil index: characterizing graph centralization using von Neumann entropy''. Journal of Complex Networks 6, 859–876 (2018). arXiv:1707.07906.
 Slobodan Maletić and Milan Rajković. ``Combinatorial Laplacian and entropy of simplicial complexes associated with complex networks''. The European Physical Journal Special Topics 212, 77–97 (2012).
 Jayadev Acharya, Ibrahim Issa, Nirmal V Shende, and Aaron B Wagner. ``Measuring quantum entropy''. 2019 IEEE International Symposium on Information Theory (ISIT) (2019). arXiv:1711.00814.
 Gregory Valiant and Paul Valiant. ``Estimating the unseen: an n/log(n)-sample estimator for entropy and support size, shown optimal via new clts''. Proceedings of the forty-third annual ACM symposium on Theory of computing (2011).
 Jayadev Acharya, Alon Orlitsky, Ananda Theertha Suresh, and Himanshu Tyagi. ``Estimating rényi entropy of discrete distributions''. IEEE Transactions on Information Theory 63, 38–56 (2016). arXiv:1408.1000.
 Sathyawageeswar Subramanian and Min-Hsiu Hsieh. ``Quantum algorithm for estimating renyi entropies of quantum states''. Physical review A (2021). arXiv:1908.05251.
 Bela Bauer, Sergey Bravyi, Mario Motta, and Garnet Kin Chan. ``Quantum algorithms for quantum chemistry and quantum materials science''. Chemical Reviews 120, 12685–12717 (2020). arXiv:2001.03685.
 Kristan Temme, Sergey Bravyi, and Jay M Gambetta. ``Error mitigation for short-depth quantum circuits''. Physical review letters (2017). arXiv:1612.02058.
 Xavi Bonet-Monroig, Ramiro Sagastizabal, M Singh, and TE O'Brien. ``Low-cost error mitigation by symmetry verification''. Physical Review A (2018). arXiv:1807.10050.
 Suguru Endo, Simon C Benjamin, and Ying Li. ``Practical quantum error mitigation for near-future applications''. Physical Review X (2018). arXiv:1712.09271.
 Sam McArdle, Xiao Yuan, and Simon Benjamin. ``Error-mitigated digital quantum simulation''. Physical review letters (2019). arXiv:1807.02467.
 Thomas E O'Brien, Stefano Polla, Nicholas C Rubin, William J Huggins, Sam McArdle, Sergio Boixo, Jarrod R McClean, and Ryan Babbush. ``Error mitigation via verified phase estimation''. Physical review X Quantum (2021). arXiv:2010.02538.
 Shashanka Ubaru, Ismail Yunus Akhalwaya, Mark S Squillante, Kenneth L Clarkson, and Lior Horesh. ``Quantum topological data analysis with linear depth and exponential speedup'' (2021). arXiv:2108.02811.
 Dominic W Berry, Andrew M Childs, and Robin Kothari. ``Hamiltonian simulation with nearly optimal dependence on all parameters''. Proceedings of 56th Annual Symposium on Foundations of Computer Science (2015). arXiv:1501.01715.
 Alicja Dutkiewicz, Barbara M Terhal, and Thomas E O'Brien. ``Heisenberg-limited quantum phase estimation of multiple eigenvalues with a single control qubit'' (2021). arXiv:2107.04605.
 Thomas E. O'Brien, Brian Tarasinski, and Barbara Terhal. ``Quantum phase estimation of multiple eigenvalues for small-scale (noisy) experiments''. New Journal of Physics (2019). arXiv:1809.09697.
 He-Liang Huang, Xi-Lin Wang, Peter P Rohde, Yi-Han Luo, You-Wei Zhao, Chang Liu, Li Li, Nai-Le Liu, Chao-Yang Lu, and Jian-Wei Pan. ``Demonstration of topological data analysis on a quantum processor''. Optica 5, 193–198 (2018). arXiv:1801.06316.
 Dylan Herman, Cody Googin, Xiaoyuan Liu, Alexey Galda, Ilya Safro, Yue Sun, Marco Pistoia, and Yuri Alexeev, "A Survey of Quantum Computing for Finance", arXiv:2201.02773.
 Alexander Schmidhuber and Seth Lloyd, "Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis", arXiv:2209.14286.
 Dominic W. Berry, Yuan Su, Casper Gyurik, Robbie King, Joao Basso, Alexander Del Toro Barba, Abhishek Rajput, Nathan Wiebe, Vedran Dunjko, and Ryan Babbush, "Quantifying Quantum Advantage in Topological Data Analysis", arXiv:2209.13581.
 Ismail Yunus Akhalwaya, Yang-Hui He, Lior Horesh, Vishnu Jejjala, William Kirby, Kugendran Naidoo, and Shashanka Ubaru, "Representation of the Fermionic Boundary Operator", arXiv:2201.11510.
 Nai-Hui Chia, András Gilyén, Tongyang Li, Han-Hsuan Lin, Ewin Tang, and Chunhao Wang, "Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning", arXiv:1910.06151.
 Shashanka Ubaru, Ismail Yunus Akhalwaya, Mark S. Squillante, Kenneth L. Clarkson, and Lior Horesh, "Quantum Topological Data Analysis with Linear Depth and Exponential Speedup", arXiv:2108.02811.
 Ryu Hayakawa, "Quantum algorithm for persistent Betti numbers and topological data analysis", arXiv:2111.00433.
 Chris Cade and P. Marcos Crichigno, "Complexity of Supersymmetric Systems and the Cohomology Problem", arXiv:2107.00011.
 Sam McArdle, András Gilyén, and Mario Berta, "A streamlined quantum algorithm for topological data analysis with exponentially fewer qubits", arXiv:2209.12887.
 A. Hamann, V. Dunjko, and S. Wölk, "Quantum-accessible reinforcement learning beyond strictly epochal environments", arXiv:2008.01481.
 Marcos Crichigno and Tamara Kohler, "Clique Homology is QMA1-hard", arXiv:2209.11793.
 Andrew Vlasic and Anh Pham, "Understanding the Mapping of Encode Data Through An Implementation of Quantum Topological Analysis", arXiv:2209.10596.
The above citations are from SAO/NASA ADS (last updated successfully 2022-11-30 04:35:43). The list may be incomplete as not all publishers provide suitable and complete citation data.
On Crossref's cited-by service no data on citing works was found (last attempt 2022-11-30 04:35:41).
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.