betaFeedback

WorksComputer Science

Exact Quantum Algorithms for Composed Boolean Functions

Abstract

We study exact quantum algorithms for block compositions of total Boolean functions. For an outer function ff of degree DD and an inner function gg on mm bits, we prove QE(f∘g)=O ⁣(mD+QE(f)Q1/(4D)(g)). 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/2)k(1+o(1))(3/\sqrt2)^{k(1+o(1))} queries asymptotically. More generally, for every fixed nonconstant total gadget hh, we determine the exact recursive rate as max⁡{deg(h),Adv⁡±(h)}\max\{\textrm{deg}(h),\operatorname{Adv}^{\pm}(h)\} and prove QE(h∘k)=O~h(R(h∘k)2)Q_E(h^{\circ k})=\widetilde O_h(R(h^{\circ k})^2). The composition limit also allows to transfer separations from QεQ_{\varepsilon} and °° to exact quantum query complexity QEQ_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=bs⁡=fbs⁡≥QE3/2−o(1)s=\operatorname{bs}=\operatorname{fbs}\ge Q_E^{3/2-o(1)}, improving the previous exponent 1.1527…1.1527\ldots. A second construction gives R≥QE2−o(1)R \ge Q_E^{2-o(1)}, improving the previous exponent 3/23/2. We also allow different inner functions and give analogous quantitative separations in quantum communication.

AI statement. We used GPT-6 Astra and GPT-6.1 Sol to explore proof strategies, search for related literature, and revise the manuscript. The main proof ideas were generated by these systems when the authors used them to understand the recent work [22]. The authors explored these ideas and related questions further. The authors take full responsibility for the correctness and content of the paper.

Introduction

Composition is a basic way to construct query algorithms and create examples of separations between complexity measures of Boolean functions. Given f:{0,1}n→{0,1}f:\{0,1\}^{n}\to\{0,1\} and g:{0,1}m→{0,1}g:\{0,1\}^{m}\to\{0,1\}, the block composition f∘gf\circ g applies gg to nn disjoint input blocks and then applies ff to their outputs. An exact quantum algorithm can evaluate this composition by replacing each query to an input bit of ff with an exact computation of gg. This simulation uses both algorithms as black boxes, but it also pays for an exact inner computation at every outer query. Is this algorithm the best possible (in terms of number of queries used), or can we improve it? In other words, is

QE(f∘g)=Θ(QE(f)QE(g)).Q_E(f\circ g)=\Theta(Q_E(f)Q_E(g)).

For comparison, degree composes exactly, and bounded-error quantum query complexity satisfies Q(f∘g)=Θ(Q(f)Q(g))Q(f\circ g)=\Theta(Q(f)Q(g)) by the general adversary characterization and its composition theorem [19, 24, 26]. The standard bounds for exact quantum queries are

QE(f∘g)≤2QE(f)QE(g),(1)Q_E(f\circ g)\le2Q_E(f)Q_E(g), \tag*{(1)}
QE(f∘g)=Ω(max⁡{QE(f),QE(g),deg⁡(f)deg⁡(g),Q(f)Q(g)}).(2)Q_E(f\circ g)=\Omega\left(\max\{Q_E(f),Q_E(g),\deg(f)\deg(g),Q(f)Q(g)\}\right). \tag*{(2)}

Here and below the functions are nonconstant and total. The upper bound uses coherent compute–phase–uncompute simulation; the lower bounds follow from restrictions, the polynomial method, and adversary composition [7, 19, 24]. Pednekar and Podder [22] showed that exact quantum complexity need not compose multiplicatively. In particular, they gave the bound

QE(f∘OR⁡m)=O(mdeg⁡(f)+n2m).Q_E(f\circ\operatorname{OR}_{m})=O\left(m\deg(f)+n^{2}\sqrt{m}\right).

and used it to construct total functions with QE(f∘g)=o(QE(f)QE(g))Q_E(f\circ g)=o(Q_E(f)Q_E(g)).

We ask whether approximate inner computations can reduce QE(f∘g)Q_E(f\circ g) in general, while the final answer remains exact. Ordinary error reduction does not resolve this question: any nonzero probability of an incorrect answer is unacceptable. Instead, our algorithm corrects the approximate computation by an exact algebraic identity. The number of blocks involved in a correction is bounded by the polynomial degree of the outer function, which can be much smaller than its exact query complexity. Our construction applies to arbitrary total inner functions and separates the cost of simulating the outer algorithm from the cost of exact correction.

Our results

Write QεQ_{\varepsilon} for quantum query complexity with worst-case error at most ε\varepsilon, Q=Q1/3Q=Q_{1/3}, and R=R1/3R=R_{1/3} for bounded-error randomized query complexity. In the first two theorems, ff and gg are nonconstant total Boolean functions on nn and mm bits, respectively. We write D=deg⁡(f)D=\deg(f) and Ef=QE(f)E_f=Q_E(f).

