PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum Query Complexity of Persistence Statistics in Graph Zigzags

Cheng Xin

arXiv:2609.05813v1quant-phcs.CG

TL;DR

Estimating scalar summaries of zigzag bar lifetimes from snapshot bits raises the question of how many queries are needed without computing a barcode. The paper represents these summaries as expected generalized ranks of random windows and establishes optimal worst-case query bounds for fixed power weights and the uniform-window mean.

  • Problem

    The paper asks how many snapshot-adjacency bits are needed to estimate scalar summaries of zigzag bar lifetimes, rather than compute the barcode.

    Source: §1 · p. 1

  • Method

    It samples R uniform times and estimates the generalized rank of the window between their extrema, whose expectation equals the persistence statistic.

    Source: §1 · p. 2

  • Results

    For fixed power weights x^r with r ≥2 and the uniform-window mean, quantum complexity is ˜Θ(n√m/ε), versus Θ(n^2m) randomized queries.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Fewer than m rational PGF weights cannot determine the positive-lifetime histogram, so these scalar statistics do not recover the barcode.

    Source: §1 · p. 3

    The bounds concern snapshot access; with an explicit update stream or searchable edge-lifetime index, complete barcodes are computable in near-linear time.

    Source: §1 · p. 3

Abstract

from arXiv · show

