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 Adv±𝒬(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 R10 closure, exact certificates give 3.9087553<Adv±𝒬R(fR)<3.9301. The natural R10 program has optimized cost $5$, while another regular program has cost at most √(87/5). Recursive self-composition yields a family on N input bits with randomized query complexity Ω(N0.7324867…), an explicit quantum algorithm using O(N0.6500178…) queries, and Q(F)=Θ(Nα) for 0.6204277…<α<0.6229063….
Related
- Near-Optimal Separations of Certificate Complexity from Randomized and Quantum Query Complexity
- Quantum Query Complexity Beyond the Worst Case
- Quantum Query Complexity of Tournament Solutions
- Optimal query complexity for fractional quantum evolution
- Quantum Query Complexity of Maximum Degree and its Generalizations
BibTeX
@misc{cox2026quantum,
title = {{Quantum Query Complexity and Span Programs from Pre-Geometry}},
author = {Justin Roy Cox and Neil Epstein and Zhirui Hu and Michael Jarret and Thomas De Mastri},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.03914},
eprint = {2610.03914},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.03914},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Quantum Query Complexity and Span Programs from Pre-Geometry
AU - Justin Roy Cox
AU - Neil Epstein
AU - Zhirui Hu
AU - Michael Jarret
AU - Thomas De Mastri
PY - 2026
DA - 2026/10/02
PB - arXiv
DO - 10.48550/arxiv.2610.03914
UR - https://arxiv.org/abs/2610.03914
AB - 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^±_𝒬(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^±_𝒬_R(f_R)<3.9301. The natural R_10 program has optimized cost $5$, while another regular program has cost at most √(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….
ER -