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.

arXiv:2509.13862 [quant-ph]

(or arXiv:2509.13862v3 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2509.13862 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.