Quantum Query Complexity and Span Programs from Pre-Geometry

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 Adv plus or minus Q(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< Adv plus or minus Q R(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 Ω(N 0.7324867), an explicit quantum algorithm using O(N 0.6500178) queries, and Q(F)=Θ(N α) for 0.6204277 <α<0.6229063.