Towards quantum advantage via topological data analysis

Abstract

Even after decades of quantum computing development, examples of generally useful quantum algorithms with exponential speedups over classical counterparts are scarce. Recent progress in quantum algorithms for linear-algebra positioned quantum machine learning (QML) as a potential source of such useful exponential improvements. Yet, in an unexpected development, a recent series of "dequantization" results has equally rapidly removed the promise of exponential speedups for several QML algorithms. This raises the critical question whether exponential speedups of other linear-algebraic QML algorithms persist. In this paper, we study the quantum-algorithmic methods behind the algorithm for topological data analysis of Lloyd, Garnerone and Zanardi through this lens. We provide evidence that the problem solved by this algorithm is classically intractable by showing that its natural generalization is as hard as simulating the one clean qubit model -- which is widely believed to require superpolynomial time on a classical computer -- and is thus very likely immune to dequantizations. Based on this result, we provide a number of new quantum algorithms for problems such as rank estimation and complex network analysis, along with complexity-theoretic evidence for their classical intractability. Furthermore, we analyze the suitability of the proposed quantum algorithms for near-term implementations. Our results provide a number of useful applications for full-blown, and restricted quantum computers with a guaranteed exponential speedup over classical methods, recovering some of the potential for linear-algebraic QML to become one of quantum computing's killer applications.

arXiv comment31+7 pages, 3 figures

References in corpus (36)

• Quantum Computing in the NISQ era and beyond
• Quantum Machine Learning
• Quantum algorithm for solving linear systems of equations
• Supervised learning with quantum enhanced feature spaces
• Quantum principal component analysis
• Error mitigation for short-depth quantum circuits
• Parameterized quantum circuits as machine learning models
• Circuit-centric quantum classifiers
• On the Power of One Bit of Quantum Information
• Quantum algorithms for quantum chemistry and quantum materials science
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• Practical Quantum Error Mitigation for Near-Future Applications
• Error-mitigated digital quantum simulation
• Low-cost error mitigation by symmetry verification
• A quantum-inspired classical algorithm for recommendation systems
• Quantum phase estimation of multiple eigenvalues for small-scale (noisy) experiments
• Quantum gradient descent for linear systems and least squares
• Spectral entropies as information-theoretic tools for complex network comparison
• Focus beyond quadratic speedups for error-corrected quantum advantage
• Complex Networks from Classical to Quantum
• The Clique Density Theorem
• Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning
• On the hardness of classically simulating the one clean qubit model
• Simplicial complexes: spectrum, homology and random walks
• The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation
• Error mitigation via verified phase estimation
• Hardness of classically sampling one clean qubit model with constant total variation distance error
• Quantum algorithm for estimating Renyi entropies of quantum states
• Demonstration of Topological Data Analysis on a Quantum Processor
• Heisenberg-limited quantum phase estimation of multiple eigenvalues with few control qubits
• Computational Difficulty of Computing the Density of States
• Hamiltonian simulation with nearly optimal dependence on spectral norm
• Entanglement Theory and the Quantum Simulation of Many-Body Physics
• Fast estimation of approximate matrix ranks using spectral densities
• The Bose-Hubbard model is QMA-complete

Cited by in corpus (23)

• Quantum Computing for High-Energy Physics: State of the Art and Challenges. Summary of the QC4HEP Working Group
• Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis
• Topological data analysis and machine learning
• Data re-uploading with a single qudit
• Complexity of Supersymmetric Systems and the Cohomology Problem
• A (simple) classical algorithm for estimating Betti numbers
• Clique Homology is QMA1-hard
• A quantum computing concept for 1-D elastic wave simulation with exponential speedup
• Digital-analog quantum learning on Rydberg atom arrays
• The topology of data hides in quantum thermal states
• Quantum Algorithm for Estimating Betti Numbers Using Cohomology Approach
• Quantum topological data analysis via the estimation of the density of states
• Quantum-Enhanced Topological Data Analysis: A Peep from an Implementation Perspective
• Unravelling quantum chaos using persistent homology
• Quantum Local Differential Privacy and Quantum Statistical Query Model
• Topological Signal Processing on Quantum Computers for Higher-Order Network Analysis
• Provable quantum speedups for computing persistence in topological data analysis
• Empirical Power of Quantum Encoding Methods for Binary Classification
• Quantum community detection via deterministic elimination
• Holey graphs: very large Betti numbers are testable
• Comparing quantum and classical Monte Carlo algorithms for estimating Betti numbers of clique complexes
• Vortex Detection from Quantum Data