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 $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.

Quantum Physics (quant-ph); Computational Geometry (cs.CG)

arXiv:2609.05813 [quant-ph]

(or arXiv:2609.05813v1 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2609.05813 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.