Quantum Topological Analysis on Digraphs

Abstract

Quantum algorithms for topological data analysis provide significant advantages over the best known classical algorithms. Unlike previous work on simplicial complexes built from point clouds, path homology on digraphs is defined for directed graphs and provides a natural topological framework for analyzing data with intrinsic directional structures. Path homology has become an emerging area in Topological Data Analysis (TDA), attracting increasing attention in recent years. We propose a quantum algorithm for path homology on digraphs that offers a significant advantage over the best known classical algorithms. We design a universal encoding protocol for the paths and boundary operators of digraphs on quantum systems. We prove a property of path homology that provides the theoretical guarantee for the algorithm. The speedup of the quantum algorithm for path homology depends on input-access assumptions. The exponential speedup arises when the path space can be efficiently accessed, while for standard digraph input the algorithm provides polynomial speedup.

26 pages, 2 figures, To be appeared on Quantum Science and Technology