Quantum algorithms for topological and geometric analysis of data
Open accessAbstract
Extracting useful information from large data sets can be a daunting task. Topological methods for analysing data sets provide a powerful technique for extracting such information. Persistent homology is a sophisticated tool for identifying topological features and for determining how such features persist as the data is viewed at different scales. Here we present quantum machine learning algorithms for calculating Betti numbers—the numbers of connected components, holes and voids—in persistent homology, and for finding eigenvectors and eigenvalues of the combinatorial Laplacian. The algorithms provide an exponential speed-up over the best currently known classical algorithms for topological data analysis.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
A quantum algorithm has been proposed for persistent homology.
“A quantum algorithm has also been proposed for a particular method in topological data analysis, namely persistent homology [87].”
From The prospects of quantum computing in computational molecular biology (2021) · cites this paper as [87]
The algorithm by Lloyd et al. for persistent homology makes use of quantum phase estimation to diagonalize a matrix exponentially faster, reaching a O(N^5) complexity.
“The algorithm by Lloyd et al. also makes use of the quantum phase estimation subroutine to diagonalize a matrix exponentially faster, reaching a O N 5 ð Þ complexity.”
From The prospects of quantum computing in computational molecular biology (2021) · cites this paper as [87]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
Quantum Algorithm for Linear Systems of Equations
Harrow, A. W., Hassidim, A., & Lloyd, S. (2009) · Physical Review Letters · doi:10.1103/physrevlett.103.150502 · Cited by 3,325 · see citing works
Self-citationQuantum Support Vector Machine for Big Data Classification
Rebentrost, P., Mohseni, M., & Lloyd, S. (2014) · Physical Review Letters · doi:10.1103/physrevlett.113.130503 · Cited by 1,951 · see citing works
Self-citationTopological Persistence and Simplification
Edelsbrunner, Letscher, & Zomorodian (2002) · Discrete & Computational Geometry · doi:10.1007/s00454-002-2885-2 · Cited by 1,779 · see citing works
Zomorodian, A., & Carlsson, G. (2005) · Discrete & Computational Geometry · doi:10.1007/s00454-004-1146-y · Cited by 1,591 · see citing works
Can One Hear the Shape of a Drum?
Kac, M. (1966) · American Mathematical Monthly · doi:10.1080/00029890.1966.11970915 · Cited by 1,402 · see citing works
Quantum principal component analysis
Lloyd, S., Mohseni, M., & Rebentrost, P. (2014) · Nature Physics · doi:10.1038/nphys3029 · Cited by 1,385 · see citing works
Self-citationStability of Persistence Diagrams
Cohen-Steiner, D., Edelsbrunner, H., & Harer, J. (2007) · Discrete & Computational Geometry · doi:10.1007/s00454-006-1276-5 · Cited by 1,280 · see citing works
Barcodes: the persistent topology of data
Ghrist, R. (2007) · Bulletin of the American Mathematical Society · doi:10.1090/s0273-0979-07-01191-3 · Cited by 1,236 · cited 2× · see citing works
“The primary difference between the topological and geometrical algorithms presented here, and algorithms for, for example, constructing clusters 19 , principal components 20 , and support vector machines 21 , is that our topological algorithms require only a small qRAM of size O ( n 2 ).”
BackgroundGiovannetti, V., Lloyd, S., & Maccone, L. (2008) · Physical Review Letters · doi:10.1103/physrevlett.100.160501 · Cited by 935 · see citing works
Self-citationQuantum Algorithm Providing Exponential Speed Increase for Finding Eigenvalues and Eigenvectors
Abrams, D. S., & Lloyd, S. (1999) · Physical Review Letters · doi:10.1103/physrevlett.83.5162 · Cited by 817 · see citing works
Self-citationAaronson, S. (2015) · Nature Physics · doi:10.1038/nphys3272 · Cited by 567 · see citing works
Architectures for a quantum random access memory
Giovannetti, V., Lloyd, S., & Maccone, L. (2008) · Physical Review A · doi:10.1103/physreva.78.052310 · Cited by 306 · see citing works
Self-citationPERSISTENCE BARCODES FOR SHAPES
CARLSSON, G., ZOMORODIAN, A., COLLINS, A., & GUIBAS, L. J. (2005) · International Journal of Shape Modeling · doi:10.1142/s0218654305000761 · Cited by 287 · see citing works
The Theory and Applications of Harmonic Integrals
Hodge, W. V. D. (1989) · Cited by 279 · see citing works
Morse Theory for Filtrations and Efficient Computation of Persistent Homology
Mischaikow, K., & Nanda, V. (2013) · Discrete & Computational Geometry · doi:10.1007/s00454-013-9529-6 · Cited by 261 · see citing works
Quantum speed-up for unsupervised learning
Aı̈meur, E., Brassard, G., & Gambs, S. (2012) · Machine Learning · doi:10.1007/s10994-012-5316-5 · Cited by 212 · see citing works
Machine learning for precise quantum measurement
Hentschel, A., & Sanders, B. C. (2010) · Physical Review Letters · doi:10.1103/physrevlett.104.063603 · Cited by 197 · see citing works
A Topological View of Unsupervised Learning from Noisy Data
Niyogi, P., Smale, S. T., & Weinberger, S. (2011) · SIAM Journal on Computing · doi:10.1137/090762932 · Cited by 150 · see citing works
Quantum adiabatic machine learning
Pudenz, K. L., & Lidar, D. A. (2012) · Quantum Information Processing · doi:10.1007/s11128-012-0506-4 · Cited by 139 · see citing works
Size theory as a topological tool for computer vision
Frosini, P., & Landi, C. (1999) · Cited by 137 · see citing works
Quantum optimization for training support vector machines
Anguita, D., Ridella, S., Rivieccio, F., & Zunino, R. (2003) · Neural Networks · doi:10.1016/s0893-6080(03)00087-x · Cited by 120 · see citing works
Equivalences and Separations Between Quantum and Classical Learnability
Servedio, R. A., & Gortler, S. J. (2004) · SIAM Journal on Computing · doi:10.1137/s0097539704412910 · Cited by 118 · see citing works
On Bounding the Betti Numbers and Computing the Euler Characteristic of Semi-Algebraic Sets
Basu, S. (1999) · Discrete & Computational Geometry · doi:10.1007/pl00009443 · Cited by 106 · see citing works
Discrete Morse Theoretic Algorithms for Computing Homology of Complexes and Maps
Harker, S., Mischaikow, K., Mrożek, M., et al. (2013) · Foundations of Computational Mathematics · doi:10.1007/s10208-013-9145-0 · Cited by 88 · see citing works
Experimental quantum private queries with linear optics
De Martini, F., Giovannetti, V., Lloyd, S., Maccone, L., Nagali, E., Sansoni, L., & Sciarrino, F. (2009) · Physical Review A · doi:10.1103/physreva.80.010302 · Cited by 81 · see citing works
Self-citationStability and Computation of Topological Invariants of Solids in ${\Bbb R}^n$
Chazal, F., & Lieutier, A. (2007) · Discrete & Computational Geometry · doi:10.1007/s00454-007-1309-8 · Cited by 55 · see citing works
Combinatorial Laplacian and entropy of simplicial complexes associated with complex networks
Maletić, S., & Rajković, M. (2012) · The European Physical Journal Special Topics · doi:10.1140/epjst/e2012-01655-6 · Cited by 45 · see citing works
Computing Betti numbers via combinatorial Laplacians
Friedman, J. (1996) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/237814.237985 · Cited by 45 · see citing works
Small Spectral Gap in the Combinatorial Laplacian Implies Hamiltonian
Butler, S., & Chung, F. (2010) · Annals of Combinatorics · doi:10.1007/s00026-009-0039-4 · Cited by 41 · see citing works
Quantum support vector machine for big feature and big data classification.Preprint
Rebentrost, P., Mohseni, M., & Lloyd, S. (2013) · arXiv (Cornell University) · Cited by 39 · see citing works
Self-citationDifferent Bounds on the Different Betti Numbers of Semi-Algebraic Sets
Basu, S. (2003) · Discrete & Computational Geometry · doi:10.1007/s00454-003-2922-9 · Cited by 31 · see citing works
Scheiblechner, P. (2007) · Journal of Complexity · doi:10.1016/j.jco.2007.03.008 · Cited by 29 · see citing works
Basu, S. (2006) · Foundations of Computational Mathematics · doi:10.1007/s10208-005-0208-8 · Cited by 15 · see citing works
Quantum Computation in Computational Geometry
Sadakane, K., SUGAWARA, N., & Tokuyama, T. (2002) · Interdisciplinary Information Sciences · doi:10.4036/iis.2002.129 · Cited by 9 · see citing works
Flagged first, then by citations
Research works printed but not linked: 7
- Robins V. Towards computing homology from finite approximations. Topol. Proc. 24, 503– 532 (1999).
- Basu S. Algorithms in real algebraic geometry: a survey. Preprint at http://arxiv.org/abs/1409.1534 (2014). · arXiv
- Kozlov D. Algorithms and Computation in Mathematics Vol. 21, Springer (2008).
- Neven H., Denchev V. S., Rose G. & Macready W. G. Training a large scale classifier with the quantum adiabatic algorithm. Preprint at http://arxiv.org/abs/0912.0779 (2009). · arXiv
- Lloyd S., Mohseni M. & Rebentrost P. Quantum algorithms for supervised and unsupervised machine learning. Preprint at http://arxiv.org/abs/1307.0411 (2013). · arXiv
- Yu. Kitaev A., Shen A. H. & Vyalyi M. N. Classical and Quantum Computation, Graduate Studies in Mathematics Vol. 47, publications of the American Mathematical Society (2004).
- Nielsen M. S. & Chuang I. L. Quantum Computation and Quantum Information Cambridge University Press (2000).
Cited by
Sorted by citations
Biamonte, J., Wittek, P., Pancotti, N., Rebentrost, P., Wiebe, N., & Lloyd, S. (2017) · Nature · doi:10.1038/nature23474 · Cited by 4,779 · see citing works
Self-citationBig data in healthcare: management, analysis and future prospects
Dash, S., Shakyawar, S. K., Sharma, M., & Kaushik, S. (2019) · Journal of Big Data · doi:10.1186/s40537-019-0217-0 · Cited by 1,747 · see citing works
A Systematic Review on Supervised and Unsupervised Machine Learning Algorithms for Data Science
Alloghani, M., Al-Jumeily, D., Mustafina, J., Hussain, A., & Aljaaf, A. J. (2020) · Unsupervised and Semi-Supervised Learning · doi:10.1007/978-3-030-22475-2_1 · Cited by 702 · see citing works
A Survey on quantum computing technology
Gyongyosi, L., & Imre, S. (2019) · Computer Science Review · doi:10.1016/j.cosrev.2018.11.002 · Cited by 646 · see citing works
A rigorous and robust quantum speed-up in supervised machine learning
Liu, Y., Arunachalam, S., & Temme, K. (2021) · Nature Physics · doi:10.1038/s41567-021-01287-z · Cited by 649 · see citing works
Quantum generalisation of feedforward neural networks
Wan, K. H., Dahlsten, O., Kristjánsson, H., Gardner, R., & Kim, M. S. (2017) · npj Quantum Information · doi:10.1038/s41534-017-0032-4 · Cited by 276 · see citing works
The prospects of quantum computing in computational molecular biology
Outeiral, C., Strahm, M., Shi, J., Morris, G. M., Benjamin, S. C., & Deane, C. M. (2021) · WIREs Computational Molecular Science · doi:10.1002/wcms.1481 · Cited by 232 · see citing works
Solving nonlinear differential equations with differentiable quantum circuits
Kyriienko, O., Paine, A. E., & Elfving, V. E. (2021) · Physical Review A · doi:10.1103/physreva.103.052416 · Cited by 185 · see citing works
Pal, S., Bhattacharya, M., Lee, S.-S., & Chakraborty, C. (2024) · Molecular Biotechnology · doi:10.1007/s12033-023-00765-4 · Cited by 84 · see citing works
Advances in quantum reinforcement learning
Dunjko, V., Taylor, J. M., & Briegel, H. J. (2017) · 2017 IEEE International Conference on Systems, Man, and Cybernetics (SMC) · doi:10.1109/smc.2017.8122616 · Cited by 81 · see citing works
- Authors
- Lloyd, S., Garnerone, S., & Zanardi, P.
- Affiliations
- Massachusetts Institute of Technology (US)
- University of Waterloo (CA)
- Corresponding author
- Lloyd, Seth
- Venue
- Nature Communications
- Published
- 2016-01-25
- Volume
- 7
- Issue
- 1
- Pages
- 10138-10138
- ISSN
- 2041-1723 (ISSN-L)
- PMC
- PMC4737711
- OpenAlex
- W2266138411
- Cited by
- 241
- References
- 34
- Citations by year
- 2026: 21 · 2025: 27 · 2024: 27 · 2023: 46 · 2022: 32 · 2021: 23 · 2020: 19 · 2019: 14 · 2018: 11 · 2017: 15 · 2016: 5 · 2015: 1
- FWCI
- 12.33
- Type
- journal article
- Language
- en
- Open access
- gold
- doi.org
- Locations
- Nature Communications (publishedVersion, cc-by)
- PubMed Central (publishedVersion, cc-by)
- PubMed (publishedVersion)
- RePEc: Research Papers in Economics (submittedVersion)
- DOAJ (DOAJ: Directory of Open Access Journals) (submittedVersion, cc-by-sa)
- DSpace@MIT (Massachusetts Institute of Technology) (submittedVersion, cc-by-nc)
- Funders
- National Science Foundation (PHY- 969969)
- Defense Advanced Research Projects Agency
- Multidisciplinary University Research Initiative (W911NF-11-1-0268)
- Air Force Office of Scientific Research
- Army Research Office (W911NF‐11‐1‐0268, MURI grant W911NF-11-1-0268, W911NF, W911NF-11)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Topological and Geometric Data Analysis
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
- Keywords
- quantum algorithms, quantum machine learning, topological data analysis, persistent homology, Betti numbers, combinatorial Laplacian, eigenvector computation, quantum advantage
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
