{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,17]],"date-time":"2026-06-17T01:43:13Z","timestamp":1781660593023,"version":"3.54.5"},"reference-count":85,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2022,11,10]],"date-time":"2022-11-10T00:00:00Z","timestamp":1668038400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100003246","name":"Dutch Research Council","doi-asserted-by":"crossref","award":["Quantum Software Consortium (project number 024.003.037)"],"award-info":[{"award-number":["Quantum Software Consortium (project number 024.003.037)"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100020314","name":"QuantERA","doi-asserted-by":"crossref","award":["QuantAlgo 680-91-034"],"award-info":[{"award-number":["QuantAlgo 680-91-034"]}],"id":[{"id":"10.13039\/501100020314","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"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 \u2013 which is widely believed to require superpolynomial time on a classical computer \u2013 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&apos;s killer applications.<\/jats:p>","DOI":"10.22331\/q-2022-11-10-855","type":"journal-article","created":{"date-parts":[[2022,11,10]],"date-time":"2022-11-10T15:19:28Z","timestamp":1668093568000},"page":"855","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":37,"title":["Towards quantum advantage via topological data analysis"],"prefix":"10.22331","volume":"6","author":[{"given":"Casper","family":"Gyurik","sequence":"first","affiliation":[{"name":"LIACS, Leiden University, Niels Bohrweg 1, 2333 CA Leiden, Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chris","family":"Cade","sequence":"additional","affiliation":[{"name":"QuSoft, Centrum Wiskunde & Informatica (CWI), Science Park 123, 1098 XG Amsterdam, Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vedran","family":"Dunjko","sequence":"additional","affiliation":[{"name":"LIACS, Leiden University, Niels Bohrweg 1, 2333 CA Leiden, Netherlands"},{"name":"LION, Leiden University, Niels Bohrweg 2, 2333 CA Leiden, Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"9598","published-online":{"date-parts":[[2022,11,10]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Vedran Dunjko and Peter Wittek. ``A non-review of quantum machine learning: trends and explorations''. Quantum 4, 32 (2020).","DOI":"10.22331\/qv-2020-03-17-32"},{"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, 195\u2013202 (2017). arXiv:1611.09347.","DOI":"10.1038\/nature23474"},{"key":"2","doi-asserted-by":"publisher","unstructured":"Aram W Harrow, Avinatan Hassidim, and Seth Lloyd. ``Quantum algorithm for linear systems of equations''. Physical review letters 103, 150502 (2009). arXiv:0811.3171.","DOI":"10.1103\/PhysRevLett.103.150502"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Vojt\u011bch Havl\u00ed\u010dek, Antonio D C\u00f3rcoles, Kristan Temme, Aram W Harrow, Abhinav Kandala, Jerry M Chow, and Jay M Gambetta. ``Supervised learning with quantum-enhanced feature spaces''. Nature 567, 209\u2013212 (2019). arXiv:1804.11326.","DOI":"10.1038\/s41586-019-0980-2"},{"key":"4","doi-asserted-by":"publisher","unstructured":"Maria Schuld, Alex Bocharov, Krysta M Svore, and Nathan Wiebe. ``Circuit-centric quantum classifiers''. Physical Review A 101, 032308 (2020). arXiv:1804.00633.","DOI":"10.1103\/PhysRevA.101.032308"},{"key":"5","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1088\/2058-9565\/ab4eb5"},{"key":"6","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1145\/3313276.3316310"},{"key":"7","doi-asserted-by":"publisher","unstructured":"Nai-Hui Chia, Andr\u00e1s Gily\u00e9n, 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.","DOI":"10.1145\/3357713.3384314"},{"key":"8","doi-asserted-by":"publisher","unstructured":"Iordanis Kerenidis and Anupam Prakash. ``Quantum recommendation systems''. Proceedings of the 8th Innovations in Theoretical Computer Science Conference (2017). arXiv:1603.08675.","DOI":"10.4230\/LIPIcs.ITCS.2017.49"},{"key":"9","doi-asserted-by":"publisher","unstructured":"Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. ``Quantum principal component analysis''. Nature Physics 10, 631\u2013633 (2014). arXiv:1307.0401.","DOI":"10.1038\/nphys3029"},{"key":"10","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PRXQuantum.2.010103"},{"key":"11","doi-asserted-by":"publisher","unstructured":"Seth Lloyd, Silvano Garnerone, and Paolo Zanardi. ``Quantum algorithms for topological and geometric analysis of data''. Nature communications 7, 1\u20137 (2016). arXiv:1408.3106.","DOI":"10.1038\/ncomms10138"},{"key":"12","doi-asserted-by":"publisher","unstructured":"John Preskill. ``Quantum computing in the NISQ era and beyond''. Quantum 2, 79 (2018). arXiv:1801.00862.","DOI":"10.22331\/q-2018-08-06-79"},{"key":"13","doi-asserted-by":"publisher","unstructured":"Robert Ghrist. ``Barcodes: the persistent topology of data''. Bulletin of the American Mathematical Society 45, 61\u201375 (2008).","DOI":"10.1090\/S0273-0979-07-01191-3"},{"key":"14","doi-asserted-by":"publisher","unstructured":"Beno Eckmann. ``Harmonische Funktionen und Randwertaufgaben in einem Komplex''. Commentarii Mathematici Helvetici 17, 240\u2013255 (1944).","DOI":"10.1007\/BF02566245"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Joel Friedman. ``Computing Betti numbers via combinatorial Laplacians''. Algorithmica 21, 331\u2013346 (1998).","DOI":"10.1007\/PL00009218"},{"key":"16","doi-asserted-by":"publisher","unstructured":"Kiya W Govek, Venkata S Yamajala, and Pablo G Camara. ``Clustering-independent analysis of genomic data using spectral simplicial theory''. PLoS computational biology (2019).","DOI":"10.1371\/journal.pcbi.1007509"},{"key":"17","unstructured":"Sam Gunn and Niels Kornerup. ``Review of a quantum algorithm for Betti numbers'' (2019). arXiv:1906.07673."},{"key":"18","doi-asserted-by":"publisher","unstructured":"Guang Hao Low and Isaac L Chuang. ``Optimal hamiltonian simulation by quantum signal processing''. Physical review letters 118, 010501 (2017). arXiv:1606.02685.","DOI":"10.1103\/PhysRevLett.118.010501"},{"key":"19","unstructured":"Timothy E Goldberg. ``Combinatorial laplacians of simplicial complexes''. Master's thesis. Bard College. (2002)."},{"key":"20","doi-asserted-by":"publisher","unstructured":"Michael A. Nielsen and Isaac L. Chuang. ``Quantum computation and quantum information''. Cambridge University Press. (2011).","DOI":"10.1017\/CBO9780511976667"},{"key":"21","doi-asserted-by":"publisher","unstructured":"Anna Gundert and May Szedl\u00e1ky. ``Higher dimensional discrete Cheeger inequalities''. Proceedings of the 13th annual symposium on Computational Geometry (2014). arXiv:1401.2290.","DOI":"10.1145\/2582112.2582118"},{"key":"22","doi-asserted-by":"publisher","unstructured":"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\u20131367 (2006).","DOI":"10.1016\/j.jcss.2006.04.007"},{"key":"23","doi-asserted-by":"publisher","unstructured":"Fernando GSL Brand\u00e3o. ``Entanglement theory and the quantum simulation of many-body physics''. PhD thesis. University of London. (2008).","DOI":"10.48550\/arXiv.0810.0026"},{"key":"24","unstructured":"Pawel Wocjan and Shengyu Zhang. ``Several natural BQP-complete problems'' (2006). arXiv:quant-ph\/0606179."},{"key":"25","doi-asserted-by":"publisher","unstructured":"Brielin Brown, Steven T Flammia, and Norbert Schuch. ``Computational difficulty of computing the density of states''. Physical review letters (2011). arXiv:1010.3060.","DOI":"10.1103\/PhysRevLett.107.040501"},{"key":"26","doi-asserted-by":"publisher","unstructured":"Micha\u0142 Adamaszek and Juraj Stacho. ``Complexity of simplicial homology and independence complexes of chordal graphs''. Computational Geometry 57, 8\u201318 (2016).","DOI":"10.1016\/j.comgeo.2016.05.003"},{"key":"27","doi-asserted-by":"publisher","unstructured":"Andr\u00e1s Gily\u00e9n, 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.","DOI":"10.1145\/3313276.3316366"},{"key":"28","doi-asserted-by":"publisher","unstructured":"Alexei Yu Kitaev, Alexander Shen, Mikhail N Vyalyi, and Mikhail N Vyalyi. ``Classical and quantum computation''. American Mathematical Society. (2002).","DOI":"10.1090\/gsm\/047"},{"key":"29","doi-asserted-by":"publisher","unstructured":"Emanuel Knill and Raymond Laflamme. ``Power of one bit of quantum information''. Physical Review Letters (1998). arXiv:quant-ph\/9802037.","DOI":"10.1103\/PhysRevLett.81.5672"},{"key":"30","doi-asserted-by":"publisher","unstructured":"Peter W Shor and Stephen P Jordan. ``Estimating Jones polynomials is a complete problem for one clean qubit''. Quantum Information & Computation 8, 681\u2013714 (2008). arXiv:0707.2831.","DOI":"10.48660\/07100034"},{"key":"31","doi-asserted-by":"publisher","unstructured":"Tomoyuki Morimae. ``Hardness of classically sampling the one-clean-qubit model with constant total variation distance error''. Physical Review A (2017). arXiv:1704.03640.","DOI":"10.1103\/PhysRevA.96.040302"},{"key":"32","doi-asserted-by":"publisher","unstructured":"Tomoyuki Morimae, Keisuke Fujii, and Joseph F Fitzsimons. ``Hardness of classically simulating the one-clean-qubit model''. Physical review letters (2014). arXiv:1312.2496.","DOI":"10.1103\/PhysRevLett.112.130502"},{"key":"33","doi-asserted-by":"publisher","unstructured":"Seth Lloyd. ``Universal quantum simulators''. SciencePages 1073\u20131078 (1996).","DOI":"10.1126\/science.273.5278.1073"},{"key":"34","unstructured":"Chris Cade and P Marcos Crichigno. ``Complexity of supersymmetric systems and the cohomology problem'' (2021). arXiv:2107.00011."},{"key":"35","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.4230\/LIPIcs.TQC.2018.4"},{"key":"36","doi-asserted-by":"publisher","unstructured":"Adam D Bookatz. ``Qma-complete problems''. Quantum Information & Computation 14, 361\u2013383 (2014). arXiv:1212.6312.","DOI":"10.26421\/QIC14.5-6-1"},{"key":"37","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1007\/978-3-662-43948-7_26"},{"key":"38","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PRXQuantum.3.020322"},{"key":"39","doi-asserted-by":"publisher","unstructured":"Danijela Horak and J\u00fcrgen Jost. ``Spectra of combinatorial Laplace operators on simplicial complexes''. Advances in Mathematics 244, 303\u2013336 (2013). arXiv:1105.2712.","DOI":"10.1016\/j.aim.2013.05.007"},{"key":"40","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1002\/cnm.3376"},{"key":"41","doi-asserted-by":"publisher","unstructured":"Hamed Ahmadi and Pawel Wocjan. ``On the quantum complexity of evaluating the Tutte polynomial''. Journal of Knot Theory and its Ramifications 19, 727\u2013737 (2010).","DOI":"10.1142\/S021821651000808X"},{"key":"42","doi-asserted-by":"publisher","unstructured":"Shashanka Ubaru, Yousef Saad, and Abd-Krim Seghouane. ``Fast estimation of approximate matrix ranks using spectral densities''. Neural computation 29, 1317\u20131351 (2017). arXiv:1608.05754.","DOI":"10.1162\/NECO_a_00951"},{"key":"43","doi-asserted-by":"publisher","unstructured":"Ho Yee Cheung, Tsz Chiu Kwok, and Lap Chi Lau. ``Fast matrix rank algorithms and applications''. Journal of the ACM (JACM) 60, 1\u201325 (2013). arXiv:1203.6705.","DOI":"10.1145\/2528404"},{"key":"44","doi-asserted-by":"publisher","unstructured":"Edoardo Di Napoli, Eric Polizzi, and Yousef Saad. ``Efficient estimation of eigenvalue counts in an interval''. Numerical Linear Algebra with Applications 23, 674\u2013692 (2016). arXiv:1308.4275.","DOI":"10.1002\/nla.2048"},{"key":"45","doi-asserted-by":"publisher","unstructured":"Lin Lin, Yousef Saad, and Chao Yang. ``Approximating spectral densities of large matrices''. SIAM review 58, 34\u201365 (2016). arXiv:1308.5467.","DOI":"10.1137\/130934283"},{"key":"46","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1145\/3219819.3220119"},{"key":"47","doi-asserted-by":"publisher","unstructured":"Sayan Mukherjee and John Steenbergen. ``Random walks on simplicial complexes and harmonics''. Random structures & algorithms 49, 379\u2013405 (2016). arXiv:1310.5099.","DOI":"10.1002\/rsa.20645"},{"key":"48","doi-asserted-by":"publisher","unstructured":"Ori Parzanchevski and Ron Rosenthal. ``Simplicial complexes: spectrum, homology and random walks''. Random Structures & Algorithms 50, 225\u2013261 (2017). arXiv:1211.6775.","DOI":"10.1002\/rsa.20657"},{"key":"49","doi-asserted-by":"publisher","unstructured":"Christian Reiher. ``The clique density theorem''. Annals of Mathematics (2016). arXiv:1212.2454.","DOI":"10.4007\/annals.2016.184.3.1"},{"key":"50","unstructured":"J.W. Moon and Moser L. ``On a problem of turan''. Publ. Math. Inst. Hung. Acad. Sci. (1962)."},{"key":"51","doi-asserted-by":"publisher","unstructured":"L\u00e1szl\u00f3 Lov\u00e1sz et al. ``Very large graphs''. Current Developments in Mathematics 2008, 67\u2013128 (2009). arXiv:0902.0132.","DOI":"10.4310\/CDM.2008.v2008.n1.a2"},{"key":"52","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1145\/2488388.2488502"},{"key":"53","doi-asserted-by":"publisher","unstructured":"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 \u2013 ICALP (2022). arXiv:2012.04090.","DOI":"10.4230\/LIPIcs.ICALP.2022.56"},{"key":"54","doi-asserted-by":"publisher","unstructured":"Ian T Jolliffe. ``Principal components in regression analysis''. Pages 129\u2013155. Springer. (1986).","DOI":"10.1007\/978-1-4757-1904-8_8"},{"key":"55","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, 217\u2013288 (2011). arXiv:0909.4061.","DOI":"10.1137\/090771806"},{"key":"56","doi-asserted-by":"publisher","unstructured":"Iordanis Kerenidis and Anupam Prakash. ``Quantum gradient descent for linear systems and least squares''. Physical Review A 101, 022316 (2020). arXiv:1704.04992.","DOI":"10.1103\/PhysRevA.101.022316"},{"key":"57","doi-asserted-by":"publisher","unstructured":"Shantanav Chakraborty, Andr\u00e1s Gily\u00e9n, 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.","DOI":"10.4230\/LIPIcs.ICALP.2019.33"},{"key":"58","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.20382\/jocg.v11i1a8"},{"key":"59","doi-asserted-by":"publisher","unstructured":"Art Duval, Caroline Klivans, and Jeremy Martin. ``Simplicial matrix-tree theorems''. Transactions of the American Mathematical Society 361, 6073\u20136114 (2009). arXiv:0802.2576.","DOI":"10.1090\/S0002-9947-09-04898-3"},{"key":"60","doi-asserted-by":"publisher","unstructured":"Andr\u00e1s Gily\u00e9n and Tongyang Li. ``Distributional property testing in a quantum world''. 11th Innovations in Theoretical Computer Science Conference (ITCS 2020) (2020). arXiv:1902.00814.","DOI":"10.4230\/LIPIcs.ITCS.2020.25"},{"key":"61","doi-asserted-by":"publisher","unstructured":"Jacob Biamonte, Mauro Faccin, and Manlio De Domenico. ``Complex networks from classical to quantum''. Communications Physics 2, 1\u201310 (2019). arXiv:1702.08459.","DOI":"10.1038\/s42005-019-0152-6"},{"key":"62","doi-asserted-by":"publisher","unstructured":"Manlio De Domenico and Jacob Biamonte. ``Spectral entropies as information-theoretic tools for complex network comparison''. Physical Review X 6 (2016). arXiv:1609.01214.","DOI":"10.1103\/PhysRevX.6.041062"},{"key":"63","doi-asserted-by":"publisher","unstructured":"Filippo Passerini and Simone Severini. ``Quantifying complexity in networks: the von Neumann entropy''. International Journal of Agent Technologies and Systems (IJATS) 1, 58\u201367 (2009). arXiv:0812.2597.","DOI":"10.4018\/jats.2009071005"},{"key":"64","doi-asserted-by":"publisher","unstructured":"David Simmons, Justin Coon, and Animesh Datta. ``The quantum Theil index: characterizing graph centralization using von Neumann entropy''. Journal of Complex Networks 6, 859\u2013876 (2018). arXiv:1707.07906.","DOI":"10.1093\/COMNET\/CNX061"},{"key":"65","doi-asserted-by":"publisher","unstructured":"Slobodan Maleti\u0107 and Milan Rajkovi\u0107. ``Combinatorial Laplacian and entropy of simplicial complexes associated with complex networks''. The European Physical Journal Special Topics 212, 77\u201397 (2012).","DOI":"10.1140\/epjst\/e2012-01655-6"},{"key":"66","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1109\/ISIT.2019.8849572"},{"key":"67","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1145\/1993636.1993727"},{"key":"68","doi-asserted-by":"publisher","unstructured":"Jayadev Acharya, Alon Orlitsky, Ananda Theertha Suresh, and Himanshu Tyagi. ``Estimating r\u00e9nyi entropy of discrete distributions''. IEEE Transactions on Information Theory 63, 38\u201356 (2016). arXiv:1408.1000.","DOI":"10.1109\/TIT.2016.2620435"},{"key":"69","doi-asserted-by":"publisher","unstructured":"Sathyawageeswar Subramanian and Min-Hsiu Hsieh. ``Quantum algorithm for estimating renyi entropies of quantum states''. Physical review A (2021). arXiv:1908.05251.","DOI":"10.1103\/PhysRevA.104.022428"},{"key":"70","doi-asserted-by":"publisher","unstructured":"Bela Bauer, Sergey Bravyi, Mario Motta, and Garnet Kin Chan. ``Quantum algorithms for quantum chemistry and quantum materials science''. Chemical Reviews 120, 12685\u201312717 (2020). arXiv:2001.03685.","DOI":"10.1021\/acs.chemrev.9b00829"},{"key":"71","doi-asserted-by":"publisher","unstructured":"Kristan Temme, Sergey Bravyi, and Jay M Gambetta. ``Error mitigation for short-depth quantum circuits''. Physical review letters (2017). arXiv:1612.02058.","DOI":"10.1103\/PhysRevLett.119.180509"},{"key":"72","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevA.98.062339"},{"key":"73","doi-asserted-by":"publisher","unstructured":"Suguru Endo, Simon C Benjamin, and Ying Li. ``Practical quantum error mitigation for near-future applications''. Physical Review X (2018). arXiv:1712.09271.","DOI":"10.1103\/PhysRevX.8.031027"},{"key":"74","doi-asserted-by":"publisher","unstructured":"Sam McArdle, Xiao Yuan, and Simon Benjamin. ``Error-mitigated digital quantum simulation''. Physical review letters (2019). arXiv:1807.02467.","DOI":"10.1103\/PhysRevLett.122.180501"},{"key":"75","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PRXQuantum.2.020317"},{"key":"76","unstructured":"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."},{"key":"77","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1145\/3313276.3316386"},{"key":"78","unstructured":"Mathys Rennela, Alfons Laarman, and Vedran Dunjko. ``Hybrid divide-and-conquer approach for tree search algorithms'' (2020). arXiv:2007.07040."},{"key":"79","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.22331\/q-2022-10-06-830"},{"key":"80","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1088\/1367-2630\/aafb8e"},{"key":"81","doi-asserted-by":"publisher","unstructured":"Rolando D Somma. ``Quantum eigenvalue estimation via time series analysis''. New Journal of Physics (2019). arXiv:1907.11748.","DOI":"10.1088\/1367-2630\/ab5c60"},{"key":"82","doi-asserted-by":"publisher","unstructured":"Tosio Kato. ``Perturbation theory for linear operators''. Volume 132. Springer Science & Business Media. (2013).","DOI":"10.1007\/978-3-642-66282-9"},{"key":"83","doi-asserted-by":"publisher","unstructured":"Xinlong Feng and Zhinan Zhang. ``The rank of a random matrix''. Applied mathematics and computation 185, 689\u2013694 (2007).","DOI":"10.1016\/j.amc.2006.07.076"},{"key":"84","doi-asserted-by":"publisher","unstructured":"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\u2013198 (2018). arXiv:1801.06316.","DOI":"10.1364\/OPTICA.5.000193"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2022-11-10-855\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2022,11,10]],"date-time":"2022-11-10T15:19:40Z","timestamp":1668093580000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2022-11-10-855\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,10]]},"references-count":85,"URL":"https:\/\/doi.org\/10.22331\/q-2022-11-10-855","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,11,10]]},"article-number":"855"}}