Quantum Algorithm of the GLMY Homology on Digraphs

• URL: http://arxiv.org/abs/2509.13862v2
• Date: Sun, 28 Sep 2025 03:34:00 GMT
• Title: Quantum Algorithm of the GLMY Homology on Digraphs
• Authors: Yunpeng Zi, Muchun Yang, D. L. Zhou,
• Abstract summary: We propose a quantum algorithm for the GLMY homology with significant advantage over the best classical algorithm.<n>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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Quantum-Channel Matrix Optimization for Holevo Bound Enhancement [87.57725685513088]
  We propose a unified projected gradient ascent algorithm to optimize the quantum channel given a fixed input ensemble.<n> Simulation results demonstrate that the proposed quantum channel optimization yields higher Holevo bounds than input ensemble optimization.
  arXiv  Detail & Related papers  (2026-02-19T04:15:03Z)
• Quartic quantum speedups for community detection [84.14713515477784]
  We develop a quantum algorithm for hypergraph community detection that achieves a quartic quantum speedup.<n>Our algorithm is based on the Kikuchi method, which we extend beyond previously considered problems such as PCA and $p$XORSAT.
  arXiv  Detail & Related papers  (2025-10-09T17:35:17Z)
• End-to-End Quantum Algorithm for Topology Optimization in Structural Mechanics [1.6943815984028532]
  We present an end-to-end, fault-tolerant quantum algorithm for topology optimization.<n>The proposed quantum workflow demonstrates how quantum algorithms can advance the field of computational science and engineering.
  arXiv  Detail & Related papers  (2025-10-08T17:42:28Z)
• Quantum DPLL and Generalized Constraints in Iterative Quantum Algorithms [0.0]
  We explore a class of hybrid quantum algorithms that are closely related to classical greedy or local search algorithms.<n>We develop a hybrid quantum version of the well-known classical Davis-Putnam-Logemann-Loveland (DPLL) algorithm for satisfiability problems.
  arXiv  Detail & Related papers  (2025-09-02T18:00:05Z)
• Hybrid quantum-classical framework for Betti number estimation with applications to topological data analysis [0.7997838571956237]
  Topological data analysis (TDA) is a rapidly growing area that applies techniques from algebraic topology to extract robust features from large-scale data.<n>A key task in TDA is the estimation of (normalized) Betti numbers, which capture essential topological invariants.<n>We explore an alternative direction: combining classical and quantum resources to estimate the Betti numbers of a simplicial complex more efficiently.
  arXiv  Detail & Related papers  (2025-08-02T23:19:11Z)
• Quantum Sieving for Code-Based Cryptanalysis and Its Limitations for ISD [0.0]
  We introduce the first quantum algorithms for code sieving by designing quantum variants of the aforementioned sieving subroutine.<n>Our quantum-walk algorithm exploits the structure of the underlying search problem by adding a layer of locality-sensitive filtering.<n>Our analysis highlights that the framework should be adapted in order to outperform the state-of-the-art of quantum ISD algorithms.
  arXiv  Detail & Related papers  (2024-08-29T11:47:33Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [62.46800898243033]
  Recent progress in quantum learning theory prompts a question: can linear properties of a large-qubit circuit be efficiently learned from measurement data generated by varying classical inputs?<n>We prove that the sample complexity scaling linearly in $d$ is required to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d.<n>We propose a kernel-based method leveraging classical shadows and truncated trigonometric expansions, enabling a controllable trade-off between prediction accuracy and computational overhead.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• Quantum Maximum Entropy Inference and Hamiltonian Learning [4.9614587340495]
  This work extends algorithms for maximum entropy inference and learning of graphical models to the quantum realm. The generalization, known as quantum iterative scaling (QIS), is straightforward, but the key challenge lies in the non-commutative nature of quantum problem instances. We explore quasi-Newton methods to enhance the performance of QIS and GD.
  arXiv  Detail & Related papers  (2024-07-16T08:11:34Z)
• Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
  Quantum computing sets the foundation for new ways of designing algorithms. New challenges arise concerning which field quantum speedup can be achieved. Looking for the design of quantum subroutines that are more efficient than their classical counterpart poses solid pillars to new powerful quantum algorithms.
  arXiv  Detail & Related papers  (2024-02-26T09:32:07Z)
• Generalized quantum Arimoto-Blahut algorithm and its application to quantum information bottleneck [55.22418739014892]
  We generalize the quantum Arimoto-Blahut algorithm by Ramakrishnan et al. We apply our algorithm to the quantum information bottleneck with three quantum systems. Our numerical analysis shows that our algorithm is better than their algorithm.
  arXiv  Detail & Related papers  (2023-11-19T00:06:11Z)
• Quantum Bayesian Optimization [64.58749619145908]
  We introduce the quantum-Gaussian process-upper confidence bound (Q-GP-UCB) algorithm. It is the first BO algorithm able to achieve a regret upper bound of O(polylog T), which is significantly smaller than its regret lower bound of Omega(sqrt(T)) in the classical setting. Thanks to our novel analysis of the confidence ellipsoid, our Q-GP-UCB with the linear kernel achieves a smaller regret than the quantum linear UCB algorithm.
  arXiv  Detail & Related papers  (2023-10-09T03:10:42Z)
• A quantum advantage over classical for local max cut [48.02822142773719]
  Quantum optimization approximation algorithm (QAOA) has a computational advantage over comparable local classical techniques on degree-3 graphs. Results hint that even small-scale quantum computation, which is relevant to the current state-of the art quantum hardware, could have significant advantages over comparably simple classical.
  arXiv  Detail & Related papers  (2023-04-17T16:42:05Z)
• Automatic and effective discovery of quantum kernels [41.61572387137452]
  Quantum computing can empower machine learning models by enabling kernel machines to leverage quantum kernels for representing similarity measures between data.<n>We present an approach to this problem, which employs optimization techniques, similar to those used in neural architecture search and AutoML.<n>The results obtained by testing our approach on a high-energy physics problem demonstrate that, in the best-case scenario, we can either match or improve testing accuracy with respect to the manual design approach.
  arXiv  Detail & Related papers  (2022-09-22T16:42:14Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.