Theorem 1.1 (Exact evaluation of compositions, Theorem 3.1). The composition f∘gf\circ g satisfies

QE(f∘g)≤6mD+12EfQ1/(4n)(g).(3)Q_E(f\circ g)\le6mD+12E_fQ_{1/(4n)}(g). \tag*{(3)}

The simulation of the outer algorithm uses approximate inner operations and accounts for the second term. The first term pays for the correction, which reads at most DD inner blocks in each branch.

Theorem 1.2 (Degree-dependent error threshold, Theorem 4.1). The composition f∘gf \circ g satisfies

QE(f∘g)=O(mD+EfQ1/(4D)(g)).(4)Q_E(f \circ g)=O\left(mD+E_fQ_{1/(4D)}(g)\right). \tag*{(4)}

The error threshold depends only on degree, which can be much smaller than the number of outer variables. Standard error reduction gives QE(f∘g)=O(mD+EfQ(g)log⁡(4D))Q_E(f \circ g)=O(mD+E_fQ(g)\log(4D)). The proof interpolates the inner query operations. The return amplitude is a polynomial of degree at most DD, so higher-order contributions cancel in the amplitude used by the algorithm.

Theorem 1.3 (Recursive NAE, Theorem 5.1). Let Fk=NAE⁡3∘kF_k=\operatorname{NAE}_3^{\circ k}, where NAE⁡3\operatorname{NAE}_3 (not all equal on 3 bits) is zero precisely on the two constant strings. For a=3/2a=3/\sqrt{2},

Ω(ak)≤QE(Fk)≤akexp⁡(O((log⁡(k+2))2)).(5)\Omega(a^k)\le Q_E(F_k)\le a^k\exp\left(O\left((\log(k+2))^2\right)\right). \tag*{(5)}

The exact complexity has the same exponential rate as the bounded-error complexity. The upper bound improves the rate 211/8=2.593…2^{11/8}=2.593\ldots of Ambainis’s STOC 2013 algorithm to 3/2=2.121…3/\sqrt{2}=2.121\ldots. The lower bound follows from the known base adversary value and its composition law [3, 4, 19, 25].

Theorem 1.4 (Exact versus randomized queries under recursion, Theorem 6.1). For every fixed nonconstant total gadget hh,

QE(h∘k)=O~h(R(h∘k)2),QE(h∘k)≤R(h∘k)2+oh(1).(6)Q_E(h^{\circ k})=\widetilde{O}_h\left(R(h^{\circ k})^2\right),\qquad Q_E(h^{\circ k})\le R(h^{\circ k})^{2+o_h(1)}. \tag*{(6)}

The tilde hides a polylogarithmic factor with a gadget-dependent exponent. Theorem 6.1 bounds this factor and identifies conditions under which it can be omitted. Its proof uses the following characterization of the exact quantum composition limit.

Theorem 1.5 (Exact quantum composition limit, Theorem 6.2). For every nonconstant total Boolean function hh,

QElim⁡(h):=lim⁡k→∞QE(h∘k)1/k=max⁡{deg⁡(h),Adv⁡±(h)}.(7)Q_E^{\lim}(h):=\lim_{k\to\infty}Q_E(h^{\circ k})^{1/k}=\max\{\deg(h),\operatorname{Adv}^{\pm}(h)\}. \tag*{(7)}

We set QElim⁡(h)=0Q_E^{\lim}(h)=0 for constant hh. We follow the notation Mlim⁡M^{\lim} of Gilmer, Saks, and Srinivasan for composition limits. Al-Dhalaan and Ben-David use M∗M^* for the same operation [2, 16]. Degree and the adversary bound compose exactly and lower bound QEQ_E up to constants. Our algorithm attains the larger of their exponential rates. Its quantitative bounds, together with deg⁡(F)≤9R(F)2\deg(F)\le9R(F)^2 and Adv⁡±(F)=O(R(F))\operatorname{Adv}^{\pm}(F)=O(R(F)), yield (6) [17, 19, 21, 24].

Theorem 1.6 (Transfer principles, Theorems 7.1 and 7.3 and Corollary 7.4). Fix α>0\alpha>0. Let LL be a nonnegative measure on total Boolean functions that vanishes on constants and satisfies L(f∘k)≥L(f)kL(f^{\circ k})\ge L(f)^k for every ff and k≥1k\ge1. Then

[L(F)=O(QE(F)α) for all F]⟺[L(f)≤QElim⁡(f)α for all f].(8)\left[L(F)=O(Q_E(F)^\alpha)\text{ for all }F\right]\Longleftrightarrow\left[L(f)\le Q_E^{\lim}(f)^\alpha\text{ for all }f\right]. \tag*{(8)}

