Skip to main page content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Access keys NCBI Homepage MyNCBI Homepage Main Content Main Navigation
. 2016 Jan 25:7:10138.
doi: 10.1038/ncomms10138.

Quantum algorithms for topological and geometric analysis of data

Seth Lloyd  1 , Silvano Garnerone  2 , Paolo Zanardi  3
Affiliations

Quantum algorithms for topological and geometric analysis of data

Seth Lloyd et al. Nat Commun. .

Abstract

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.

PubMed Disclaimer

References

    1. Zomorodian A. & Carlsson G. Computing persistent homology. Discret. Comput. Geom. 33, 249–274 (2005).
    1. Robins V. Towards computing homology from finite approximations. Topol. Proc. 24, 503–532 (1999).
    1. Frosini P. & Landi C. Size theory as a topological tool for computer vision. Pattern Recognit. Image Anal. 9, 596–603 (1999).
    1. Carlsson G., Zomorodian A., Collins A. & Guibas L. Persistence barcodes for shapes. Int. J. Shape Model. 11, 149–188 (2005).
    1. Edelsbrunner H., Letscher D. & Zomorodian A. Topological persistence and simplification. Discret. Comput. Geom. 28, 511–533 (2002).

Publication types