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 $φ(x)=\mathbb{E}[x^R]$, the statistic $F_φ=\sum_bφ(\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_φ$. 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_φ$ 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Θ(n\sqrt m/\varepsilon)$ 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_φ\le K$, they are $\widetildeΘ(\sqrt{mK}/\varepsilon)$ and $\widetildeΘ(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.
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)=E[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 O(m(K+n)/ε) queries when a bound K≥Fφ is supplied, against O(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 Θ(nm/ε) 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.
We study the minimum weight cycle problem (MWC) and the minimum weight triangle problem (MWT) in the quantum query model, for n-vertex graphs with integer edge weights in [M] given by their adjacency matrix. Roditty and Vassilevska Williams showed that the two problems are classically equivalent. We show that an exact minimum weight cycle of an undirected graph can be found with O~(n19/12) queries, while Ω(n3/2) queries are necessary. The algorithm learns only the n7/6 lightest vertex pairs, uses quantum counting to locate weight thresholds above them, applies a strict form of the Moore bound to bound the optimum and the size of each weight class, and searches the classes for the few heavy edges of an optimal cycle with nested quantum walks. A simpler version gives O~(n5/3) queries, and searching for fewer heavy edges trades queries for approximation, with a 2-approximation in O~(n8/5) queries and a tight O(logn)-approximation in O~(n3/2) queries. In contrast, MWT costs O(n9/7logM) queries, so the classical equivalence becomes a polynomial separation. For cycles of constant length we give explicit exponents, such as O~(n125/83) for the minimum weight 5-cycle, and we prove that deciding whether a graph has a k-cycle of total weight exactly zero requires Ω(n2−2/(⌊k/2⌋+1)) queries for every constant k≥4. Finally, non-adaptive learning graphs cannot beat n2 for cycles of about logn edges, and we conjecture that exact MWC on directed graphs requires n2−o(1) queries.
Quantum counting is a fundamental quantum algorithm that estimates the fraction of marked elements using a membership oracle, achieving a quadratic speedup over classical sampling. The membership oracle, however, assumes exact labeling of each element, but this assumption fails when the labels are inherently probabilistic. We study quantum counting with \emph{Bernoulli oracles}, where given m Bernoulli distributions with unknown biases p1,…,pm and a gap parameter Δ, the goal is to estimate the fraction ρ of \emph{positive} distributions (pi≥1/2+Δ) to within additive error ε. We prove an upper bound of O~(Δερ+Δε1) queries, achieving a quadratic speedup over the classical sample complexity. % of Θ(ρ/Δ2ε2).
Our algorithm first uses the Quantum Singular Value Transformation (QSVT) to coherently amplify the bias gap without collapsing the superposition over distributions, and then applies two-stage adaptive amplitude estimation. We complement this upper bound with a near-matching lower bound of Ω(ρ/(Δε)) via a new composition theorem for the quantum adversary method in the Boolean-over-average-case direction. For the special case of a constant gap Δ=Θ(1), which corresponds to the bounded-error oracle where each query returns the correct label with constant probability, our bounds specialize to O~(ερ+ε1) and Ω(ερ), thereby characterizing the query complexity of quantum counting with bounded-error oracles.
We study the quantum query complexity of several basic graph problems. 1) We prove a tight Θ(n3/2) bound for finding a maximum-out-degree vertex in an n-vertex tournament, resolving a conjecture of Mande, Paraashar, and Saurabh [FSTTCS'23]. 2) Using the same proof idea, we give a direct proof that finding a maximum-degree vertex in an n-vertex undirected graph requires Θ(n3/2) quantum queries, a bound implicit in the work of Apers and Lee [CCC'21]. Both lower bounds above hold even for computing only the maximum degree or maximum out-degree. 3) We also study Maximum (k,n−k)-Cut, which asks for the largest cut with one side of size k. For every constant k≥1, we give an O(n2−1/(k+1))-query quantum algorithm. 4) We establish a reduction to Maximum (k,n−k)-Cut involving k-Graph Collision, which asks whether the marked vertices of a known graph contain a k-clique. For k≥3, this yields unconditional lower bounds with exponents strictly larger than 3/2, showing that this problem is strictly harder than computing maximum degree. Additionally, under a conjecture we propose for k-Graph Collision, the reduction yields a lower bound matching our upper bound above.
We consider the quantum query complexity of local search as a function of graph geometry. Given a graph G=(V,E) with n vertices and black box access to a function f:V→R, the goal is find a vertex v that is a local minimum, i.e. with f(v)≤f(u) for all (u,v)∈E, using as few oracle queries as possible. We show that the quantum query complexity of local search on G is Ω(gn43), where g is the vertex congestion of the graph. For a β-expander with maximum degree Δ, this implies a lower bound of $ Ω\bigl(\frac{\sqrtβ \; n^{\frac{1}{4}}}{\sqrtΔ \; \log{n}} \bigr)$. We obtain these bounds by applying the strong weighted adversary method to a construction by Brânzei, Choo, and Recker (2024). As a corollary, on constant degree expanders, we derive a lower bound of Ω(lognn41). This improves upon the best prior quantum lower bound of $Ω\bigl( \frac{n^{\frac{1}{8}}}{\log{n}}\bigr) $ by Santha and Szegedy (2004). In contrast to the classical setting, a gap remains in the quantum case between our lower bound and the best-known upper bound of O(n31) for such graphs.
Determining whether every trajectory of the linear system x˙=Ax converges to zero (or, equivalently, whether A is Hurwitz stable) is a fundamental problem in control theory. It arises, for example, in verifying the stability of feedback controllers and state observers, as well as of linearized dynamical models. We study the quantum query complexity of deciding whether a matrix A∈Cn×n is Hurwitz stable, given an exact normalized block-encoding of A. The query complexity is characterized in terms of the system dimension n and a supplied lower bound 0<ν≤ωA on the imaginary-axis distance ωA:=mint∈Rσmin(A−itI), where σmin(A) is the smallest singular value of A. We prove a query-complexity lower bound of Ω(n/ν), which holds even when A is restricted to be real and diagonal. For general matrices with nonzero ωA, we encode an approximation of the right-half-plane spectral projector sign+(A):=(I+sign(A))/2 as a block of a matrix inverse, where A is Hurwitz if and only if the projector is zero. To test this, we produce a quantum algorithm which determines if a (β,b,1/(4n))-block-encoded projector matrix (like sign+(A)) is zero or not; for constant success probability, it has complexity Θ(βn). When the zero test is applied to specific approximations of sign+(A), this yields an upper bound of O(nν−2log(n/ν)) queries in the general case, and O(nν−1logn) when A is Hermitian or normal. The latter upper bound matches the lower bound up to a logarithmic factor. Thus the dimension dependence of quantum Hurwitz testing is nearly optimal, while the remaining factor in the non-normal case isolates an open conditioning gap.
Subgraph detection asks whether an n-vertex graph, accessed through queries to its adjacency matrix, contains a copy of a fixed graph H. We prove the first unconditional superlinear lower bounds on the bounded-error quantum query complexity of this problem, answering a longstanding open question. A copy of H is a certificate of constant size, so the adversary method with nonnegative weights cannot prove superlinear lower bounds.
For every fixed r≥4, detecting the clique Kr requires nλr−o(1) queries, where λ4=19/18, the exponents λr increase strictly with r, and λr≥2−42/r+O(1/r). More generally, we prove superlinear lower bounds for detecting every fixed connected graph H with chromatic number c≥4. These bounds approach quadratic as c grows: for sufficiently large c, detection requires n2−O(loglogc/c)−o(1) queries. Chromatic number alone does not characterize the quantum query complexity of subgraph detection: we show that detecting the complete bipartite graph Kr,r requires nβr−o(1) queries, where β10=181/180 and βr≥2−O(1/r).
Our main technical result is a lower bound for finding an all-ones certificate from a known family when the input bits are sampled independently. Its proof combines Zhandry's compressed oracle [CRYPTO 2019] with conditioning on a randomly planted certificate, adapting an argument of Belovs [FOCS 2026]. Our hard instances are built from graphs containing many copies of the desired subgraph with limited overlap. For cliques, we use a construction of Gowers and Janzer [CPC 2021]; for complete bipartite graphs, we use a random construction.