{"id":"arxiv/2611.16412","url":"https://arxiv.org/abs/2611.16412","tags":["cs.CC","quant-ph"],"score":0,"title":"Exact Quantum Algorithms for Composed Boolean Functions","domain":"cs.CC","source":"arxiv","authors":["Gagan Chiruvella","Chandrima Kayal","Rajat Mittal","Manaswi Paraashar","Nitin Saurabh"],"reviews":0,"subject":"cs.CC","summary":"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 $$ 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. We first establish the construction with an arity-dependent…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-12","reactions":{}}