← 研踪 PaperTrailarXiv:2611.16412 · v1
Exact Quantum Algorithms for Composed Boolean Functions
首次提交 2026-11-12 15:24
版本更新 2026-11-12 15:24
雷达观测 2026-11-13 14:15
摘要
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 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)$. The composition limit also allows to transfer separations from $Q_{\varepsilon}$ and $°$ 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.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-12 15:24 · 最新观测版本
Exact Quantum Algorithms for Composed Boolean Functions
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 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)$. The composition limit also allows to transfer separations from $Q_{\varepsilon}$ and $°$ 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.
查看此版本解读 →查看此版本原文 ↗