{"arxiv_id":"2611.16412","title":"Exact Quantum Algorithms for Composed Boolean Functions","abstract":"We study exact quantum algorithms for block compositions of total Boolean functions. For an outer function $f$ of degree $D$ and an inner function $g$ on $m$ bits, we prove $$\n  Q_E(f\\circ g)=O\\!\\left(mD+Q_E(f)Q_{1/(4D)}(g)\\right). $$ The algorithm combines approximate inner evaluations with a finite exact correction. Its two costs are governed by different parameters of the outer function: exact query complexity determines the cost of simulation, whereas polynomial degree determines the number of inner blocks used in the correction.\n  We first establish the construction with an arity-dependent error threshold and then obtain the degree-dependent threshold above. For recursive ternary not-all-equal, this gives an exact algorithm using $(3/\\sqrt2)^{k(1+o(1))}$ queries asymptotically. More generally, for every fixed nonconstant total gadget $h$, we determine the exact recursive rate as $\\max\\{\\textrm{deg}(h),\\operatorname{Adv}^{\\pm}(h)\\}$ and prove $Q_E(h^{\\circ k})=\\widetilde O_h(R(h^{\\circ k})^2)$.\n  The composition limit also allows to transfer separations from $Q_{\\varepsilon}$ and $\\deg$ to exact quantum query complexity $Q_E$ (similar to fractional block sensitivity to block sensitivity transfer in Tal and Kulkarni 2016, Chicago Journal of Theoretical Computer Science). We construct a family with $s=\\operatorname{bs}=\\operatorname{fbs}\\ge Q_E^{3/2-o(1)}$, improving the previous exponent $1.1527\\ldots$. A second construction gives $R \\ge Q_E^{2-o(1)}$, improving the previous exponent $3/2$. We also allow different inner functions and give analogous quantitative separations in quantum communication.","primary_cat":"cs.CC","cross_cats":["quant-ph"],"submitted_at":"2026-11-12T07:24:01+00:00","latest_version":1,"source":"arxiv","source_label":"arXiv","source_url":null,"has_pdf":true,"has_source":false,"verdict":"ACCEPT","confidence":"HIGH","one_line_summary":"The paper proves a general composition theorem for exact quantum query complexity, leading to improved separations: sensitivity vs exact quantum exponent 3/2 and randomized vs exact quantum nearly exponent 2.","novelty_score":9.0,"correctness_risk":"medium","formal_verification":"none","upvotes":0,"downvotes":0,"pith_score":0,"inbound_count":0,"_links":{"html":"https://pith.science/paper/2611.16412","verdict":"/api/v1/verdicts/2611.16412"}}