{"id":"arxiv/2610.03914","url":"https://arxiv.org/abs/2610.03914","tags":["quant-ph"],"score":0,"title":"Quantum Query Complexity and Span Programs from Pre-Geometry","domain":"quant-ph","source":"arxiv","authors":["Justin Roy Cox","Neil Epstein","Zhirui Hu","Michael Jarret","Thomas De Mastri"],"reviews":0,"subject":"quant-ph","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-10-02","reactions":{}}