Quantum Query Complexity and Span Programs from Pre-Geometry

Abstract

Span programs provide a general method for designing quantum query algorithms, and for Boolean coordinate queries their optimum cost agrees with the general adversary bound. We develop a matroidal organization of this optimization that separates dependence data determined by the query problem from the dependence structure chosen by a span program. The resulting source matroid records query dependence, target determination, and separation data, while a program matroid records dependencies among the target and response-labeled input elements of a candidate program. When a query problem admits a source matroid, we use its structure to organize adversary upper and lower bounds. For separating binary query sets in this setting, the global matroid-span-program optimum equals ${\mathrm{Adv}}_{\mathcal{Q}}^{\pm }(f)$. For a fixed regular program matroid, projective uniqueness reduces optimization over real representations to positive element weights. We express positive and negative costs as weighted basis ratios and derive exact $1$-, $2$-, and $3$-sum reductions, giving a compositional evaluation of the fixed-weight objective along a Seymour decomposition. For pointed $R_{10}$ closure, exact certificates give $3.9087553<{\mathrm{Adv}}_{{\mathcal{Q}}_R}^{\pm }(f_R)<3.9301$. The natural $R_{10}$ program has optimized cost $5$, while another regular program has cost at most $\sqrt{87/5}$. Recursive self-composition yields a family on $N$ input bits with randomized query complexity $\Omega (N^{0.7324867\dots })$, an explicit quantum algorithm using $O(N^{0.6500178\dots })$ queries, and $Q(F)=\Theta (N^{\alpha })$ for $0.6204277\dots <\alpha <0.6229063\dots$.

91 pages