Quantum Algorithm of the GLMY Homology on Digraphs

2025/09/17 by Yunpeng Zi, Zi, Yunpeng, Muchun Yang +3
Computer Science · Mathematics · #FOS: Physical sciences #Homotopy and Cohomology in Algebraic Topology #Quantum Physics (quant-ph) #Topological and Geometric Data Analysis #advanced mathematical theories

paper · pdf · doi:10.48550/arxiv.2509.13862

openalex publication_date 2025/09/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Quantum algorithms for topological data analysis provide significant advantage over the best classical algorithm. Different from the previous simplical complex on points cloud, the GLMY homology introduced by Alexander Grigor'yan, Yong Lin, Yuri Muranov and Shing-Tung Yau, is defined on digraph and is a arising realm in Topological Data Analysis (TDA), which attracts more and more attention recently. We propose a quantum algorithm for the GLMY homology with significant advantage over the best classical algorithm. We design a universal encoding protocol for the quantum states and boundary operators of GLMY homology on digraphs. And a property of the GLMY homology is proved for the theoretical guarantee of the quantum algorithm. The quantum algorithm for GLMY homology provides a cubic speedup in general cases, and it can provide an exponential quantum advantage in the case of the input data is given as a specification of paths.

Citations

• Inductive construction of path homology chains
• Homology of weighted path complexes and directed hypergraphs
• Quantum Topological Data Analysis with Linear Depth and Exponential Speedup
• Experimental Quantum Embedding for Machine Learning
• An efficient algorithm for 1-dimensional (persistent) path homology
• Weighted Path homology of Weighted Digraphs and Persistence
• Persistent Path Homology of Directed Networks
• The Embedded Homology of Hypergraphs and Applications
• Homotopy theory for digraphs
• Homologies of path complexes and digraphs
• Efficient state preparation for a register of quantum bits

Related

• A quantum algorithm for Khovanov homology
• Quantum algorithms for topological and geometric analysis of big data
• New aspects of quantum topological data analysis: Betti number estimation, and testing and tracking of homology and cohomology classes
• Topological Quantum Information, Khovanov Homology and the Jones Polynomial
• The Topology of Grover Algorithm