We study the query complexity of estimating scalar summaries of zigzag bar lifetimes from snapshot-adjacency bits. For graphs $G_1,\ldots,G_m$ on $n$ labeled vertices, let $\ell_b$ be the snapshot lifetime of a degree-one bar $b$ of the intersection zigzag. For a probability generating function $\phi(x)=\mathbb{E}[x^R]$, the statistic $F_\phi=\sum_b\phi(\ell_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_\phi$. 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 $\varepsilon n$ and $\widetilde O(\sqrt{m(K+n)}/\varepsilon)$ queries when a bound $K\ge F_\phi$ is supplied, against $\widetilde O(m\min\{n^2,(K+n)/\varepsilon^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\ge2$, and for the uniform-window mean, the worst-case complexities are $\widetilde\Theta(n\sqrt m/\varepsilon)$ quantum and $\Theta(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_\phi\le K$, they are $\widetilde\Theta(\sqrt{mK}/\varepsilon)$ and $\widetilde\Theta(m\min\{n^2,K/\varepsilon^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.

1 Introduction

The paper asks how many snapshot-adjacency bits are needed to estimate scalar summaries of zigzag lifetimes. It replaces barcode computation with random-window rank estimation and classifies query complexity in dense and leakage-controlled sparse regimes.

1 Introduction

  • Sampling R uniform times makes the expected generalized rank of the window between their extrema equal the persistence statistic, without computing a barcode.For graphs, window rank becomes an average of edge and component counts on the intersection graph.Source: §1 · p. 2
  • The estimator framework needs no spectral gap, prepared homology state, or QRAM, and its algorithms scale with the statistic’s value.The paper also establishes randomized lower bounds against fully adaptive querying.Source: §1 · pp. 2–3
  • For fixed power weights x^r with r ≥2 and the uniform-window mean, quantum complexity is ˜Θ(n√m/ε), versus Θ(n^2m) randomized queries.The randomized lower bound requires reading a constant fraction of the input, even with error n/4; for constant ε the quantum bound is the square root of the randomized one.Source: §1 · p. 2
  • Sparse-instance optimality is shown under a split-leakage promise and Fϕ(G) ≤ K; logarithmic-degree power and binomial weights meet the leakage condition.Fixed-power weights have constant leakage, so the decoy construction breaks the sparse promise and whether they are easier on sparse instances remains open.Source: §1 · pp. 2–3
  • Fewer than m rational-weight statistics cannot determine the positive-lifetime histogram.The paper frames this as evidence that the scalar-estimation problem is not disguised barcode computation.Source: §1 · p. 3
  • The query bounds concern snapshot access; with an explicit update stream or searchable edge-lifetime index, the complete barcode is computable in near-linear time.The paper reports query classifications separately from gate work, depth, workspace, and output.Source: §1 · p. 3

2 Problem Setup

The setup models a temporal graph as adjacency snapshots accessible one bit at a time, then defines persistence statistics through randomly sampled windows. For the intersection zigzag, the expected generalized rank of such a window equals the weighted lifetime statistic.

2 Problem Setup

  • The temporal graph consists of simple undirected snapshots on a common labeled vertex set; queries return adjacency bits, with quantum queries allowed in superposition and classical queries adaptive.No adjacency list, update list, edge-lifetime index, component oracle, or QRAM is supplied.Source: §2 · p. 3
  • For a snapshot window, the intersection graph is the intersection of its snapshots, and its generalized rank is the circuit rank of that graph.The setup defines rank as the rank of the map from the limit to the colimit of H1 for the restricted zigzag.Source: §2 · p. 3
  • A bar’s snapshot lifetime counts supported snapshot nodes, while a PGF-weighted statistic sums φ(ℓ_b/m) over bars.The statistic includes normalized degree-r total persistence and uses an input-independent random variable R to define φ.Source: §2 · p. 4

3 Persistence Statistics from Random Windows

  • Sampling R uniform times and taking the window between their extrema makes expected generalized rank equal the PGF-weighted persistence statistic.The uniform-window mean is itself a PGF weight, with R=1 of probability 1/(m+1) and R=2 otherwise.Source: §3 · p. 4

4 Quantum and Classical Estimators

The estimators turn sampled-window edge and component counts into additive-εn estimates, with supplied-density and adaptive quantum variants. In the dense regime, matching lower bounds establish Θ(n√m/ε) quantum and Θ(n²m) randomized complexity for fixed powers r ≥ 2 and the uniform-window mean.

4 Quantum and Classical Estimators

  • The supplied-K quantum estimator returns an additive-εn estimate with a deterministic worst-case query budget; its component estimate uses dyadic-scale reversible exploration.Each adjacency query to a window intersection is implemented by searching for a missing snapshot, at eO(√m) snapshot-query cost.Source: §4 · p. 5
  • Without a supplied bound on F, the adaptive quantum estimator retains an instance-sensitive query bound, with a deterministic cap.A dummy-density bootstrap estimates the budget, and the cap is the dense budget.Source: §4 · p. 5
  • The randomized estimator achieves additive-εn accuracy by Bernstein sampling for edges and dyadic breadth-first-search sampling for components, or by reading all O(n²m) bits.Its variance bound is ē ≤ K + n.Source: §4 · p. 5

5 Matching Bounds in the Dense Regime

  • For fixed integer r ≥ 2, estimating S_r or A to additive error εn (n ≥ 192, m ≥ 3, 1/n ≤ ε ≤ 1/4) requires Ω(n√m/ε) quantum and Ω(n²m) randomized queries.Source: §5 · p. 6

6 Matching Bounds under a Low-Density Leakage Promise

The low-density classification makes the lower bound conditional on a central split-leakage promise for the weight and the promise Fϕ(G) ≤ K. Leakage measures the largest weighted mass retained when a full bar is split by deleting one central snapshot.

6 Matching Bounds under a Low-Density Leakage Promise

  • Central split leakage is the largest weighted mass retained when a full bar is split by one missing central snapshot.The leakage promise enters only the lower bounds; the upper bound holds for every weight.Source: §6 · p. 6
  • The leakage-controlled classification applies to sampleable weights satisfying the leakage condition, on inputs promised to have Fϕ(G) ≤ K.The stated upper bounds are worst-case because K is supplied; the adaptive no-K result is a separate theorem, not part of this minimax equality.Source: §6 · p. 6
  • The randomized lower bound is Ω(m min{n², K/ε²}) against adaptive querying, using transcript censoring to control divergence.The quantum lower-bound sketch uses all-one rows and split rows while keeping related inputs within the statistic promise.Source: §6 · p. 7

7 Weight Functions and Resources

Logarithmic-degree power weights satisfy the stated leakage condition, while the resource discussion describes their window-preparation and workspace costs. Separately, fewer than m rational PGF weights cannot determine the positive-lifetime histogram.

7 Weight Functions and Resources

  • For ϕr(x) = x^r, λϕr,m ≤ 2(2/3)^r, so the leakage promise holds at logarithmic degree.A central split leaves two pieces of normalized length at most 2/3.Source: §7 · p. 7
  • Window preparation uses eO(rmax log m) gates and O(rmax log m) qubits; workspace includes an explicit discovered list of O(ε⁻¹ log n) qubits.The supplied-K algorithm's gate work includes oracle calls, window preparation, and list membership.Source: §7 · p. 7

8 Limits of Recovering the Positive-Lifetime Histogram

  • Bars with zero snapshot lifetime are invisible to these PGF weights, and even the positive-lifetime histogram requires many independent weighted statistics.Source: §8 · p. 7
  • Fewer than m rational-coefficient PGF weights can give identical statistic values for two graph sequences with different positive-lifetime histograms.A common spanning star realizes the histograms using one chord per requested bar over a contiguous block.Source: §8 · p. 7

9 Related Work

Prior work provides persistence summaries and efficient barcode algorithms under update-stream access, while this paper studies snapshot-bit query complexity. The proofs connect persistence-weighted statistics to sampled window ranks, and the discussion identifies extensions to sparse instances and higher-dimensional zigzags.

9 Related Work

  • Given an explicit update sequence, the graph zigzag barcode is computable in near-linear time, with faster general algorithms; this paper’s snapshot-bit lower bounds do not apply to update-stream methods [19, 20].Source: §9 · p. 8

10 Discussion and Open Problems

  • Two open questions are whether constant-leakage weights permit faster sparse-instance algorithms and whether degree-k simplicial-zigzag statistics admit sublinear sampling.The first question is posed for fixed powers x^r with Fϕ ≤ K ≪ n^2; the second concerns the absence of two-dimensional faces in the current identity.Source: §10 · p. 9

A Proofs for Sections 2 and 3

  • For a degree-one bar, the probability that all sampled times lie in its support is (ℓ_b/m)^r, yielding the PGF-weighted statistic after averaging over R.The generalized rank is additive over intervals, and the graph identity follows from the common-cycle-space characterization and Euler’s formula.Source: A Proofs for Sections 2 and 3 · p. 9
  • A constant PGF term is excluded because it would count bars containing no sampled snapshot, which a nonempty random window cannot represent.Rescaling the statistic by C rescales the required additive-error precision by C and the 1/ε² terms by C².Source: A Proofs for Sections 2 and 3 · p. 9
  • A uniformly chosen nonempty snapshot window corresponds to R = 1 with probability 1/(m + 1) and R = 2 with probability m/(m + 1).A bar spanning ℓ consecutive snapshots contains ℓ(ℓ + 1)/2 such windows.Source: A Proofs for Sections 2 and 3 · p. 9

B.1 Dyadic reciprocal-size decomposition and proofs of the estimators

The estimator reduces the target to average edge and component counts over sampled intersection graphs. Dyadic reciprocal-component estimates and edge counting yield quantum and classical procedures, with a bootstrap supporting instance-sensitive cost when a bound is not supplied.

B.1 Dyadic reciprocal-size decomposition and proofs of the estimators

  • F = ē − n + c̄, and F ≤ ē ≤ F + n − 1, so the edge-count estimate can use K + n as its scale.The component term is estimated separately and its cost is absorbed by the edge term because K + n ≥ n.Source: §B.1 · p. 10
  • The quantum estimator combines amplitude estimation of intersection edges with a dyadic component estimator, then returns ē − n + c̄.Each intersection-edge query is implemented using snapshot-bit queries, and the edge term absorbs the component-estimation cost.Source: §B.1 · p. 10
  • A bootstrap estimates an upper bound from marked edge samples, allowing the quantum procedure to adapt its cost to F while retaining a deterministic dense-instance cap.The bootstrap requires sufficiently small circuit error; constant simulation error would invalidate the stated instance-sensitive expected bound.Source: §B.1 · pp. 10–11
  • The classical estimator uses Õ((K + n)/ε²) samples for edge counts, adds component estimation, and can instead read all O(n²m) input bits.It chooses the cheaper of the sampling and full-input branches.Source: §B.1 · p. 11

B.2 Full proof of quantum component estimation

The appendix supplies a dyadic quantum component estimator, a classical density bootstrap for unknown bounds, and a real-valued-output adversary lemma. Together these establish component-count procedures and support lower bounds for approximation.

B.2 Full proof of quantum component estimation

  • The coherent dyadic component estimator achieves additive error εn/2 with Õ(√n/ε) adjacency queries.It explores a uniform vertex’s component with bounded searches, estimates level contributions, and controls sampler bias and amplitude-estimation error.Source: §B.2 · pp. 11–12

B.3 Classical density bootstrap without a supplied bound

  • A classical bootstrap estimates a constant-factor upper bound from dummy-augmented edge samples, then uses it to set the final estimator’s budget.The procedure has deterministic cap O(n²h), and the same good bootstrap event gives its instance-sensitive cost and high-probability guarantee.Source: §B.3 · p. 12

C.1 Metric-output adversary lemma

  • For real-valued approximation, the biregular adversary lemma bounds quantum queries when related inputs require disjoint acceptable output sets.The proof bounds per-query progress using the maximum related-neighbor counts at each query position.Source: §C.1 · pp. 12–13

C.2 Proof of Theorem 5.1

The proofs use independent optional-edge rows to construct persistence changes and information-hard input families. They establish a fully adaptive classical lower-bound argument and develop related censored-row information bounds for the instance-sensitive results.

C.2 Proof of Theorem 5.1

  • A spanning-star gadget makes each optional chord an independent fundamental cycle; a missing edge splits its full-lifetime bar into two shorter bars.For fixed r ≥ 2 and the uniform-window statistic A, the split-row contribution is at most 5/9 of a full bar’s weight.Source: §C.2 · p. 13
  • The quantum lower-bound construction relates inputs by erasing zeros in split rows, so the acceptable output intervals are disjoint.The proof invokes the real-valued-output adversary progress bound rather than requiring a single global Boolean threshold.Source: §C.2 · pp. 13–14
  • Theorem 5.1’s classical lower bound follows from distinguishing input distributions whose statistic means differ, while informative queries reveal only a censored-row response.The transcript argument gives Ω(n²m) queries, and the paper states that the classical lower bounds hold against fully adaptive algorithms.Source: §C.2 · p. 14

D Proofs for Section 6

  • For the quantum instance-sensitive lower bound, related inputs satisfy the promise and have disjoint additive-error output intervals, enabling the metric-output adversary argument.The relation is formed by erasing zeros from selected split rows.Source: D Proofs for Section 6 · p. 14
  • For the censored-row model, adaptive transcripts have KL divergence at most 128QΔ²/(p−L), including ordinary queries and reveals.A reveal consumes at least L/4 previous queries, and the row is resolved after a zero or reveal.Source: D Proofs for Section 6 · pp. 14–15
  • The sparse-instance classical lower bound conditions product distributions on promise-supported good events, then uses their transcript separation to contradict low-query estimation.The conditioning changes each transcript distribution by at most 1/32 in total variation.Source: D Proofs for Section 6 · pp. 15–16

E Proofs for Sections 7 and 8

The proof sketches bound central split weights using the fact that each piece has normalized length at most 2/3. They give sufficient logarithmic-degree choices for power and binomial weights.

E Proofs for Sections 7 and 8

  • For the power weight x^r, r ≥ ⌈log_(3/2)(64n/ε)⌉ is a sufficient degree choice.The bound follows from monotonicity of x^r on central splits.Source: E Proofs for Sections 7 and 8 · pp. 16–17
  • On a central split, both normalized piece lengths are at most 2/3, allowing monotonicity to bound the power-weight leakage.Source: E Proofs for Sections 7 and 8 · p. 17
  • For the binomial weight x((1 + x)/2)^s, s ≥ ⌈log_(6/5)(128n/(3ε))⌉ is sufficient.For x ≤ 2/3, x((1 + x)/2)^s ≤ (2/3)(5/6)^s; the two split pieces are then bounded and rearranged.Source: E Proofs for Sections 7 and 8 · p. 17

E.1 Resource accounting

The resource discussion describes sampling-window preparation and precision controls, alongside limits on recovering histograms and bar positions from scalar statistics. It also gives a non-identifiability construction for fewer than m weighted statistics.

E.1 Resource accounting

  • For non-power-of-two m, uniform labels in [m] can be prepared to desired accuracy with polylogarithmic gates, without graph data or QRAM.Power weights use r independent uniform time registers and reversible minimum/maximum computation; binomial weights use s Hadamard control bits and a mandatory time register.Source: §E.1 · p. 17
  • The sampling distribution is compiled to total-variation error ζ = O(ε/n), while coherent subroutines are compiled to inverse-polynomial operator error in the total-use cap.The distribution error is chosen so its effect on the target expectation is at most Bnζ.Source: §E.1 · p. 17
  • The parallel comparator tree has depth eO(log rmax log m) and uses O(rmax log m) qubits.Source: §E.1 · p. 17
  • Because 0 ≤ Fϕ ≤ Bn, the classical scalar output requires O(log(n/ε)) bits.Source: §E.1 · p. 17
  • Fewer than m weighted statistics can assign identical statistic vectors to distinct positive-lifetime histograms, realizable with optional edges on contiguous snapshot blocks.Exact power moments through S_m determine the histogram, but require m scalar outputs and do not recover bar positions.Source: §E.1 · pp. 17–18

F Finite Sanity Checks

Finite checks test identities, split-weight bounds, parameter inequalities, KL bounds, and a dyadic expansion over specified finite ranges; the authors state these checks do not replace proofs. The disclosure describes AI assistance and author verification.

F Finite Sanity Checks

  • For m ≤ 12, direct enumeration agrees with the power-weight identity, and the uniform-window weight agrees with (x + mx^2)/(m + 1).Source: F Finite Sanity Checks · p. 18
  • For 3 ≤ m < 80, tested central split weights for 2 ≤ r ≤ 8 and the uniform-window weight are at most 5/9.Integer-rounding endpoints in the logarithmic-degree bounds for power and binomial weights were also checked separately.Source: F Finite Sanity Checks · p. 18
  • At the stated boundary values, the listed inequalities, promise support, mean separation, and Chebyshev budget all hold; a dense grid also satisfies the numerical KL upper bounds.The checks cover n = 214 with specified ε and K values, and KL bounds 64∆^2/L before reveal and 16∆^2/p− at reveal.Source: F Finite Sanity Checks · p. 18
  • For 2 ≤ n < 200, the dyadic reciprocal-size expansion has nonnegative tail at most 2^-J for the stated precision values.These checks are finite sanity tests, not substitutes for proofs.Source: F Finite Sanity Checks · p. 18

AI Disclosure

  • ChatGPT and Claude assisted with literature review, brainstorming, proof checking, and language polishing; the authors say they verified the arguments and references and take responsibility for the final content.Source: AI Disclosure · p. 22
Loading 2609.05813v1…