REVIEW 2 major objections 5 minor 14 references
Complexity of Normalized Persistence Problems for Topological Data Analysis and Local Hamiltonians
T0 review · 2 major / 5 minor · reviewed 2026-07-12 · grok-4.5
Pith's one-line read A practically motivated fraction of persistent holes is DQC1-hard for clique complexes and sits in BQP, giving evidence of exponential quantum advantage for TDA.
desk verdict Solid first DQC1-hardness results that actually hit clique-complex TDA instances, plus a clean upgrade of low-energy spectral problems to constant locality. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
Circuit-to-Hamiltonian constructions that place the DQC1 (or SDQC1) acceptance signal inside a low-energy subspace of an O(1)-local history Hamiltonian, then encode that Hamiltonian into a weighted combinatorial Laplacian via universal simulation so that the normalized low-energy quantities become TDA instances.
What would settle it
Either an efficient classical algorithm for the hard Normalized Quasi-Harmonic Persistence instances (collapsing DQC1 into BPP) or a proof that the hard Laplacian instances cannot prepare the required low-energy mixture without already solving a DQC1-hard problem.
Extended reading notes
Core claim
Normalized Quasi-Harmonic Persistence on clique complexes is DQC1-hard and contained in BQP under natural state-preparation and large-overlap assumptions; the same hardness and containment hold for Low-energy Normalized Subtrace and Low-energy Spectral Density on O(1)-local Hamiltonians. Exact-kernel normalized persistence is SDQC1-hard.
Load-bearing premise
All BQP containment proofs need an efficient circuit that prepares a state close to the uniform mixture over the low-energy or kernel subspace being measured.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces normalized persistence (the fraction of holes that persist under inclusion of complexes) and a family of related low-energy spectral problems for local Hamiltonians. It proves that Normalized Quasi-Harmonic Persistence (Problem 8) is DQC1-hard for clique-complex Laplacians and contained in BQP under efficient low-energy mixture preparation and large-overlap assumptions (Theorem 8, Lemma 6). Parallel results establish DQC1-hardness of Low-energy Normalized Subtrace and Low-energy Spectral Density for O(1)-local Hamiltonians (Theorems 1, 3), strengthening prior log-local hardness for related full-space quantities. Exact-kernel variants are placed in a new perfect-completeness class SDQC1, with SDQC1-hardness for Normalized Persistence and Low-energy Kernel Density (Theorems 5, 7); exact Normalized Harmonic Persistence is left as a conjecture conditional on a coefficient-sensitive kernel-preserving simulation (Conjectures 1–2). Containment proofs use phase estimation and fixed-point amplitude amplification under the stated state-preparation assumptions.
Significance. If the reductions hold, the work supplies the first DQC1-hardness statements that apply directly to clique complexes arising in TDA, and upgrades several spectral-density hardness results from log-local to constant-local Hamiltonians. The subspace-normalized landscape (Figure 1, Table 1) cleanly unifies prior pure-state overlap problems with the new mixture-normalized quantities. The introduction of SDQC1 is a natural and useful device for exact-kernel problems. Hardness is shown to survive the same state-preparation and large-overlap assumptions used for BQP containment, so the claimed exponential quantum advantage is well-scoped under the standard DQC1 ⊈ BPP assumption. Exact-kernel TDA hardness is correctly left conditional, which is a strength of the presentation rather than a weakness.
major comments (2)
- Lemmas 1–7 and the hardness statements that preserve them (Theorems 1, 3, 5–8) all rest on efficient preparation of a state close in trace distance to the uniform mixture over the relevant low-energy or kernel subspace. Lemma 8 constructs this mixture for the unperturbed history subspace of the circuit-to-Hamiltonian construction, and the CMP+Rayudu chain (Lemma 10, Figure 2) transfers it to the clique Laplacian. The paper does not, however, give a general criterion for when hard instances of the TDA or local-Hamiltonian problems admit such preparation without already solving a hard problem. Section 1.6 flags this as open; a short, explicit discussion of the scope of the claimed quantum advantage (worst-case under the mixture oracle vs. natural TDA filtrations) would make the central claim more precise without changing the theorems.
- Conjecture 2 (coefficient-sensitive kernel realization) is the load-bearing missing ingredient for SDQC1-hardness of Normalized Harmonic Persistence. The discussion in Section 7 correctly identifies that approximate low-energy simulation (CMP/Rayudu) does not preserve kernel dimension, and that the King–Kohler gapped-homology construction does not immediately supply the required filtration-compatible, coefficient-sensitive encoding. The conditional Lemma 11 is sound, but the manuscript would be stronger if it either (i) sketched a concrete obstruction or (ii) indicated a restricted gate set / history-Hamiltonian class for which Conjecture 2 is already known or easier. As written, the gap between the proven NQHP result and the conjectured NHP result is large and should be stated more sharply in the abstract and introduction.
minor comments (5)
- Definition 2 of SDQC1 depends on the gate set G; the text notes this but does not fix a concrete universal set for the hardness theorems. A single sentence specifying the intended gateset (e.g., Clifford+T or the set used in the circuit-to-Hamiltonian construction) would remove ambiguity.
- Figure 1 is dense; the distinction between solid reduction arrows and dotted pure-state specializations is useful but the caption could more explicitly list which boxes are new vs. prior work (Normalized Subtrace, LLSD).
- Appendix A (Rayudu construction) is clear, but the identity-shift constants C and C̃ that appear in the LENS-for-TDA reduction (Section 6.1) are only described as “efficiently computable.” A short remark that they are classical poly-time functions of the gadget parameters would help readers who want to implement the reduction.
- Typographical: “Brand˜ ao” appears with a tilde in several places; standardize to Brandão. Also “1/2 BQP” vs. “½BQP” notation is inconsistent in Section 1.6.
- Problem 8 (NQHP) forces G1 and G2 to share the same vertex set. This is natural for Vietoris–Rips filtrations, but a one-sentence remark that the hardness still holds under this restriction (via G1=G2) would prevent readers from thinking the result is only for general inclusions.
Circularity Check
No circularity: hardness follows from explicit circuit-to-Hamiltonian reductions that approximate DQC1/SDQC1 acceptance probabilities by independent spectral quantities; containment uses standard phase estimation under stated state-preparation assumptions.
full rationale
The paper's central claims are complexity-theoretic hardness and containment statements obtained by polynomial-time reductions and algorithmic reductions, not by fitting parameters or by defining the target quantities in terms of the source problems. In Sections 5.2–5.6 the DQC1 (resp. SDQC1) acceptance probability is encoded into the low-energy spectrum of an explicitly constructed O(1)-local history Hamiltonian H_DQC1 (resp. H_SDQC1) via a unary-clock circuit-to-Hamiltonian map; Lemmas 9 and 8 then show that the low-energy normalized subtrace / spectral density / kernel density of this Hamiltonian approximates the acceptance probability to inverse-polynomial precision, while the uniform mixture over the unperturbed history subspace is preparable by a poly-size circuit. The same quantities are transferred to clique-complex Laplacians by the external CMP+Rayudu simulation chain (Lemma 10, Appendix A). None of these steps is self-definitional: the spectral quantities are defined independently of the circuit acceptance probability and are only shown to be close to it. Containment (Section 8) likewise relies on phase estimation and fixed-point amplitude amplification applied to an assumed preparable mixture, under the large-overlap promise; the hardness proofs preserve those assumptions rather than assuming the conclusion. Exact-kernel TDA hardness is correctly left conditional on the open Conjecture 2. No fitted inputs, uniqueness theorems imported from the authors, or ansatz smuggling appear. The derivation chain is therefore self-contained against the external complexity classes DQC1 and SDQC1.
Assumptions & free parameters
assumptions (4)
- domain assumption DQC1 is not contained in BPP (standard assumption used to interpret hardness as evidence of exponential quantum advantage).
- domain assumption Cubitt–Montanaro–Piddock universal simulation and Rayudu combinatorial-Laplacian simulation of XX+ZZ Hamiltonians preserve low-energy spectra up to inverse-polynomial error (Lemma 10).
- standard math Marriott–Watrous amplification can be performed inside DQC1 with O(log n) clean qubits.
- standard math Efficient preparation of the uniform mixture over history states of a DQC1 circuit (Lemma 8).
invented entities (1)
-
SDQC1 (Subspace DQC1 with perfect completeness)
Cite this review
Pith. "Pith review of Complexity of Normalized Persistence Problems for Topological Data Analysis and Local Hamiltonians." pith.science (2026). https://pith.science/paper/WRFTKBWI
@misc{pith2026260703278,
author = {Pith},
title = {Pith review of: Complexity of Normalized Persistence Problems for Topological Data Analysis and Local Hamiltonians},
year = {2026},
howpublished = {\url{https://pith.science/paper/WRFTKBWI}},
note = {Machine review of arXiv:2607.03278}
}
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 $\mathsf{DQC}_1$-hard and contained in $\mathsf{BQP}$, giving evidence of an exponential quantum speedup for TDA under the standard assumption that $\mathsf{DQC}_1 \not\subseteq \mathsf{BPP}$. These are the first $\mathsf{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 $\mathsf{DQC}_1$-hard for $O(1)$-local Hamiltonians, strengthening previous results that required log-local interactions. We also introduce a variant of $\mathsf{DQC}_1$ with perfect completeness ($\mathsf{SDQC}_1$) to characterize the hardness of problems normalized by an exact kernel. This includes normalized persistence for $O(1)$-local Hamiltonians, which we show is $\mathsf{SDQC}_1$-hard.
Figures
Figures from the paper (1 more)
Reference graph
Works this paper leans on
-
[1]
[DW22] Tamal Krishna Dey and Yusu Wang.Computational topology for data analysis
arXiv:1701.05182 [quant-ph]. [DW22] Tamal Krishna Dey and Yusu Wang.Computational topology for data analysis. Cam- bridge University Press, 2022. [EHG25] Roman Edenhofer, Atsuya Hasegawa, and Fran¸ cois Le Gall. Dequantization and hard- ness of spectral sum estimation.arXiv preprint arXiv:2509.20183, 2025. [FKM+18] Keisuke Fujii, Hirotada Kobayashi, Tomoy...
arXiv 2022
-
[2]
Real numbersϵ≥ 1 poly(n) and1> µ >1/2
-
[3]
Output:An estimateχ∈Rwith probability at leastµthat satisfies Trη(H)−ϵ≤χ≤ Trη(H) +ϵ, where Trη(H) := 1 2n X 0≤λi≤η λi
A sparse positive semidefinite HamiltonianH∈C 2n×2n with∥H∥ ≤poly(n). Output:An estimateχ∈Rwith probability at leastµthat satisfies Trη(H)−ϵ≤χ≤ Trη(H) +ϵ, where Trη(H) := 1 2n X 0≤λi≤η λi. The following complexity theoretic result was shown in [Bra08]. Theorem 10([Bra08]).Normalized SubtraceisDQC 1-hard forO(log(n))-local Hamiltonians. A related problem w...
-
[4]
Real numbersϵ≥ 1 poly(n) ,η≥ 1 poly(n) ,δ≥ 1 poly(n) and1> µ >1/2
-
[5]
Output:An estimateχ∈[0,1]with probability at leastµthat satisfies DH(0, η)−ϵ≤χ≤D H(0, η+δ) +ϵ 1In [GCD22],N H (a, b) was used for this quantity
A sparse positive semidefinite HamiltonianH∈C 2n×2n with∥H∥ ≤poly(n). Output:An estimateχ∈[0,1]with probability at leastµthat satisfies DH(0, η)−ϵ≤χ≤D H(0, η+δ) +ϵ 1In [GCD22],N H (a, b) was used for this quantity. We instead denote this byD H (a, b) and useN H (a, b) for an unnormalized quantity. 59 The following result is known on this problem. Theorem ...
-
[6]
Promise:1
Apoly(n)-size classical description of a setS⊆K 1,p ofp-simplices inK 1. Promise:1. Spectral gapγ(∆ K2 p ) := min{|λ| |λ∈Spec(∆ K2 p ), λ >0} ≥ 1 poly(n)
-
[7]
Output:1if (a),0if (b)
For the uniform superposition|σ⟩:= 1√ |S| P σi∈S |σi⟩, either (a)∥proj Hp(K2)(|σ⟩)∥ ≥δ, or (b)∥proj Hp(K2)(|σ⟩)∥< 1 exp(n). Output:1if (a),0if (b). This problem was shown to beBQP 1-hard and contained inBQP. The following two promise problems for local Hamiltonians are introduced in [GSK +26] as underlying quantum primitives for Harmonic Persistence. Firs...
-
[8]
Ann-qubitO(log(n))-local HamiltonianH= Pm i=1 Hi withm=O(poly(n))
Show all 14 references
-
[9]
Promise:
A succinct description of a quantum state|ψ⟩. Promise:
-
[10]
Spectral gapγ(H) := min{|λ| |λ∈Spec(H), λ >0} ≥ 1 poly(n)
-
[11]
Output:1if(a),0if(b)
Either(a)∥proj kerH (|ψ⟩)∥ ≥ 1 poly(n) , or(b)∥proj kerH (|ψ⟩)∥< 1 exp(n). Output:1if(a),0if(b). Similarly to theHarmonic persistence, this problem was shown to beBQP 1-hard and contained inBQPin [GSK +26]. Next, we introduce a low-energy variant of this problem. Problem 14(Lo...
-
[12]
Ann-qubit log-local HamiltonianH= Pm i=1 Hi withm=O(poly(n))
-
[13]
A thresholdη∈Ω(1/poly(n))
-
[14]
60 Promise:Either(a) ∥projE≤η(H)(|ψ⟩)∥ ≥ 1 poly(n) , or(b) ∥projE≤η(H)(|ψ⟩)∥< 1 exp(n)
A succinct description of a quantum state|ψ⟩. 60 Promise:Either(a) ∥projE≤η(H)(|ψ⟩)∥ ≥ 1 poly(n) , or(b) ∥projE≤η(H)(|ψ⟩)∥< 1 exp(n) . Output:1if(a),0if(b). Here E≤η(H) := Span C {|ψ⟩ | |ψ⟩is an eigenvector ofHwith eigenvalue< η}. This problem is known to beBQP-complete [GSK +26]. 61
Reviewed July 12, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.