Towards quantum advantage via topological data analysis
1LIACS, Leiden University, Niels Bohrweg 1, 2333 CA Leiden, Netherlands
2QuSoft, Centrum Wiskunde & Informatica (CWI), Science Park 123, 1098 XG Amsterdam, Netherlands
3LION, Leiden University, Niels Bohrweg 2, 2333 CA Leiden, Netherlands
| Published: | 2022-11-10, volume 6, page 855 |
| Eprint: | arXiv:2005.02607v5 |
| Doi: | https://doi.org/10.22331/q-2022-11-10-855 |
| Citation: | Quantum 6, 855 (2022). |
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
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.
Featured image: Example of a clique complex with three 1-dimensional holes (adapted from Robert Ghrist. “Barcodes: the persistent topology of data” in Bulletin of the American Mathematical Society 2008). The number of these holes is equal to the first Betti number.
Popular summary
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.
► BibTeX data
► References
[1] Vedran Dunjko and Peter Wittek. ``A non-review of quantum machine learning: trends and explorations''. Quantum 4, 32 (2020).
https://doi.org/10.22331/qv-2020-03-17-32
[2] Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd. ``Quantum machine learning''. Nature 549, 195–202 (2017). arXiv:1611.09347.
https://doi.org/10.1038/nature23474
arXiv:1611.09347
[3] Aram W Harrow, Avinatan Hassidim, and Seth Lloyd. ``Quantum algorithm for linear systems of equations''. Physical review letters 103, 150502 (2009). arXiv:0811.3171.
https://doi.org/10.1103/PhysRevLett.103.150502
arXiv:0811.3171
[4] 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.
https://doi.org/10.1038/s41586-019-0980-2
arXiv:1804.11326
[5] Maria Schuld, Alex Bocharov, Krysta M Svore, and Nathan Wiebe. ``Circuit-centric quantum classifiers''. Physical Review A 101, 032308 (2020). arXiv:1804.00633.
https://doi.org/10.1103/PhysRevA.101.032308
arXiv:1804.00633
[6] 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.
https://doi.org/10.1088/2058-9565/ab4eb5
arXiv:1906.07682
[7] 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.
https://doi.org/10.1145/3313276.3316310
arXiv:1807.04271
[8] 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.
https://doi.org/10.1145/3357713.3384314
arXiv:1910.06151
[9] Iordanis Kerenidis and Anupam Prakash. ``Quantum recommendation systems''. Proceedings of the 8th Innovations in Theoretical Computer Science Conference (2017). arXiv:1603.08675.
https://doi.org/10.4230/LIPIcs.ITCS.2017.49
arXiv:1603.08675
[10] Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. ``Quantum principal component analysis''. Nature Physics 10, 631–633 (2014). arXiv:1307.0401.
https://doi.org/10.1038/nphys3029
arXiv:1307.0401
[11] 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.
https://doi.org/10.1103/PRXQuantum.2.010103
arXiv:2011.04149
[12] 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.
https://doi.org/10.1038/ncomms10138
arXiv:1408.3106
[13] John Preskill. ``Quantum computing in the NISQ era and beyond''. Quantum 2, 79 (2018). arXiv:1801.00862.
https://doi.org/10.22331/q-2018-08-06-79
arXiv:1801.00862
[14] Robert Ghrist. ``Barcodes: the persistent topology of data''. Bulletin of the American Mathematical Society 45, 61–75 (2008).
https://doi.org/10.1090/S0273-0979-07-01191-3
[15] Beno Eckmann. ``Harmonische Funktionen und Randwertaufgaben in einem Komplex''. Commentarii Mathematici Helvetici 17, 240–255 (1944).
https://doi.org/10.1007/BF02566245
[16] Joel Friedman. ``Computing Betti numbers via combinatorial Laplacians''. Algorithmica 21, 331–346 (1998).
https://doi.org/10.1007/PL00009218
[17] Kiya W Govek, Venkata S Yamajala, and Pablo G Camara. ``Clustering-independent analysis of genomic data using spectral simplicial theory''. PLoS computational biology (2019).
https://doi.org/10.1371/journal.pcbi.1007509
[18] Sam Gunn and Niels Kornerup. ``Review of a quantum algorithm for Betti numbers'' (2019). arXiv:1906.07673.
arXiv:1906.07673
[19] Guang Hao Low and Isaac L Chuang. ``Optimal hamiltonian simulation by quantum signal processing''. Physical review letters 118, 010501 (2017). arXiv:1606.02685.
https://doi.org/10.1103/PhysRevLett.118.010501
arXiv:1606.02685
[20] Timothy E Goldberg. ``Combinatorial laplacians of simplicial complexes''. Master's thesis. Bard College. (2002).
[21] Michael A. Nielsen and Isaac L. Chuang. ``Quantum computation and quantum information''. Cambridge University Press. (2011).
https://doi.org/10.1017/CBO9780511976667
[22] Anna Gundert and May Szedláky. ``Higher dimensional discrete Cheeger inequalities''. Proceedings of the 13th annual symposium on Computational Geometry (2014). arXiv:1401.2290.
https://doi.org/10.1145/2582112.2582118
arXiv:1401.2290
[23] 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).
https://doi.org/10.1016/j.jcss.2006.04.007
[24] Fernando GSL Brandão. ``Entanglement theory and the quantum simulation of many-body physics''. PhD thesis. University of London. (2008).
https://doi.org/10.48550/arXiv.0810.0026
[25] Pawel Wocjan and Shengyu Zhang. ``Several natural BQP-complete problems'' (2006). arXiv:quant-ph/0606179.
arXiv:quant-ph/0606179
[26] Brielin Brown, Steven T Flammia, and Norbert Schuch. ``Computational difficulty of computing the density of states''. Physical review letters (2011). arXiv:1010.3060.
https://doi.org/10.1103/PhysRevLett.107.040501
arXiv:1010.3060
[27] Michał Adamaszek and Juraj Stacho. ``Complexity of simplicial homology and independence complexes of chordal graphs''. Computational Geometry 57, 8–18 (2016).
https://doi.org/10.1016/j.comgeo.2016.05.003
[28] 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.
https://doi.org/10.1145/3313276.3316366
arXiv:1806.01838
[29] Alexei Yu Kitaev, Alexander Shen, Mikhail N Vyalyi, and Mikhail N Vyalyi. ``Classical and quantum computation''. American Mathematical Society. (2002).
https://doi.org/10.1090/gsm/047
[30] Emanuel Knill and Raymond Laflamme. ``Power of one bit of quantum information''. Physical Review Letters (1998). arXiv:quant-ph/9802037.
https://doi.org/10.1103/PhysRevLett.81.5672
arXiv:quant-ph/9802037
[31] 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.
https://doi.org/10.48660/07100034
arXiv:0707.2831
[32] Tomoyuki Morimae. ``Hardness of classically sampling the one-clean-qubit model with constant total variation distance error''. Physical Review A (2017). arXiv:1704.03640.
https://doi.org/10.1103/PhysRevA.96.040302
arXiv:1704.03640
[33] Tomoyuki Morimae, Keisuke Fujii, and Joseph F Fitzsimons. ``Hardness of classically simulating the one-clean-qubit model''. Physical review letters (2014). arXiv:1312.2496.
https://doi.org/10.1103/PhysRevLett.112.130502
arXiv:1312.2496
[34] Seth Lloyd. ``Universal quantum simulators''. SciencePages 1073–1078 (1996).
https://doi.org/10.1126/science.273.5278.1073
[35] Chris Cade and P Marcos Crichigno. ``Complexity of supersymmetric systems and the cohomology problem'' (2021). arXiv:2107.00011.
arXiv:2107.00011
[36] 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.
https://doi.org/10.4230/LIPIcs.TQC.2018.4
arXiv:1706.09279
[37] Adam D Bookatz. ``Qma-complete problems''. Quantum Information & Computation 14, 361–383 (2014). arXiv:1212.6312.
https://doi.org/10.26421/QIC14.5-6-1
arXiv:1212.6312
[38] 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.
https://doi.org/10.1007/978-3-662-43948-7_26
arXiv:1311.3297
[39] 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.
https://doi.org/10.1103/PRXQuantum.3.020322
arXiv:2103.08215
[40] Danijela Horak and Jürgen Jost. ``Spectra of combinatorial Laplace operators on simplicial complexes''. Advances in Mathematics 244, 303–336 (2013). arXiv:1105.2712.
https://doi.org/10.1016/j.aim.2013.05.007
arXiv:1105.2712
[41] 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.
https://doi.org/10.1002/cnm.3376
arXiv:1912.04135
[42] 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).
https://doi.org/10.1142/S021821651000808X
[43] 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.
https://doi.org/10.1162/NECO_a_00951
arXiv:1608.05754
[44] 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.
https://doi.org/10.1145/2528404
arXiv:1203.6705
[45] 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.
https://doi.org/10.1002/nla.2048
arXiv:1308.4275
[46] Lin Lin, Yousef Saad, and Chao Yang. ``Approximating spectral densities of large matrices''. SIAM review 58, 34–65 (2016). arXiv:1308.5467.
https://doi.org/10.1137/130934283
arXiv:1308.5467
[47] 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.
https://doi.org/10.1145/3219819.3220119
arXiv:1712.01725
[48] Sayan Mukherjee and John Steenbergen. ``Random walks on simplicial complexes and harmonics''. Random structures & algorithms 49, 379–405 (2016). arXiv:1310.5099.
https://doi.org/10.1002/rsa.20645
arXiv:1310.5099
[49] Ori Parzanchevski and Ron Rosenthal. ``Simplicial complexes: spectrum, homology and random walks''. Random Structures & Algorithms 50, 225–261 (2017). arXiv:1211.6775.
https://doi.org/10.1002/rsa.20657
arXiv:1211.6775
[50] Christian Reiher. ``The clique density theorem''. Annals of Mathematics (2016). arXiv:1212.2454.
https://doi.org/10.4007/annals.2016.184.3.1
arXiv:1212.2454
[51] J.W. Moon and Moser L. ``On a problem of turan''. Publ. Math. Inst. Hung. Acad. Sci. (1962).
[52] László Lovász et al. ``Very large graphs''. Current Developments in Mathematics 2008, 67–128 (2009). arXiv:0902.0132.
https://doi.org/10.4310/CDM.2008.v2008.n1.a2
arXiv:0902.0132
[53] 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.
https://doi.org/10.1145/2488388.2488502
arXiv:1304.1548
[54] 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.
https://doi.org/10.4230/LIPIcs.ICALP.2022.56
arXiv:2012.04090
[55] Ian T Jolliffe. ``Principal components in regression analysis''. Pages 129–155. Springer. (1986).
https://doi.org/10.1007/978-1-4757-1904-8_8
[56] 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.
https://doi.org/10.1137/090771806
arXiv:0909.4061
[57] Iordanis Kerenidis and Anupam Prakash. ``Quantum gradient descent for linear systems and least squares''. Physical Review A 101, 022316 (2020). arXiv:1704.04992.
https://doi.org/10.1103/PhysRevA.101.022316
arXiv:1704.04992
[58] 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.
https://doi.org/10.4230/LIPIcs.ICALP.2019.33
arXiv:1804.01973
[59] 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.
https://doi.org/10.20382/jocg.v11i1a8
arXiv:1708.08436
[60] Art Duval, Caroline Klivans, and Jeremy Martin. ``Simplicial matrix-tree theorems''. Transactions of the American Mathematical Society 361, 6073–6114 (2009). arXiv:0802.2576.
https://doi.org/10.1090/S0002-9947-09-04898-3
arXiv:0802.2576
[61] 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.
https://doi.org/10.4230/LIPIcs.ITCS.2020.25
arXiv:1902.00814
[62] Jacob Biamonte, Mauro Faccin, and Manlio De Domenico. ``Complex networks from classical to quantum''. Communications Physics 2, 1–10 (2019). arXiv:1702.08459.
https://doi.org/10.1038/s42005-019-0152-6
arXiv:1702.08459
[63] Manlio De Domenico and Jacob Biamonte. ``Spectral entropies as information-theoretic tools for complex network comparison''. Physical Review X 6 (2016). arXiv:1609.01214.
https://doi.org/10.1103/PhysRevX.6.041062
arXiv:1609.01214
[64] 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.
https://doi.org/10.4018/jats.2009071005
arXiv:0812.2597
[65] 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.
https://doi.org/10.1093/COMNET/CNX061
arXiv:1707.07906
[66] 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).
https://doi.org/10.1140/epjst/e2012-01655-6
[67] 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.
https://doi.org/10.1109/ISIT.2019.8849572
arXiv:1711.00814
[68] 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).
https://doi.org/10.1145/1993636.1993727
[69] 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.
https://doi.org/10.1109/TIT.2016.2620435
arXiv:1408.1000
[70] Sathyawageeswar Subramanian and Min-Hsiu Hsieh. ``Quantum algorithm for estimating renyi entropies of quantum states''. Physical review A (2021). arXiv:1908.05251.
https://doi.org/10.1103/PhysRevA.104.022428
arXiv:1908.05251
[71] 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.
https://doi.org/10.1021/acs.chemrev.9b00829
arXiv:2001.03685
[72] Kristan Temme, Sergey Bravyi, and Jay M Gambetta. ``Error mitigation for short-depth quantum circuits''. Physical review letters (2017). arXiv:1612.02058.
https://doi.org/10.1103/PhysRevLett.119.180509
arXiv:1612.02058
[73] 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.
https://doi.org/10.1103/PhysRevA.98.062339
arXiv:1807.10050
[74] Suguru Endo, Simon C Benjamin, and Ying Li. ``Practical quantum error mitigation for near-future applications''. Physical Review X (2018). arXiv:1712.09271.
https://doi.org/10.1103/PhysRevX.8.031027
arXiv:1712.09271
[75] Sam McArdle, Xiao Yuan, and Simon Benjamin. ``Error-mitigated digital quantum simulation''. Physical review letters (2019). arXiv:1807.02467.
https://doi.org/10.1103/PhysRevLett.122.180501
arXiv:1807.02467
[76] 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.
https://doi.org/10.1103/PRXQuantum.2.020317
arXiv:2010.02538
[77] 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.
arXiv:2108.02811
[78] 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.
https://doi.org/10.1145/3313276.3316386
arXiv:1501.01715
[79] Mathys Rennela, Alfons Laarman, and Vedran Dunjko. ``Hybrid divide-and-conquer approach for tree search algorithms'' (2020). arXiv:2007.07040.
arXiv:2007.07040
[80] 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.
https://doi.org/10.22331/q-2022-10-06-830
arXiv:2107.04605
[81] 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.
https://doi.org/10.1088/1367-2630/aafb8e
arXiv:1809.09697
[82] Rolando D Somma. ``Quantum eigenvalue estimation via time series analysis''. New Journal of Physics (2019). arXiv:1907.11748.
https://doi.org/10.1088/1367-2630/ab5c60
arXiv:1907.11748
[83] Tosio Kato. ``Perturbation theory for linear operators''. Volume 132. Springer Science & Business Media. (2013).
https://doi.org/10.1007/978-3-642-66282-9
[84] Xinlong Feng and Zhinan Zhang. ``The rank of a random matrix''. Applied mathematics and computation 185, 689–694 (2007).
https://doi.org/10.1016/j.amc.2006.07.076
[85] 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.
https://doi.org/10.1364/OPTICA.5.000193
arXiv:1801.06316
Cited by
[1] Chenghong Zhu, Hongshun Yao, Yingjian Liu, and Xin Wang, "Optimizer-dependent generalization bound for quantum neural networks", Quantum Machine Intelligence 7 2, 92 (2025).
[2] Dániel T. R. Nagy, Csaba Czabán, Bence Bakó, Péter Hága, Zsófia Kallus, and Zoltán Zimborás, "Hybrid quantum-classical reinforcement learning in latent observation spaces", Quantum Machine Intelligence 7 2, 88 (2025).
[3] Alberto Di Meglio, Karl Jansen, Ivano Tavernelli, Constantia Alexandrou, Srinivasan Arunachalam, Christian W. Bauer, Kerstin Borras, Stefano Carrazza, Arianna Crippa, Vincent Croft, Roland de Putter, Andrea Delgado, Vedran Dunjko, Daniel J. Egger, Elias Fernández-Combarro, Elina Fuchs, Lena Funcke, Daniel González-Cuadra, Michele Grossi, Jad C. Halimeh, Zoë Holmes, Stefan Kühn, Denis Lacroix, Randy Lewis, Donatella Lucchesi, Miriam Lucio Martinez, Federico Meloni, Antonio Mezzacapo, Simone Montangero, Lento Nagano, Vincent R. Pascuzzi, Voica Radescu, Enrique Rico Ortega, Alessandro Roggero, Julian Schuhmacher, Joao Seixas, Pietro Silvi, Panagiotis Spentzouris, Francesco Tacchino, Kristan Temme, Koji Terashi, Jordi Tura, Cenk Tüysüz, Sofia Vallecorsa, Uwe-Jens Wiese, Shinjae Yoo, and Jinglei Zhang, "Quantum Computing for High-Energy Physics: State of the Art and Challenges", PRX Quantum 5 3, 037001 (2024).
[4] Roberto Zucchini, "A new quantum computational set-up for algebraic topology via simplicial sets", Journal of AppliedMath 3 4, 3011 (2025).
[5] Armando Angrisani and Elham Kashefi, "Quantum Differential Privacy in the Local Model", IEEE Transactions on Information Theory 71 5, 3675 (2025).
[6] Nhat A. Nghiem, Xianfeng David Gu, and Tzu-Chieh Wei, "Quantum Algorithm for Estimating Betti Numbers Using Cohomology Approach", Quantum 9, 1955 (2025).
[7] Shaked Leibzirer and Ron Rosenthal, "Eigenvalues and spectral gap in sparse random simplicial complexes", Annales de l'Institut Henri Poincaré, Probabilités et Statistiques 61 2(2025).
[8] Caesnan M.G. Leditto, Angus Southwell, Behnam Tonekaboni, Gregory A.L. White, Muhammad Usman, and Kavan Modi, "Topological signal processing on quantum computers for higher-order network analysis", Physical Review Applied 23 5, 054054 (2025).
[9] Ankit Khandelwal and M Girish Chandra, 2023 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW) 534 (2023) ISBN:979-8-3503-1199-0.
[10] Zhiyan Ding, Lin Lin, Yilun Yang, and Ruizhe Zhang, "Quantum Filtering and Analysis of Multiplicities in Eigenvalue Spectra", PRX Quantum 7 2, 020318 (2026).
[11] Simon Apers, Sander Gribling, Sayantan Sen, and Dániel Szabó, "A (simple) classical algorithm for estimating Betti numbers", Quantum 7, 1202 (2023).
[12] Robbie King and Tamara Kohler, 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) 493 (2024) ISBN:979-8-3315-1674-1.
[13] Gennaro De Luca, Andrew Vlasic, Michael Vitz, and Anh Pham, "Empirical power of quantum encoding methods for binary classification", Quantum Machine Intelligence 7 2, 72 (2025).
[14] Chris Cade and P. Marcos Crichigno, "Complexity of Supersymmetric Systems and the Cohomology Problem", Quantum 8, 1325 (2024).
[15] Harvey Cao, Daniel Leykam, and Dimitris G. Angelakis, "Unravelling quantum chaos using persistent homology", Physical Review E 107 4, 044204 (2023).
[16] Sam McArdle, András Gilyén,, and Mario Berta, "A streamlined quantum algorithm for topological data analysis with exponentially fewer qubits", Quantum 10, 2058 (2026).
[17] Hayata Yamasaki, Natsuto Isogai, and Mio Murao, "Advantage of quantum machine learning from general computational advantages", npj Quantum Information 12 1, 125 (2026).
[18] Casper Gyurik, Alexander Schmidhuber, Robbie King, Vedran Dunjko, and Ryu Hayakawa, "Provable Quantum Speedups for Computing Persistence in Topological Data Analysis", PRX Quantum 7 2, 020361 (2026).
[19] Maxime Clenet, Maxime Dion, and F. Guillaume Blanchet, "Addressing ecological challenges from a quantum computing perspective", Methods in Ecology and Evolution 17 3, 632 (2026).
[20] Stefano Scali, Chukwudubem Umeano, and Oleksandr Kyriienko, "Quantum topological data analysis via the estimation of the density of states", Physical Review A 110 4, 042616 (2024).
[21] Dániel Szabó and Simon Apers, Lecture Notes in Computer Science 15539, 298 (2025) ISBN:978-3-031-82696-2.
[22] Massimiliano Incudini, Francesco Martini, and Alessandra Di Pierro, 2023 IEEE International Conference on Quantum Computing and Engineering (QCE) 621 (2023) ISBN:979-8-3503-4323-6.
[23] Chukwudubem Umeano, Stefano Scali, and Oleksandr Kyriienko, "Quantum community detection via deterministic elimination", Physical Review A 112 5, 052422 (2025).
[24] Aritra Bose, Kahn Rhrissorrakrai, Filippo Utro, Laxmi Parida, Saugata Basu, Jannis Born, Sara Capponi, Dimitra Chalkia, Timothy A. Chan, Hakan Doga, Frederik F. Flöther, Gad Getz, Mark Goldsmith, Tanvi Gujarati, Aldo Guzman-Saenz, Dimitrios Iliopoulos, Gavin O. Jones, Stefan Knecht, Dhiraj Madan, Sabrina Maniscalco, Nicola Mariella, Joseph A. Morrone, Khadijeh Najafi, Pushpak Pati, Daniel Platt, Maria Anna Rapsomaniki, Anupama Ray, Omar Shehab, Ivano Tavernelli, Meltem Tolunay, Stefan Woerner, Sergiy Zhuk, and Jeannette M. Garcia, "Advancing single-cell omics and cell-based therapeutics with quantum computing", Nature Reviews Molecular Cell Biology 27 5, 394 (2026).
[25] Daniel Leykam and Dimitris G. Angelakis, "Topological data analysis and machine learning", Advances in Physics: X 8 1, 2202331 (2023).
[26] Chelsea A. Williams, Annie E. Paine, Antonio A. Gentile, Daniel Berger, and Oleksandr Kyriienko, "Vortex detection from quantum data", Physical Review A 112 6, 062409 (2025).
[27] Nhat A. Nghiem, "Quantum algorithm for computing distances between subspaces", Physics Letters A 514-515, 129610 (2024).
[28] Noah L. Wach, Manuel S. Rudolph, Fred Jendrzejewski, and Sebastian Schmitt, "Data re-uploading with a single qudit", Quantum Machine Intelligence 5 2, 36 (2023).
[29] Dominic W. Berry, Yuan Su, Casper Gyurik, Robbie King, Joao Basso, Alexander Del Toro Barba, Abhishek Rajput, Nathan Wiebe, Vedran Dunjko, and Ryan Babbush, "Analyzing Prospects for Quantum Advantage in Topological Data Analysis", PRX Quantum 5 1, 010319 (2024).
[30] Ryu Hayakawa, Kuo-Chin Chen, and Min-Hsiu Hsieh, "Quantum Walks on Simplicial Complexes and Harmonic Homology: Application to Topological Data Analysis with Superpolynomial Speedups", Quantum 10, 2138 (2026).
[31] Ankit Khandelwal and M Girish Chandra, 2023 IEEE International Conference on Quantum Computing and Engineering (QCE) 10 (2023) ISBN:979-8-3503-4323-6.
[32] Stefano Scali, Chukwudubem Umeano, and Oleksandr Kyriienko, "The topology of data hides in quantum thermal states", APL Quantum 1 3, 036106 (2024).
[33] Massimiliano Incudini, Francesco Martini, and Alessandra Di Pierro, "Toward Useful Quantum Kernels", Advanced Quantum Technologies 8 12, 2300298 (2025).
[34] Marcos Crichigno and Tamara Kohler, "Clique Homology is $${{\mathsf{QMA}}}_{1}$$-hard", Nature Communications 15 1, 9846 (2024).
[35] Robbie King and Tamara Kohler, "Gapped Clique Homology on Weighted Graphs Is \({\text{QMA}_1}\)-Hard and Contained in QMA", SIAM Journal on Computing FOCS24-137 (2026).
[36] Ismail Yunus Akhalwaya, Ahmed Bhayat, Adam Connolly, Steven Herbert, Lior Horesh, Julien Sorci, and Shashanka Ubaru, "Comparing quantum and classical Monte Carlo algorithms for estimating Betti numbers of clique complexes", Quantum 9, 1901 (2025).
[37] Jonathan Z Lu, Lucy Jiao, Kristina Wolinski, Milan Kornjača, Hong-Ye Hu, Sergio Cantu, Fangli Liu, Susanne F Yelin, and Sheng-Tao Wang, "Digital–analog quantum learning on Rydberg atom arrays", Quantum Science and Technology 10 1, 015038 (2025).
[38] Malte Schade, Cyrill Bösch, Václav Hapla, and Andreas Fichtner, "A quantum computing concept for 1-D elastic wave simulation with exponential speedup", Geophysical Journal International 238 1, 321 (2024).
[39] 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, (2022).
[40] 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, (2021).
[41] Ismail Yunus Akhalwaya, Shashanka Ubaru, Kenneth L. Clarkson, Mark S. Squillante, Vishnu Jejjala, Yang-Hui He, Kugendran Naidoo, Vasileios Kalantzis, and Lior Horesh, "Topological data analysis on noisy quantum computers", arXiv:2209.09371, (2022).
[42] 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, (2019).
[43] Sam McArdle, András Gilyén, and Mario Berta, "A streamlined quantum algorithm for topological data analysis with exponentially fewer qubits", arXiv:2209.12887, (2022).
[44] Alexander Schmidhuber and Seth Lloyd, "Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis", PRX Quantum 4 4, 040349 (2023).
[45] Alexander Schmidhuber, Michele Reilly, Paolo Zanardi, Seth Lloyd, and Aaron Lauda, "A quantum algorithm for Khovanov homology", arXiv:2501.12378, (2025).
[46] Ismail Yunus Akhalwaya, Yang-Hui He, Lior Horesh, Vishnu Jejjala, William Kirby, Kugendran Naidoo, and Shashanka Ubaru, "Representation of the fermionic boundary operator", Physical Review A 106 2, 022407 (2022).
[47] Ankit Khandelwal and M Girish Chandra, "Quantum-Enhanced Topological Data Analysis: A Peep from an Implementation Perspective", arXiv:2302.09553, (2023).
[48] 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, (2022).
[49] Roberto Zucchini, "A new quantum computational set-up for algebraic topology via simplicial sets", arXiv:2309.11304, (2023).
[50] Noah L. Wach, Manuel S. Rudolph, Fred Jendrzejewski, and Sebastian Schmitt, "Data re-uploading with a single qudit", arXiv:2302.13932, (2023).
[51] A. Hamann, V. Dunjko, and S. Wölk, "Quantum-accessible reinforcement learning beyond strictly epochal environments", arXiv:2008.01481, (2020).
[52] Hiroshi Yamauchi, Satoshi Kanno, Yuki Sato, Hiroyuki Tezuka, Yoshi-aki Shimada, Eriko Kaminishi, and Naoki Yamamoto, "Quantum spectroscopy of topological dynamics via a supersymmetric Hamiltonian", arXiv:2511.23169, (2025).
[53] Andrew Vlasic and Anh Pham, "Understanding the Mapping of Encode Data Through An Implementation of Quantum Topological Analysis", arXiv:2209.10596, (2022).
[54] Evan Peters, "On the coherent extension of some Fano-type learning bounds", arXiv:2404.07277, (2024).
[55] Nhat A. Nghiem, "Quantum topological data analysis algorithm for dynamical systems", arXiv:2509.22372, (2025).
[56] Stefano Scali, Brian Coyle, Giuseppe Buonaiuto, and Michal Krompiec, "Quantum Randomized Subspace Iteration", arXiv:2604.09483, (2026).
The above citations are from Crossref's cited-by service (last updated successfully 2026-08-07 23:16:53) and SAO/NASA ADS (last updated successfully 2026-08-07 23:16:55). 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.