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
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] 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.
[2] Alexander Schmidhuber and Seth Lloyd, “Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis”, arXiv:2209.14286.
[3] 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.
[4] 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.
[5] 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.
[6] 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.
[7] Ryu Hayakawa, “Quantum algorithm for persistent Betti numbers and topological data analysis”, arXiv:2111.00433.
[8] Chris Cade and P. Marcos Crichigno, “Complexity of Supersymmetric Systems and the Cohomology Problem”, arXiv:2107.00011.
[9] Sam McArdle, András Gilyén, and Mario Berta, “A streamlined quantum algorithm for topological data analysis with exponentially fewer qubits”, arXiv:2209.12887.
[10] A. Hamann, V. Dunjko, and S. Wölk, “Quantum-accessible reinforcement learning beyond strictly epochal environments”, arXiv:2008.01481.
[11] Marcos Crichigno and Tamara Kohler, “Clique Homology is QMA1-hard”, arXiv:2209.11793.
[12] 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-11 15:16:04). 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-11 15:16:02).
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.
