Quantum Algorithm for the GLMY Homology on Digraphs
Organizers
Speaker
Muchun Yang
Time
Thursday, October 16, 2025 2:00 PM - 3:00 PM
Venue
A3-4-101
Online
Zoom 928 682 9093
(BIMSA)
Abstract
Quantum algorithms for topological data analysis provide significant advantages over the best classical algorithm. Differing from previous simplical complexes on point clouds, the GLMY homology introduced by Alexander Grigor’yan, Yong Lin, Yuri Muranov and Shing-Tung Yau, is defined on digraph in the realm of Topological Data Analysis (TDA), a field which continues to attract increasing attention. We propose a quantum algorithm for the GLMY homology with significant advantages 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 can provide an exponential quantum advantage in the case when the input data is given as a specification of paths.