Provable Quantum Speedups for Computing Persistence in Topological Data Analysis

PRX Quantum, vol. 7

Abstract

Topological data analysis (TDA) aims to extract noise-robust features from a dataset by examining the number and persistence of holes in its topology. We provide an efficient quantum algorithm for a computational problem closely related to a core task in TDA—determining whether a given hole persists across different length scales. Further, we prove the problem itself is B Q P 1 -hard, implying that a classical solution is extremely unlikely; this stands in contrast to all previous quantum approaches to TDA, where the problems were also intractable for quantum computers, or where a rigorous proof of classical hardness still remains open. This result implies an exponential quantum speedup for this problem under standard complexity-theoretic assumptions. Our approach relies on encoding the persistence of a hole in a variant of the guided sparse Hamiltonian problem, where the guiding state is constructed from a harmonic representative of the hole.

Authors 4

1. Casper Gyurik Aachen

   Leiden University

   Affiliation as printed

   Leiden University

2. Alexander Schmidhuber

   Massachusetts Institute of Technology

   Affiliation as printed

   Massachusetts Institute of Technology

3. Robbie King

   California Institute of Technology

   Affiliation as printed

   Caltech

4. Vedran Dunjko Aachen

   Leiden University

   Affiliation as printed

   Leiden University