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 Category: research Comments: 0 Disputed: false Division: cs Mentions: 0 Discussed: 0 Published: 2026-11-12 Page: https://delphi.science/r/arxiv/2611.16412 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…