For each B∈{s,bs,fbs}B\in\{s,\mathrm{bs},\mathrm{fbs}\}, the universal bound B(F)=O(QE(F)α)B(F)=O(Q_E(F)^\alpha) is equivalent to fbs(f)≤QElim⁡(f)α\mathrm{fbs}(f)\le Q_E^{\lim}(f)^\alpha for all ff.

Taking kkth roots along recursive powers removes the universal constant and gives a pointwise criterion with coefficient one. In the reverse direction, degree and the adversary bound give QElim⁡(f)≤2QE(f)Q_E^{\lim}(f)\le2Q_E(f). The fractional block-sensitivity criterion uses the normalization and composition results of Tal and Kulkarni–Tal [18, 26].

Theorem 1.7 (Sensitivity separation, Theorem 8.1). Let mk=⌈(9/8)k⌉m_k=\lceil(9/8)^k\rceil, Gk=Fk∘OR⁡mkG_k=F_k\circ\operatorname{OR}_{m_k}, and Nk=3kmkN_k=3^k m_k. Then

s(Gk)=bs⁡(Gk)=fbs⁡(Gk)=Nk,QE(Gk)=Nk2/3+o(1).(9)s(G_k)=\operatorname{bs}(G_k)=\operatorname{fbs}(G_k)=N_k,\qquad Q_E(G_k)=N_k^{2/3+o(1)}. \tag*{(9)}

For each L∈{s,bs⁡,fbs⁡}L\in\{s,\operatorname{bs},\operatorname{fbs}\}, the quantitative separation is

L(Gk)≥QE(Gk)3/2exp⁡(−O((log⁡log⁡(QE(Gk)+3))2)).L(G_k)\ge Q_E(G_k)^{3/2}\exp\left(-O\left((\log\log(Q_E(G_k)+3))^2\right)\right).

The OR layer preserves full sensitivity and balances the degree and adversary costs. The exponent 3/23/2 improves on 8log⁡2(3)/11=1.1527…8\log_2(3)/11=1.1527\ldots, obtained from Ambainis’s algorithm for recursive NAE [3, 4].

