Quantum Query Complexity of Persistence Statistics in Graph Zigzags
Abstract
We study the query complexity of estimating scalar summaries of zigzag bar lifetimes from snapshot-adjacency bits. For graphs G1,…,Gm on n labeled vertices, let ℓb be the snapshot lifetime of a degree-one bar b of the intersection zigzag. For a probability generating function ϕ(x)=𝔼[xR], the statistic Fϕ=∑bϕ(ℓb/m) includes normalized degree-r total persistence and the mean generalized rank over a uniform time window. An exact identity underlies our algorithm: sample R uniform times; the expected generalized rank between their minimum and maximum equals Fϕ. For graphs that rank is the circuit rank of an intersection graph, so a nonlinear barcode functional becomes an average of edge and component counts, and no barcode is computed. Without spectral-gap, homology-state, or QRAM assumptions, this gives a quantum estimator with additive error ε n and Õ(√(m(K+n))/ε) queries when a bound K≥ Fϕ is supplied, against Õ(mmin{n2,(K+n)/ε2}) classically, and an adaptive quantum variant with the same instance dependence. These estimators are optimal in two regimes. For every fixed power weight xr, r≥2, and for the uniform-window mean, the worst-case complexities are Θ̃(n√m/ε) quantum and Θ(n2m) classical. On sparse instances, under an explicit split-leakage promise met by power and binomial weights of logarithmic degree and the promise Fϕ≤ K, they are Θ̃(√(mK)/ε) and Θ̃(mmin{n2,K/ε2}). The classical lower bounds hold against fully adaptive algorithms, and fewer than m such statistics cannot determine the positive-lifetime histogram. All bounds concern snapshot access; with an explicit update stream, near-linear full-barcode algorithms are known.
Related
- Near-Optimal Separations of Certificate Complexity from Randomized and Quantum Query Complexity
- Quantum Query Complexity Beyond the Worst Case
- Quantum Query Complexity of Tournament Solutions
- Optimal query complexity for fractional quantum evolution
- Quantum Query Complexity of Maximum Degree and its Generalizations
BibTeX
@misc{xin2026quantum,
title = {{Quantum Query Complexity of Persistence Statistics in Graph Zigzags}},
author = {Cheng Xin},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.05813},
eprint = {2609.05813},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.05813},
}
RIS
TY - UNPB
TI - Quantum Query Complexity of Persistence Statistics in Graph Zigzags
AU - Cheng Xin
PY - 2026
DA - 2026/09/05
PB - arXiv
DO - 10.48550/arxiv.2609.05813
UR - https://arxiv.org/abs/2609.05813
AB - We study the query complexity of estimating scalar summaries of zigzag bar lifetimes from snapshot-adjacency bits. For graphs G_1,…,G_m on n labeled vertices, let ℓ_b be the snapshot lifetime of a degree-one bar b of the intersection zigzag. For a probability generating function ϕ(x)=𝔼[x^R], the statistic F_ϕ=∑_bϕ(ℓ_b/m) includes normalized degree-r total persistence and the mean generalized rank over a uniform time window. An exact identity underlies our algorithm: sample R uniform times; the expected generalized rank between their minimum and maximum equals F_ϕ. For graphs that rank is the circuit rank of an intersection graph, so a nonlinear barcode functional becomes an average of edge and component counts, and no barcode is computed. Without spectral-gap, homology-state, or QRAM assumptions, this gives a quantum estimator with additive error ε n and Õ(√(m(K+n))/ε) queries when a bound K≥ F_ϕ is supplied, against Õ(mmin{n^2,(K+n)/ε^2}) classically, and an adaptive quantum variant with the same instance dependence. These estimators are optimal in two regimes. For every fixed power weight x^r, r≥2, and for the uniform-window mean, the worst-case complexities are Θ̃(n√m/ε) quantum and Θ(n^2m) classical. On sparse instances, under an explicit split-leakage promise met by power and binomial weights of logarithmic degree and the promise F_ϕ≤ K, they are Θ̃(√(mK)/ε) and Θ̃(mmin{n^2,K/ε^2}). The classical lower bounds hold against fully adaptive algorithms, and fewer than m such statistics cannot determine the positive-lifetime histogram. All bounds concern snapshot access; with an explicit update stream, near-linear full-barcode algorithms are known.
ER -