Exact quantum algorithms for composed Boolean functions

The paper in detail

Write the outer function as a signed multilinear polynomial \(H\) on \(\{-1,1\}^n\), so that \(f\circ g\) is \(H(z)\) with \(z_i=(-1)^{g(x^{(i)})}\). An approximate inner algorithm with error \(\varepsilon\) on block \(i\) has output bias \(b_i\), and the residual \(e_i=z_i-b_i\) has \(\lvert e_i\rvert\le2\varepsilon\). Because \(H\) is multilinear of degree \(D\), Taylor expansion about \(b\) is exact and stops at order \(D\).

The algorithm implements each term of that expansion coherently. The derivative factor is a correlation of \(H\) with a parity under a product distribution, which the outer exact algorithm can produce by conjugating each of its queries with inner operations, at a cost of order \(Q_E(f)\) times the inner cost regardless of the set size. The residual factor is implemented by actually reading the at most \(D\) blocks in the set, costing about \(mD\) queries. Summing over sets with input-independent weights yields a circuit whose return amplitude is \(H(z)/2\), and exact amplitude amplification turns this known-magnitude amplitude into a clean phase.

A second construction interpolates each approximate inner reflection toward the exact one; the return amplitude becomes the polynomial \(H(b+\lambda(z-b))\) in \(\lambda\), of degree at most \(D\), so the error threshold can be \(1/(4D)\) rather than \(1/(4n)\). For recursive functions the theorem is applied with an exact outer tree and an approximate inner tree whose depths balance the degree cost against the adversary cost.

Open questions include whether the subexponential factors can be removed and whether these query-efficient algorithms can also be made time-efficient.

Transferable methods

1. Exact multilinear expansion about the approximate biases

   Approximate inner answers give a point \(b\) near the true sign vector \(z\). Expanding \(H(z)\) around \(b\) produces only finitely many terms, each a product of small residuals and a derivative that is bounded by one. That is what makes an exact correction affordable.

   Expanding each monomial of \(H(b+e)\) gives, with no remainder and no factorials, \[H(z)=\sum_{S\subseteq[n],\,\lvert S\rvert\le D}e_S\,\partial_SH(b),\qquad e_S=\prod_{i\in S}e_i.\] Each derivative is a correlation: let \(Y_i\) be independent signs, uniform for \(i\in S\) and with mean \(b_i\) otherwise; then \(\partial_SH(b)=\mathbb E[H(Y)\prod_{i\in S}Y_i]\), because a uniform sign that appears once averages a monomial to zero, and one that appears twice cancels. As \(H(Y)Y_S=\pm1\), \(\lvert\partial_SH(b)\rvert\le1\).

   Editorial remark on normalisation: with \(\varepsilon=1/(4n)\), the residual weights satisfy \[\sum_k\binom nk(2\varepsilon)^k\le\Bigl(1+\frac1{2n}\Bigr)^n<e^{1/2}<2,\] consistent with the paper's statement that the weights sum to less than two and can be padded to exactly two, giving return amplitude \(H(z)/2\) and the known success probability \(1/4\) that exact amplification requires.

   Editorial check: for NAE₃, \(H(y)=-\tfrac12+\tfrac12(y_1y_2+y_1y_3+y_2y_3)\) has degree 2. With random biases within 0.1 of \(z\), the expansion reproduces \(H(z)=-1\) to rounding error, and the correlation formula matches \(\partial_{\{1,3\}}H(b)=1/2\) exactly.

   How to reuse it

   Whenever a zero-error answer is a low-degree multilinear function of quantities that can be estimated cheaply, expand about the estimates: the correction involves only sets of size at most the degree, and the derivatives are bounded correlations that can be generated by sampling rather than computed.

2. Balancing degree against simulation cost

   The bound has two terms with different growth: \(mD\) (read the selected blocks) and \(Q_E(f)\,Q(g)\) (simulate the outer algorithm). Choosing the inner layer so that the two terms grow at the same rate gives the best exponent, and the same balancing produces the paper's separations.

   For \(F_k=\mathrm{NAE}_3^{\circ k}\) the paper uses \(\deg F_k=2^k\), \(\mathrm{Adv}^{\pm}(F_k)=a^k\) with \(a=3/\sqrt2\), and input length \(3^k\). In Theorem 1.7 the inner function is \(\mathrm{OR}_{m_k}\) with \(m_k=\lceil(9/8)^k\rceil\), so \(\deg=m_k\) and \(Q=\Theta(\sqrt{m_k})\).

   Editorial check of the exponent: the correction term is \(m_k\deg F_k=(9/8)^k2^k=(9/4)^k\), and the simulation term is about \(a^k\sqrt{m_k}=\bigl(\tfrac3{\sqrt2}\cdot\tfrac{3}{2\sqrt2}\bigr)^k=(9/4)^k\), so both grow at the same rate. The input length is \(N_k=(27/8)^k\) and \((27/8)^{2/3}=9/4\), so \(Q_E(G_k)=N_k^{2/3+o(1)}\) while sensitivity is \(N_k\): exponent \(3/2\).

   How to reuse it

   For composed constructions, tabulate how each cost term grows per level and tune the inner block to equalise them. The same bookkeeping, with degree and adversary rates in place of the two terms, yields the composition limit \(\max\{\deg h,\mathrm{Adv}^{\pm}(h)\}\).

Source: Sections 1.2, 3.1–3.2 (Eq. 3.3, Lemma 3.2); Theorems 1.3 and 1.7. Based on the linked paper version. Derivations marked as editorial, and suggested uses in other problems, are editorial guidance rather than results of the paper.

Context & limitations

Why it matters. Exact quantum query complexity does not compose multiplicatively, and the two costs are governed by different parameters of the outer function: its exact complexity pays for the simulation, its degree for the correction. The near-quadratic separation between randomized and exact quantum queries for total functions improves the previous exponent \(3/2\) from pointer functions.

Limitations. The recursive results are asymptotic, with factors such as \(e^{O((\log k)^2)}\) and gadget-dependent polylogarithms; separations hold for specially constructed families. The algorithms count queries, not running time. The authors state that the main proof ideas were generated by GPT-6 Astra and GPT-6.1 Sol while they studied earlier work, and that they take responsibility for correctness; no formal verification is reported.

Description based on the full arXiv HTML of v1, read 2026-11-13: the abstract and AI statement, Section 1 (all results and proof strategy), Sections 3.1–3.2 (expansion and Lemma 3.2), and Sections 5 and 5.1 (recursive NAE parameters). The circuit constructions of Sections 3.3–3.5 and 4, and Sections 6–11, were read for structure only. The expansion identity and Lemma 3.2 were checked on NAE₃ with random biases, and the exponent balance of Theorem 1.7 was recomputed.