{"id":"palomar/PALOMAR-2026-09-29-000001","url":"https://github.com/troyjlee/quantum-query-complexity/tree/517ba85eb211232771429804d8583e3f52b9d541","json":"https://data.palomar-registry.org/entries/PALOMAR-2026-09-29-000001-v1.json","repo":"https://github.com/troyjlee/quantum-query-complexity","tags":["quant-ph","cs.CC","msc:68Q12","msc:81P68","lean","quantum-computing","query-complexity","adversary-bounds"],"score":0,"title":"Adversary bounds and the polynomial method for quantum queries","trust":"high","domain":"quant-ph","source":"palomar","authors":["Troy Lee"],"reviews":0,"subject":"quant-ph","summary":"Lean proofs of strong duality and exact block composition for the negative-weight adversary bound on total Boolean functions, explicit constant-factor characterizations of bounded-error quantum query complexity in value and Boolean XOR oracle models, and uniform extraction of query algorithms from supplied promise dual certificates. The submission also proves that every output probability of a q-query algorithm on Boolean inputs has a real polynomial representation of degree at most 2q in each model. Seven statements are compared against a standalone Mathlib-only specification of the finite…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"verified":true,"discussed":0,"published":"2026-09-29","reactions":{},"formalized":true,"formalizes":[{"title":"Negative weights make adversaries stronger","identifier":"https://arxiv.org/abs/quant-ph/0611054v2","relationship":"adapts"},{"title":"Quantum query complexity of state conversion","identifier":"https://arxiv.org/abs/1011.3020v2","relationship":"adapts"},{"title":"Reflections for quantum query algorithms","identifier":"https://arxiv.org/abs/1005.1601v1","relationship":"adapts"},{"title":"The quantum query complexity of composition with a relation","identifier":"https://arxiv.org/abs/2004.06439v1","relationship":"formalizes"},{"title":"Quantum Lower Bounds by Polynomials","identifier":"https://arxiv.org/abs/quant-ph/9802049v3","relationship":"adapts"}]}