Complexity of Normalized Persistence Problems for Topological Data Analysis and Local Hamiltonians

Jul 16, 2026

Upload by Aria

Topological data analysis (TDA) leverages algebraic topology to extract structure from data, with persistent homology quantifying how robust topological features remain across lengthscales. This work introduces normalized persistence, an interpretable variant counting the fraction of holes that persist across scales. A variant is proven DQC 1-hard and contained in BQP, supporting exponential quantum speedup under standard assumptions. The paper connects normalized persistence to estimating spectral quantities in low-energy subspaces of O(1)-local Hamiltonians, establishing DQC 1-hardness and introducing SDQC1 hardness for exact-kernel-normalized problems.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages61

Reading Time2 h 34 min

AccessFree to download

Overview

Motivation

Existing Literature

Main Results

Complexity Landscape

Techniques

Preliminaries

Subspace DQC 1 with Perfect Completeness

Problem Definitions and Main Results

Low-Energy Spectral Problems

Spectral density problems

Exact Normalized Persistence

Hardness for Local-Hamiltonian Subspace Problems

Preparing Uniform Mixtures of History States

DQC 1-hardness of LENS

Hardness for TDA Problems

DQC 1-hardness of LENS for TDA

Containment of Low-Energy and Normalized Persistence Problems

YITP-26-81 arXiv :2607 .03278v1 [ quant-ph] 3 Jul 2026 Complexity of Normalized Persistence Problems for Topological Data Analysis and Local Hamiltonians Dominic Lowe 1 , M. S. Kim 1 , Roberto Bondesan2 , and Ryu Hayakawa3 1 Blackett Laboratory, Imperial College London, SW7 2AZ, United Kingdom 2 Department of Computing, Imperial College London, SW7 2AZ, United Kingdom 3 Yukawa Institute for Theoretical Physics & The Hakubi Center, Kyoto University, Japan Abstract Topological data analysis (TDA) is a machine learning technique that uses topology to extract patterns from data and has shown the potential to exhibit quantum advantage. A key concept in TDA is persistent homology, which measures the robustness of topological information at different lengthscales. In this paper, we introduce and study the problem of normalized persistence, a practically motivated and easily interpretable version of persistent homology that counts the fraction of holes that persist at different lengthscales. We prove that a variant of normalized persistence is DQC 1-hard and contained in BQP, giving evidence of an exponential quantum speedup for TDA under the standard assumption that DQC 1 ⊈ BPP. These are the first DQC 1-hardness results that are directly applicable to TDA instances. We also find a close connection between normalized persistence and the complexity of estimating spectral quantities in the low-energy subspace of local Hamiltonians. We study a family of such problems, including a low-energy normalized subtrace and spectral density. We show that these are DQC 1-hard for O(1)-local Hamiltonians, strengthening previous results that required log-local interactions. We also introduce a variant of DQC 1 with perfect completeness (SDQC1 ) to characterize the hardness of problems normalized by an exact kernel. This includes normalized persistence for O(1)-local Hamiltonians, which we show is SDQC 1-hard. Contents 1 Overview 2 1.1 Motivation ......................................... 2 1.2 Existing Literature ..................................... 4 1.2.1 Complexity results for TDA ............................ 4 1.2.2 Quantum algorithms for TDA ........................... 5 1.3 Main Results ........................................ 5 1.3.1 Results for TDA .................................. 5 1.3.2 Results for Local Hamiltonians .......................... 7 1.4 Complexity Landscape ................................... 8 1.5 Techniques ......................................... 10 1.6 Discussions and open questions .............................. 12 1.7 Organization ........................................ 13 2 Preliminaries 13 3 Subspace DQC 1 with Perfect Completeness 17 3.1 Power of SDQC 1 ...................................... 18 4 Problem Definitions and Main Results 18 4.1 Low-Energy Spectral Problems .............................. 19 4.2 Spectral density problems ................................. 20 4.3 Low-Energy Kernel Density ................................ 21 4.4 Normalized Quasi-Persistence ............................... 22 4.5 Exact Normalized Persistence ............................... 23 4.6 Normalized Quasi-Harmonic Persistence ......................... 24 4.7 Normalized Harmonic Persistence in TDA ........................ 25 5 Hardness for Local-Hamiltonian Subspace Problems 26 5.1 Preparing Uniform Mixtures of History States ...................... 26 5.2 DQC 1-hardness of LENS .................................. 26 5.3 DQC 1-hardness of LESD .................................. 31 5.4 Hardness of Normalized Quasi-Persistence ........................ 34 5.5 SDQC 1-hardness of LEKD ................................. 35 5.6 Hardness of Exact Normalized Persistence ........................ 36 6 Hardness for TDA Problems 37 6.1 DQC 1-hardness of LENS for TDA ............................. 38 6.2 DQC 1-hardness of LESD for TDA and NQHP ....................... 4

FAQs

What problem does the paper address in topological data analysis?

It studies the computational complexity of normalized persistence, an interpretable version of persistent homology that measures the fraction of holes persisting across lengthscales in TDA.

What are the main complexity-theoretic results for normalized persistence?

A variant of normalized persistence is proven DQC 1-hard and also contained in BQP, with the implication of exponential quantum speedup for TDA under the assumption DQC 1 ⊄̸ BPP.

How is normalized persistence connected to local Hamiltonians?

The paper shows a close connection between normalized persistence and the complexity of estimating spectral quantities in the low-energy subspace of local Hamiltonians, including results for low-energy normalized subtrace and spectral density for O(1)-local Hamiltonians.

Jul 16, 2026

Upload by Aria