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}^{\pm}_{\mathcal 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<\mathrm{Adv}^{\pm}_{\mathcal 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 $\Omega(N^{0.7324867\ldots})$, an explicit quantum algorithm using $O(N^{0.6500178\ldots})$ queries, and $Q(F)=\Theta(N^\alpha)$ for $0.6204277\ldots<\alpha<0.6229063\ldots$.

arXiv:2610.03914 [quant-ph]

(or arXiv:2610.03914v1 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2610.03914 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

appendix_file_map.json

audit_classical_bounds/MANIFEST.sha256

audit_classical_bounds/README.md

audit_classical_bounds/fbs_certificates.json

audit_classical_bounds/sabotage_certificate.json

audit_classical_bounds/verify_classical.py

r10_adversary_reproducibility_archive/MANIFEST.sha256

r10_adversary_reproducibility_archive/README.md

r10_adversary_reproducibility_archive/common/conventions.json

r10_adversary_reproducibility_archive/common/r10_common.py

r10_adversary_reproducibility_archive/common/verify_common.py

r10_adversary_reproducibility_archive/lower/DERIVATION_PROVENANCE.md

r10_adversary_reproducibility_archive/lower/expanded_lower_matrices.json

r10_adversary_reproducibility_archive/lower/lower_certificate.json

r10_adversary_reproducibility_archive/lower/source_orbits.json

r10_adversary_reproducibility_archive/lower/verify_lower.py

r10_adversary_reproducibility_archive/upper/RECONSTRUCTION_NOTES.md

r10_adversary_reproducibility_archive/upper/exact_summary.json

r10_adversary_reproducibility_archive/upper/factor32_dyadic.json

r10_adversary_reproducibility_archive/upper/verify_upper.py

r10_adversary_reproducibility_archive/verify_all.py

r10_atlas/INTRINSIC_ATLAS_FREEZE.json

r10_atlas/R10_ATLAS_MANIFEST.sha256

r10_atlas/README.md

r10_atlas/build_atlas.py

r10_atlas/r10_port_geometry.json

r10_atlas/r10_response_atlas.json

r10_atlas/verification_results.json

r10_atlas/verify_atlas.py

r10_program_reproducibility/MANIFEST.sha256

r10_program_reproducibility/README.md

r10_program_reproducibility/verify_programs.py

r10_recursive_verification/MANIFEST.sha256

r10_recursive_verification/README.md

r10_recursive_verification/common.py

r10_recursive_verification/verify_all.py

r10_recursive_verification/verify_base_r10.py

r10_recursive_verification/verify_recursive_boolean.py

r10_recursive_verification/verify_response_recurrence.py

(37 additional files not shown) You must enabled JavaScript to view entire file list.

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.