PIRSA:16080020

Quantum algorithm for topological analysis of data

Lloyd, S. (2016). Quantum algorithm for topological analysis of data. Perimeter Institute. https://pirsa.org/16080020

Lloyd, Seth. Quantum algorithm for topological analysis of data. Perimeter Institute, Aug. 12, 2016, https://pirsa.org/16080020 

          @misc{ pirsa_PIRSA:16080020,
            doi = {10.48660/16080020},
            url = {https://pirsa.org/16080020},
            author = {Lloyd, Seth},
            keywords = {Condensed Matter},
            language = {en},
            title = {Quantum algorithm for topological analysis of data},
            publisher = {Perimeter Institute},
            year = {2016},
            month = {aug},
            note = {PIRSA:16080020 see, \url{https://pirsa.org}}
          }

Seth Lloyd Massachusetts Institute of Technology (MIT) - Center for Extreme Quantum Information Theory (xQIT)

Talk numberPIRSA:16080020
DOI10.48660/16080020
Collection
Talk Type Conference
Subject

Abstract

This talk presents a quantum algorithm for performing persistent homology, the identification of topological features of data sets such as connected components, holes and voids. Finding the full persistent homology of a data set over n points using classical algorithms takes time O(2^{2n}), while the quantum algorithm takes time O(n^2), an exponential improvement. The quantum algorithm does not require a quantum random access memory and is suitable for implementation on small quantum computers with a few hundred qubits.