References

  1. [1]S. Aaronson, S. Ben-David, and R. Kothari. Separations in query complexity using cheat sheets. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 863–876. ACM, 2016. doi: 10.1145/2897518.2897644. URL https://arxiv.org/abs/1511.01937v2. Theorem numbering follows the full version, arXiv:1511.01937v2.
  2. [2]B. Al-Dhalaan and S. Ben-David. Monte carlo to las vegas for recursively composed functions. arXiv:2601.08073, 2026. URL https://arxiv.org/abs/2601.08073.
  3. [3]A. Ambainis. Superlinear advantage for exact quantum algorithms. In Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing (STOC), pages 891–900. ACM, 2013. doi: 10.1145/2488608.2488721. URL https://doi.org/10.1145/2488608.2488721.
  4. [4]A. Ambainis. Superlinear advantage for exact quantum algorithms. SIAM Journal on Computing, 45(2): 617–631, 2016. doi: 10.1137/130939043. URL https://arxiv.org/abs/1211.0721v6.
  5. [5]A. Ambainis, K. Balodis, A. Belovs, T. Lee, M. Santha, and J. Smotrov. Separations in query complexity based on pointer functions. Journal of the ACM, 64(5), 2017. doi: 10.1145/3106234. URL https://arxiv.org/abs/1506.04719. Article 32.
  6. [6]A. Anshu, A. Belovs, S. Ben-David, M. Göös, R. Jain, R. Kothari, T. Lee, and M. Santha. Separations in communication complexity using cheat sheets and information complexity. In Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 555–564. IEEE, 2016. doi: 10.1109/FOCS.2016.66. URL https://arxiv.org/abs/1605.01142.
  7. [7]R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf. Quantum lower bounds by polynomials. Journal of the ACM, 48(4):778–797, 2001. doi: 10.1145/502090.502097. URL https://arxiv.org/abs/quant-ph/9802049.
  8. [8]S. Ben-David and R. Kothari. Randomized query complexity of sabotaged and composed functions. Theory of Computing, 14(5):1–27, 2018. doi: 10.4086/toc.2018.v014a005. URL https://theoryofcomputing.org/articles/v014a005/.
  9. [9]G. Brassard, P. Høyer, M. Mosca, and A. Tapp. Quantum amplitude amplification and estimation. In S. J. Lomonaco, Jr. and H. E. Brandt, editors, Quantum Computation and Information, volume 305 of Contemporary Mathematics, pages 53–74. American Mathematical Society, 2002. doi: 10.1090/conm/305/05215. URL https://arxiv.org/abs/quant-ph/0005055.
  10. [10]H. Buhrman and R. de Wolf. Communication complexity lower bounds by polynomials. In Proceedings of the 16th Annual IEEE Conference on Computational Complexity (CCC), pages 120–130. IEEE, 2001. doi: 10.1109/CCC.2001.933879. URL https://arxiv.org/abs/cs/9910010.
  11. [11]H. Buhrman and R. de Wolf. Complexity measures and decision tree complexity: A survey. Theoretical Computer Science, 288(1):21–43, 2002. doi: 10.1016/S0304-3975(01)00144-X. URL https://homepages.cwi.nl/~redwolf/publ/other/tcs.pdf.DOI
  12. [12]H. Buhrman, R. Cleve, and A. Wigderson. Quantum vs. classical communication and computation. In Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing (STOC), pages 63–68. ACM, 1998. doi: 10.1145/276698.276713. URL https://arxiv.org/abs/quant-ph/9802040.
  13. [13]H. Buhrman, R. Cleve, R. de Wolf, and C. Zalka. Bounds for small-error and zero-error quantum algorithms. In Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 358–368. IEEE, 1999. doi: 10.1109/SFFCS.1999.814607. URL https://arxiv.org/abs/cs/9904019.
  14. [14]A. Chattopadhyay, Y. Filmus, S. Koroth, O. Meir, and T. Pitassi. Query-to-communication lifting using low-discrepancy gadgets. SIAM Journal on Computing, 50(1):171–210, 2021. doi: 10.1137/19M1310153. URL https://arxiv.org/abs/1904.13056.
  15. [15]R. de Wolf. A note on quantum algorithms and the minimal degree of ε-error polynomials for symmetric functions. arXiv:0802.1816v2, 2008. URL https://arxiv.org/abs/0802.1816v2.
  16. [16]J. Gilmer, M. Saks, and S. Srinivasan. Composition limits and separating examples for some Boolean function complexity measures. arXiv:1306.0630, 2013. URL https://arxiv.org/abs/1306.0630. Conference version in CCC 2013.
  17. [17]H. Huang. Induced subgraphs of hypercubes and a proof of the sensitivity conjecture. Annals of Mathematics, 190(3):949–955, 2019. doi: 10.4007/annals.2019.190.3.6. URL https://annals.math.princeton.edu/2019/190-3/p06.DOI
  18. [18]R. Kulkarni and A. Tal. On fractional block sensitivity. Chicago Journal of Theoretical Computer Science, 2016(8):1–16, 2016. doi: 10.4086/cjtcs.2016.008. URL https://eccc.weizmann.ac.il/report/2013/168/.DOI
  19. [19]T. Lee, R. Mittal, B. W. Reichardt, R. Špalek, and M. Szegedy. Quantum query complexity of state conversion. In Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 344–353. IEEE, 2011. doi: 10.1109/FOCS.2011.75. URL https://arxiv.org/abs/1011.3020.
  20. [20]G. Midrijānis. Exact quantum query complexity for total Boolean functions. arXiv:quant-ph/0403168, 2004. URL https://arxiv.org/abs/quant-ph/0403168.
  21. [21]N. Nisan. CREW PRAMs and decision trees. SIAM Journal on Computing, 20(6):999–1007, 1991. doi: 10.1137/0220062. URL https://doi.org/10.1137/0220062.
  22. [22]S. Pednekar and S. Podder. A general composition theorem for approximate degree. arXiv:2609.30139v2, 2026. URL https://arxiv.org/abs/2609.30139v2. Version 2, October 23, 2026.
  23. [23]A. A. Razborov. On the distributional complexity of disjointness. Theoretical Computer Science, 106(2):385–390, 1992. doi: 10.1016/0304-3975(92)90260-M. URL https://people.cs.uchicago.edu/~razborov/files/dis.pdf.DOI
  24. [24]B. W. Reichardt. Reflections for quantum query algorithms. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 560–569. SIAM, 2011. URL https://arxiv.org/abs/1005.1604.
  25. [25]B. W. Reichardt and R. Špalek. Span-program-based quantum algorithm for evaluating formulas. Theory of Computing, 8(13):291–319, 2012. doi: 10.4086/toc.2012.v008a013. URL https://theoryofcomputing.org/articles/v008a013/. Conference version in STOC 2008.DOI
  26. [26]A. Tal. Properties and applications of Boolean function composition. In Proceedings of the 4th Innovations in Theoretical Computer Science Conference (ITCS), pages 441–454, 2013. doi: 10.1145/2422436.2422485. URL https://eccc.weizmann.ac.il/report/2012/163/, Claim numbering follows the full version, ECCC TR12-163.DOI

Paper details

vlnc:W_k58u2e2h
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 6

downloads · 1

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

GPT-6 Astra, GPT-6.1 Sol

View statement
Looking for related papers…
Contents