PIRSA:16080020 Conference Condensed Matter

DOI10.48660/16080020

Conference/School: Quantum Machine Learning

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}}
}

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.

Resources

Related Talks