Quantum Log-Determinant Methods for Torsion-Sensitive Topological Data Analysis

arXiv (Cornell University)

Abstract

Betti numbers are central to topological data analysis but fail to capture torsion in integral homology. Torsion can distinguish topological structures with identical Betti numbers, and examples from classical topological data analysis show that it can affect the topology inferred from data. Related torsion-sensitive quantities are also known to have practical applications in graph-based machine learning, including biomedical applications. We investigate how quantum spectral methods can access this additional information. Log pseudodeterminants, obtained by summing the logarithms of the nonzero boundary-Laplacian eigenvalues, summarize spectral information about a simplicial complex. Under explicit topological assumptions, an alternating combination of these quantities gives the size of a higher critical group, the higher-dimensional analogue of a graph sandpile group. With stronger certification, a related construction recovers the size of the torsion subgroup in homology itself. This is, to our knowledge, the first provably correct quantum estimator of integral-homology torsion order. We give a new quantum algorithm for estimating these quantities, with explicit dependence on how the input is queried, the required accuracy, and the spectral gaps. Exact spectra for balanced multipartite clique complexes provide favorable gaps, and a related construction gives an explicit torsion-bearing benchmark. With compact query access, the algorithm need not construct the exponentially large boundary matrices explicitly. For a restricted torsion-bearing family, a tailored amplitude-estimation routine uses quadratically fewer queries than any randomized classical algorithm given comparable access when estimating the log pseudodeterminant. Estimating the full, unnormalized quantity to fixed additive error still costs in proportion to the candidate-space dimension $D$.

Authors 5

1. Dimitrios Thanos Aachen Institute of Advanced Computer Science

   Leiden University · Netherlands Institute for Advanced Study in the Humanities and Social Sciences

   Affiliation as printed

   Institute of Advanced Computer Science , Leiden University , The Netherlands

2. Caesnan Leditto

   Universitas Kristen Immanuel · Monash University

   Affiliation as printed

   Faculty of Science and Computer , Universitas Kristen Immanuel , Yogyakarta , Indonesia

   School of Physics and Astronomy , Monash University , Melbourne , Australia

3. Adam Wesołowski

   Royal Holloway University of London · University of Oxford

   Affiliation as printed

   Department of Computer Science , Royal Holloway University of London , UK

   Department of Computer Science , University of Oxford , UK

4. Andreea-Iulia Lefterovici

   Leibniz University Hannover

   Affiliation as printed

   Institut für Theoretische Physik , Leibniz Universität Hannover , Hannover , Germany

   Matematikos ir informatikos fakultetas , Vilniaus universiteto , Vilnius , Lithuania

5. Mahtab Yaghubi Rad