PIRSA:16080020

Video URL

https://pirsa.org/16080020

Quantum algorithm for topological analysis of data

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

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

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

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

Talk numberPIRSA:16080020
DOI10.48660/16080020
Source RepositoryPIRSA
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.