A streamlined quantum algorithm for topological data analysis with exponentially fewer qubits

Quantum, vol. 10, pp. 2058

Abstract

Topological invariants of a dataset, such as the number of holes that survive from one length scale to another (persistent Betti numbers) can be used to analyze and classify data in machine learning applications. We present an improved quantum algorithm for computing persistent Betti numbers, and provide an end-to-end complexity analysis. Our approach provides large polynomial time improvements, and an exponential space saving, over existing quantum algorithms. Subject to gap dependencies, our algorithm obtains an almost quintic speedup in the number of datapoints over previously known rigorous classical algorithms for computing the persistent Betti numbers to constant additive error – the salient task for applications. However, we also introduce a quantum-inspired classical power method with provable scaling only quadratically worse than the quantum algorithm. This gives a provable classical algorithm with scaling comparable to existing classical heuristics. We discuss whether quantum algorithms can achieve an exponential speedup for tasks of practical interest, as claimed previously. We conclude that there is currently no evidence for this being the case.

Authors 3

1. Sam McArdle

   Amazon (United States)

   Affiliation as printed

   AWS Center for Quantum Computing, Pasadena, CA 91125, USA

2. András Gilyén

   HUN-REN Alfréd Rényi Institute of Mathematics

   Affiliation as printed

   Alfréd Rényi Institute of Mathematics, Budapest, Hungary

3. Mario Berta Aachen Institute for Quantum Information

   RWTH Aachen University · Imperial College London

   Affiliation as printed

   Department of Computing, Imperial College London, London, UK

   Institute for Quantum Information, RWTH Aachen University, Aachen, Germany