Open Research Index

Adversary bounds and the polynomial method for quantum queries

Troy Lee

Palomar Registrypalomar/PALOMAR-2026-09-29-000001Sep 29, 2026quant-phscore 0

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…

SourceRepositoryJSON

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/palomar/PALOMAR-2026-09-29-000001
curl -X POST /api/v1/records/palomar/PALOMAR-2026-09-29-000001/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/palomar/PALOMAR-2026-09-29-000001/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'