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\} f : { 0 , 1 } n → { 0 , 1 } and g : { 0 , 1 } m → { 0 , 1 } g:\{0,1\}^{m}\to\{0,1\} g : { 0 , 1 } m → { 0 , 1 } , the block composition f ∘ g f\circ g f ∘ g applies g g g to n n n disjoint input blocks and then applies f f f to their outputs. An exact quantum algorithm can evaluate this composition by replacing each query to an input bit of f f f with an exact computation of g g g . 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
Q E ( f ∘ g ) = Θ ( Q E ( f ) Q E ( g ) ) . Q_E(f\circ g)=\Theta(Q_E(f)Q_E(g)). Q E ( f ∘ g ) = Θ ( 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)) Q ( f ∘ g ) = Θ ( Q ( f ) Q ( g )) by the general adversary characterization and its composition theorem [19 , 24 , 26 ] . The standard bounds for exact quantum queries are
Q E ( f ∘ g ) ≤ 2 Q E ( f ) Q E ( g ) , (1) Q_E(f\circ g)\le2Q_E(f)Q_E(g), \tag*{(1)} Q E ( f ∘ g ) ≤ 2 Q E ( f ) Q E ( g ) , (1)
Q E ( f ∘ g ) = Ω ( max { Q E ( f ) , Q E ( 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)} Q E ( f ∘ g ) = Ω ( max { Q E ( f ) , Q E ( g ) , deg ( f ) deg ( g ) , Q ( f ) Q ( g )} ) . (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
Q E ( f ∘ OR m ) = O ( m deg ( f ) + n 2 m ) . Q_E(f\circ\operatorname{OR}_{m})=O\left(m\deg(f)+n^{2}\sqrt{m}\right). Q E ( f ∘ OR m ) = O ( m deg ( f ) + n 2 m ) .
and used it to construct total functions with Q E ( f ∘ g ) = o ( Q E ( f ) Q E ( g ) ) Q_E(f\circ g)=o(Q_E(f)Q_E(g)) Q E ( f ∘ g ) = o ( Q E ( f ) Q E ( g )) .
We ask whether approximate inner computations can reduce Q E ( f ∘ g ) Q_E(f\circ g) Q E ( f ∘ 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} Q ε for quantum query complexity with worst-case error at most ε \varepsilon ε , Q = Q 1 / 3 Q=Q_{1/3} Q = Q 1/3 , and R = R 1 / 3 R=R_{1/3} R = R 1/3 for bounded-error randomized query complexity. In the first two theorems, f f f and g g g are nonconstant total Boolean functions on n n n and m m m bits, respectively. We write D = deg ( f ) D=\deg(f) D = deg ( f ) and E f = Q E ( f ) E_f=Q_E(f) E f = Q E ( f ) .
Theorem 1.1 (Exact evaluation of compositions, Theorem 3.1 ). The composition f ∘ g f\circ g f ∘ g satisfies
Q E ( f ∘ g ) ≤ 6 m D + 12 E f Q 1 / ( 4 n ) ( g ) . (3) Q_E(f\circ g)\le6mD+12E_fQ_{1/(4n)}(g). \tag*{(3)} Q E ( f ∘ g ) ≤ 6 m D + 12 E f Q 1/ ( 4 n ) ( g ) . (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 D D D inner blocks in each branch.
Theorem 1.2 (Degree-dependent error threshold, Theorem 4.1 ). The composition f ∘ g f \circ g f ∘ g satisfies
Q E ( f ∘ g ) = O ( m D + E f Q 1 / ( 4 D ) ( g ) ) . (4) Q_E(f \circ g)=O\left(mD+E_fQ_{1/(4D)}(g)\right). \tag*{(4)} Q E ( f ∘ g ) = O ( m D + E f Q 1/ ( 4 D ) ( g ) ) . (4) The error threshold depends only on degree, which can be much smaller than the number of outer variables. Standard error reduction gives Q E ( f ∘ g ) = O ( m D + E f Q ( g ) log ( 4 D ) ) Q_E(f \circ g)=O(mD+E_fQ(g)\log(4D)) Q E ( f ∘ g ) = O ( m D + E f Q ( g ) log ( 4 D )) . The proof interpolates the inner query operations. The return amplitude is a polynomial of degree at most D D D , so higher-order contributions cancel in the amplitude used by the algorithm.
Theorem 1.3 (Recursive NAE, Theorem 5.1 ). Let F k = NAE 3 ∘ k F_k=\operatorname{NAE}_3^{\circ k} F k = NAE 3 ∘ k , where NAE 3 \operatorname{NAE}_3 NAE 3 (not all equal on 3 bits ) is zero precisely on the two constant strings. For a = 3 / 2 a=3/\sqrt{2} a = 3/ 2 ,
Ω ( a k ) ≤ Q E ( F k ) ≤ a k exp ( 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)} Ω ( a k ) ≤ Q E ( F k ) ≤ a k exp ( O ( ( log ( k + 2 ) ) 2 ) ) . (5) The exact complexity has the same exponential rate as the bounded-error complexity. The upper bound improves the rate 2 11 / 8 = 2.593 … 2^{11/8}=2.593\ldots 2 11/8 = 2.593 … of Ambainis’s STOC 2013 algorithm to 3 / 2 = 2.121 … 3/\sqrt{2}=2.121\ldots 3/ 2 = 2.121 … . 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 h h h ,
Q E ( h ∘ k ) = O ~ h ( R ( h ∘ k ) 2 ) , Q E ( h ∘ k ) ≤ R ( h ∘ k ) 2 + o h ( 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)} Q E ( h ∘ k ) = O h ( R ( h ∘ k ) 2 ) , Q E ( h ∘ k ) ≤ R ( h ∘ k ) 2 + o h ( 1 ) . (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 h h h ,
Q E lim ( h ) : = lim k → ∞ Q E ( 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)} Q E l i m ( h ) := k → ∞ lim Q E ( h ∘ k ) 1/ k = max { deg ( h ) , Adv ± ( h )} . (7) We set Q E lim ( h ) = 0 Q_E^{\lim}(h)=0 Q E l i m ( h ) = 0 for constant h h h . We follow the notation M lim M^{\lim} M l i m of Gilmer, Saks, and Srinivasan for composition limits. Al-Dhalaan and Ben-David use M ∗ M^* M ∗ for the same operation [2 , 16 ] . Degree and the adversary bound compose exactly and lower bound Q E Q_E Q E up to constants. Our algorithm attains the larger of their exponential rates. Its quantitative bounds, together with deg ( F ) ≤ 9 R ( F ) 2 \deg(F)\le9R(F)^2 deg ( F ) ≤ 9 R ( F ) 2 and Adv ± ( F ) = O ( R ( F ) ) \operatorname{Adv}^{\pm}(F)=O(R(F)) Adv ± ( 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 α > 0 . Let L L L be a nonnegative measure on total Boolean functions that vanishes on constants and satisfies L ( f ∘ k ) ≥ L ( f ) k L(f^{\circ k})\ge L(f)^k L ( f ∘ k ) ≥ L ( f ) k for every f f f and k ≥ 1 k\ge1 k ≥ 1 . Then
[ L ( F ) = O ( Q E ( F ) α ) for all F ] ⟺ [ L ( f ) ≤ Q E lim ( 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)} [ L ( F ) = O ( Q E ( F ) α ) for all F ] ⟺ [ L ( f ) ≤ Q E l i m ( f ) α for all f ] . (8) For each B ∈ { s , b s , f b s } B\in\{s,\mathrm{bs},\mathrm{fbs}\} B ∈ { s , bs , fbs } , the universal bound B ( F ) = O ( Q E ( F ) α ) B(F)=O(Q_E(F)^\alpha) B ( F ) = O ( Q E ( F ) α ) is equivalent to f b s ( f ) ≤ Q E lim ( f ) α \mathrm{fbs}(f)\le Q_E^{\lim}(f)^\alpha fbs ( f ) ≤ Q E l i m ( f ) α for all f f f .
Taking k k k th 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 Q E lim ( f ) ≤ 2 Q E ( f ) Q_E^{\lim}(f)\le2Q_E(f) Q E l i m ( f ) ≤ 2 Q 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 m k = ⌈ ( 9 / 8 ) k ⌉ m_k=\lceil(9/8)^k\rceil m k = ⌈( 9/8 ) k ⌉ , G k = F k ∘ OR m k G_k=F_k\circ\operatorname{OR}_{m_k} G k = F k ∘ OR m k , and N k = 3 k m k N_k=3^k m_k N k = 3 k m k . Then
s ( G k ) = bs ( G k ) = fbs ( G k ) = N k , Q E ( G k ) = N k 2 / 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)} s ( G k ) = bs ( G k ) = fbs ( G k ) = N k , Q E ( G k ) = N k 2/3 + o ( 1 ) . (9) For each L ∈ { s , bs , fbs } L\in\{s,\operatorname{bs},\operatorname{fbs}\} L ∈ { s , bs , fbs } , the quantitative separation is
L ( G k ) ≥ Q E ( G k ) 3 / 2 exp ( − O ( ( log log ( Q E ( G k ) + 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). L ( G k ) ≥ Q E ( G k ) 3/2 exp ( − O ( ( log log ( Q E ( G k ) + 3 ) ) 2 ) ) . The OR layer preserves full sensitivity and balances the degree and adversary costs. The exponent 3 / 2 3/2 3/2 improves on 8 log 2 ( 3 ) / 11 = 1.1527 … 8\log_2(3)/11=1.1527\ldots 8 log 2 ( 3 ) /11 = 1.1527 … , obtained from Ambainis’s algorithm for recursive NAE [3 , 4 ] .
Theorem 1.8 (Randomized versus exact quantum queries, Theorem 9.3 ). There is a family of total Boolean functions W n W_n W n for which q n = Q E ( W n ) q_n=Q_E(W_n) q n = Q E ( W n ) grows unboundedly and
R ( W n ) ≥ q n 2 exp ( − O ( log ( q n + 2 ) log log ( q n + 3 ) ) ) . (10) R(W_n)\ge q_n^2\exp\left(-O\left(\sqrt{\log(q_n+2)\log\log(q_n+3)}\right)\right). \tag*{(10)} R ( W n ) ≥ q n 2 exp ( − O ( log ( q n + 2 ) log log ( q n + 3 ) ) ) . (10) For every 0 < ε < 1 0<\varepsilon<1 0 < ε < 1 , there is a fixed total function h = h ε h=h_\varepsilon h = h ε whose recursive powers have unbounded exact quantum query complexity and satisfy
R ( h ∘ k ) ≥ Q E ( h ∘ k ) 2 − ε R(h^{\circ k})\ge Q_E(h^{\circ k})^{2-\varepsilon} R ( h ∘ k ) ≥ Q E ( h ∘ k ) 2 − ε for all sufficiently large k k k .
This improves the previous exponent 3 / 2 3/2 3/2 from pointer functions. A cheat-sheet construction gives small degree and bounded-error quantum complexity, while sabotage complexity supplies a randomized lower bound with a base that is preserved under recursion [1 , 5 , 8 ] . The composition limit in (7) converts the two small parameters into an exact quantum upper bound along the powers of a fixed h h h . An explicit choice of recursion depth as a function of the base gadget size gives the quantitative bound in (10) .
Theorem 1.9 (Different inner functions, Proposition 10.1). Let g i g_i g i be nonconstant total Boolean functions on disjoint blocks of sizes m i m_i m i , and let f f f be nonconstant and total. If 0 < ε i < 1 / 2 0<\varepsilon_i<1/2 0 < ε i < 1/2 and ∑ i ε i ≤ 1 / 4 \sum_i\varepsilon_i\le1/4 ∑ i ε i ≤ 1/4 , then
Q E ( f ( g 1 , … , g n ) ) ≤ 6 D m ( f ) + 12 Q E ( f ) max i Q ε i ( g i ) . Q_E(f(g_1,\ldots,g_n))\le6D_{\mathrm{m}}(f)+12Q_E(f)\max_i Q_{\varepsilon_i}(g_i). Q E ( f ( g 1 , … , g n )) ≤ 6 D m ( f ) + 12 Q E ( f ) i max Q ε i ( g i ) . Here D m ( f ) D_{\mathrm{m}}(f) D m ( f ) is the maximum sum of block sizes over the support of a monomial of the signed outer polynomial.
The weighted degree records the largest correction cost of a branch. The separate error budgets accommodate inner problems of different difficulty.
Theorem 1.10 (Communication separations, Theorems 11.3 and 11.5 ). Let H h \mathcal{H}_h H h denote the coordinatewise AND lift of h h h . Then R 1 / 3 c c ( H G k ) = Θ ( N k ) R^{\mathrm{cc}}_{1/3}(\mathcal{H}_{G_k})=\Theta(N_k) R 1/3 cc ( H G k ) = Θ ( N k ) and
Ω ( N k 2 / 3 ) ≤ Q E c c ( H G k ) ≤ N k 2 / 3 exp ( O ( ( log log ( N k + 2 ) ) 2 ) ) . \Omega(N_k^{2/3})\le Q_E^{\mathrm{cc}}(\mathcal{H}_{G_k})\le N_k^{2/3}\exp\left(O\left((\log\log(N_k+2))^2\right)\right). Ω ( N k 2/3 ) ≤ Q E cc ( H G k ) ≤ N k 2/3 exp ( O ( ( log log ( N k + 2 ) ) 2 ) ) . There is also a family of total communication functions W n W_n W n for which q n = Q E c c ( W n ) q_n=Q_E^{\mathrm{cc}}(W_n) q n = Q E cc ( W n ) grows unboundedly and
R 1 / 3 c c ( W n ) ≥ q n 2 exp ( − O ( log ( q n + 2 ) log log ( q n + 3 ) ) ) . R^{\mathrm{cc}}_{1/3}(W_n)\ge q_n^2\exp\left(-O\left(\sqrt{\log(q_n+2)\log\log(q_n+3)}\right)\right). R 1/3 cc ( W n ) ≥ q n 2 exp ( − O ( log ( q n + 2 ) log log ( q n + 3 ) ) ) .
For every 0 < ε < 1 0 < \varepsilon< 1 0 < ε < 1 , there are total communication functions F k F_k F k of unbounded exact quantum communication complexity such that, for all sufficiently large k k k ,
R 1 / 3 c c ( F k ) ≥ Q E c c ( F k ) 2 − ε . R^{\mathrm{cc}}_{1/3}(F_k) \ge Q^{\mathrm{cc}}_E(F_k)^{2-\varepsilon}. R 1/3 cc ( F k ) ≥ Q E cc ( F k ) 2 − ε .
The randomized lower bounds hold with public randomness and unrestricted interaction. The exact quantum upper bounds use no prior entanglement.
The AND lift preserves a disjointness restriction, and the log-rank bound gives the matching quantum exponent. The nearly quadratic gap uses the cheat-sheet family, an inner-product lift, and the standard query simulation for exact protocols. It improves the previous communication separation exponent 3 / 2 3/2 3/2 [6 , 10 , 12 , 14 ] .
Proof strategy
The first algorithm starts with the signed multilinear polynomial H H H of the outer function. For a fixed composed input, let z i ∈ { − 1 , 1 } z_i \in\{-1,1\} z i ∈ { − 1 , 1 } be the correct sign of the i i i th inner answer and let b i ∈ [ − 1 , 1 ] b_i \in[-1,1] b i ∈ [ − 1 , 1 ] be the output bias of its approximate algorithm. Multilinearity gives the exact identity
H ( z ) = ∑ S ⊆ [ n ] ( z − b ) S ∂ S H ( b ) . H(z) = \sum_{S \subseteq[n]} (z-b)_S \, \partial_S H(b). H ( z ) = S ⊆ [ n ] ∑ ( z − b ) S ∂ S H ( b ) .
Only sets of size at most D D D contribute. This identity suggests the algorithm, but it does not by itself give a query implementation: the biases b i b_i b i are unknown and the coefficients need not be positive.
We resolve these two issues separately. Each derivative is represented as a bounded correlation under a product distribution generated by the inner algorithms. Conjugating the outer query operations implements this correlation without explicitly estimating any b i b_i b i . The remaining residual factors are implemented by reading the selected blocks. Their small size controls the normalization of a coherent sum over S S S . The sum has the correct output sign and an input-independent magnitude, so exact amplitude amplification [9 ] produces a clean phase.
The degree-dependent error threshold requires a different expansion. We interpolate each approximate inner reflection toward the exact reflection, using a parameter λ \lambda λ . The complete circuit then has return amplitude H ( b + λ ( z − b ) ) H(b+\lambda(z-b)) H ( b + λ ( z − b )) . This scalar polynomial has degree at most D D D , even though the circuit’s operator expansion may have nonzero terms of higher order. We implement its coefficients through order D D D and bound their total normalization. A constant number of repetitions of the inner algorithm gives the accuracy needed for this bound.
For recursion, the composition theorem is applied to an exact outer tree and an approximate inner tree of unequal depths. Their depths are chosen to balance the degree cost against the adversary cost. The three possible relations between these parameters lead to the quantitative bounds in Section 6. The transfer principles and separation results then follow by comparing exponential rates.
Relation to previous work
Our proofs use the polynomial method [7 ] , the general adversary characterization [19 , 24 ] , and exact amplitude amplification [9 ] as established tools. The composition algorithm develops the approximate-evaluation and exact-correction approach beyond the OR inner function treated by Pednekar and Podder [22 ] . The transfer arguments use the composition framework of Tal [26 ] and the fractional block-sensitivity results of Kulkarni and Tal [18 ] . For the randomized separation, the cheat-sheet construction [1 ] and sabotage lower bounds [8 ] are inputs to our recursive exact algorithm. Similarly, the communication applications use existing simulation, rank, and lifting theorems [10 , 12 , 14 ] . These literature results are stated with citations at the points where they are used; the proofs focus on the new algorithms and their consequences.
Organization. Section 2 reviews the query model and the relevant complexity measures. Section 3 gives the composition algorithm, and Section 4 improves its error threshold to depend on degree. Section 5 applies the algorithm to recursive NAE. Section 6 analyzes recursive powers of a fixed function and compares exact and randomized queries. Section 7 derives the transfer principles. Sections 8 and 9 give the sensitivity and randomized query separations, respectively. Section 10 handles different inner functions, Section 11 gives the communication applications, and Section 12 discusses open problems.
Preliminaries
All functions are total and Boolean unless stated otherwise. We write [ n ] = { 1 , … , n } [n] = \{1, \ldots, n\} [ n ] = { 1 , … , n } and use x ( 1 ) , … , x ( n ) x^{(1)}, \ldots, x^{(n)} x ( 1 ) , … , x ( n ) for disjoint input blocks. For nonconstant functions f : { 0 , 1 } n → { 0 , 1 } f : \{0,1\}^{n} \to\{0,1\} f : { 0 , 1 } n → { 0 , 1 } and g : { 0 , 1 } m → { 0 , 1 } g : \{0,1\}^{m} \to\{0,1\} g : { 0 , 1 } m → { 0 , 1 } , their block composition is
( f ∘ g ) ( x ( 1 ) , … , x ( n ) ) = f ( g ( x ( 1 ) ) , … , g ( x ( n ) ) ) . (f \circ g)(x^{(1)}, \ldots, x^{(n)}) = f(g(x^{(1)}), \ldots, g(x^{(n)})). ( f ∘ g ) ( x ( 1 ) , … , x ( n ) ) = f ( g ( x ( 1 ) ) , … , g ( x ( n ) )) .
When a composition has constant blocks, we first substitute their values into the outer function. Logarithms are natural unless a base is displayed. Constants are absolute except in statements about a fixed recursive gadget, where they may depend on the gadget. The notation O ~ \widetilde{O} O and Ω ~ \widetilde{\Omega} Ω suppresses polylogarithmic factors in the stated parameter; a subscript h h h permits the constants and logarithmic exponents to depend on a fixed h h h .
Query complexity and coherent algorithms
We use the standard quantum query model [4 , 7 ] . For an input x ∈ { 0 , 1 } N x \in\{0,1\}^{N} x ∈ { 0 , 1 } N , a phase query acts as
O x ∣ j , w ⟩ = ( − 1 ) x j ∣ j , w ⟩ ( j ∈ [ N ] ) , O x ∣ 0 , w ⟩ = ∣ 0 , w ⟩ . O_x|j,w\rangle= (-1)^{x_j}|j,w\rangle\quad(j \in[N]), \qquad O_x|0,w\rangle= |0,w\rangle. O x ∣ j , w ⟩ = ( − 1 ) x j ∣ j , w ⟩ ( j ∈ [ N ]) , O x ∣0 , w ⟩ = ∣0 , w ⟩ .
The dummy coordinate 0 permits controlled queries and padding at unit query cost. Algorithms may use arbitrary input-independent unitaries and auxiliary registers. Only calls to O x O_x O x are charged. We defer all measurements until the end.
We write Q ε ( f ) Q_{\varepsilon}(f) Q ε ( f ) for the minimum worst-case number of queries of a quantum algorithm whose error is at most ε \varepsilon ε on every input, and put Q ( f ) = Q 1 / 3 ( f ) Q(f) = Q_{1/3}(f) Q ( f ) = Q 1/3 ( f ) and Q E ( f ) = Q 0 ( f ) Q_E(f) = Q_0(f) Q E ( f ) = Q 0 ( f ) . We use D ( f ) D(f) D ( f ) for deterministic query complexity and R ( f ) = R 1 / 3 ( f ) R(f) = R_{1/3}(f) R ( f ) = R 1/3 ( f ) for randomized query complexity, with the number of queries maximized over inputs and random choices. Standard coherent error reduction gives [11 ]
Q ε ( f ) = O ( Q ( f ) log ( 1 / ε ) ) ( 0 < ε ≤ 1 / 3 ) . (11) Q_{\varepsilon}(f) = O(Q(f)\log(1/\varepsilon)) \qquad(0 < \varepsilon\le1/3). \tag*{(11)} Q ε ( f ) = O ( Q ( f ) log ( 1/ ε )) ( 0 < ε ≤ 1/3 ) . (11)
Our constructions require the outer algorithm to return its workspace to the initial state. The standard compute–phase–uncompute construction achieves this at a factor-two query cost. Specifically, if A x A_x A x is an exact T T T -query algorithm for f f f and Z Z Z acts on its output qubit, then
A x † Z A x ∣ 0 ⟩ = ( − 1 ) f ( x ) ∣ 0 ⟩ . (12) A_x^\dagger Z A_x|0\rangle= (-1)^{f(x)}|0\rangle. \tag*{(12)} A x † Z A x ∣0 ⟩ = ( − 1 ) f ( x ) ∣0 ⟩ . (12)
This is a clean phase algorithm of cost 2 T 2T 2 T . Conversely, a controlled clean phase computes the corresponding Boolean value exactly with the same query cost. We retain this factor of two throughout.
Encoding scalars as return amplitudes
The exact correction is assembled from circuits that encode real numbers in a single amplitude. These amplitudes are used coherently; the algorithm never estimates them. The return amplitude of a unitary U x U_x U x is ⟨ 0 ∣ U x ∣ 0 ⟩ \langle0|U_x|0\rangle ⟨ 0∣ U x ∣0 ⟩ , where ∣ 0 ⟩ |0\rangle ∣0 ⟩ includes every initial register. If a t t t -query algorithm A x A_x A x has signed output bias b ( x ) = E [ ( − 1 ) A ( x ) ] b(x)=\mathbb{E}[(-1)^{A(x)}] b ( x ) = E [( − 1 ) A ( x ) ] , then
⟨ 0 ∣ A x † Z A x ∣ 0 ⟩ = b ( x ) . (13) \langle0|A_x^\dagger Z A_x|0\rangle=b(x). \tag*{(13)} ⟨ 0∣ A x † Z A x ∣0 ⟩ = b ( x ) . (13)
Running two circuits on disjoint work registers multiplies their return amplitudes. To form a weighted sum, we use a selector register whose amplitudes depend only on prescribed weights. For w j ≥ 0 w_j \ge0 w j ≥ 0 , L = ∑ j w j > 0 L=\sum_j w_j>0 L = ∑ j w j > 0 , and a selector V ∣ 0 ⟩ = ∑ j w j / L ∣ j ⟩ V|0\rangle=\sum_j\sqrt{w_j/L}|j\rangle V ∣0 ⟩ = ∑ j w j / L ∣ j ⟩ ,
⟨ 0 , 0 ∣ ( V † ⊗ I ) ( ∑ j ∣ j ⟩ ⟨ j ∣ ⊗ U j , x ) ( V ⊗ I ) ∣ 0 , 0 ⟩ = 1 L ∑ j w j ⟨ 0 ∣ U j , x ∣ 0 ⟩ . (14) \langle0,0|(V^\dagger\otimes I)\left(\sum_j |j\rangle\langle j|\otimes U_{j,x}\right)(V\otimes I)|0,0\rangle=\frac{1}{L}\sum_j w_j\langle0|U_{j,x}|0\rangle. \tag*{(14)} ⟨ 0 , 0∣ ( V † ⊗ I ) ( j ∑ ∣ j ⟩ ⟨ j ∣ ⊗ U j , x ) ( V ⊗ I ) ∣0 , 0 ⟩ = L 1 j ∑ w j ⟨ 0∣ U j , x ∣0 ⟩ . (14)
The weights in this identity must be independent of the input. The branch circuits may still depend on the input through their oracle calls. Padding all branches to a common query schedule makes the total cost the maximum branch cost.
The last step of both composition algorithms is exact amplitude amplification [9 ] . We use its standard three-call specialization: a unitary with return amplitude in { − 1 / 2 , 1 / 2 } \{-1/2,1/2\} { − 1/2 , 1/2 } can be converted to the corresponding clean phase. The input-independent magnitude is what makes this final amplification exact.
Degree and the general adversary bound
The exact degree deg ( f ) \deg(f) deg ( f ) is the degree of the unique real multilinear polynomial representing f f f on the Boolean cube. The polynomial method [7 ] gives
Q E ( f ) ≥ 1 2 deg ( f ) . (15) Q_E(f)\ge\frac{1}{2}\deg(f). \tag*{(15)} Q E ( f ) ≥ 2 1 deg ( f ) . (15)
For an outer function f f f we use its signed representation
H ( y ) = ( − 1 ) f ( ( 1 − y ) / 2 ) = ∑ T ⊆ [ n ] H ^ ( T ) y T , y T = ∏ i ∈ T y i . H(y)=(-1)^{f((1-y)/2)}=\sum_{T\subseteq[n]}\widehat{H}(T)y_T,\qquad y_T=\prod_{i\in T}y_i. H ( y ) = ( − 1 ) f (( 1 − y ) /2 ) = T ⊆ [ n ] ∑ H ( T ) y T , y T = i ∈ T ∏ y i .
The same symbol denotes its multilinear extension to R n \mathbb{R}^n R n . We write ∂ S = ∏ i ∈ S ∂ / ∂ y i \partial_S=\prod_{i\in S}\partial/\partial y_i ∂ S = ∏ i ∈ S ∂ / ∂ y i and, in composition statements, abbreviate
D = deg ( f ) , E f = Q E ( f ) , E g = Q E ( g ) . D=\deg(f),\qquad E_f=Q_E(f),\qquad E_g=Q_E(g). D = deg ( f ) , E f = Q E ( f ) , E g = Q E ( g ) .
Thus D D D without an argument denotes polynomial degree, whereas D ( f ) D(f) D ( f ) denotes deterministic query complexity.
We use the following exact composition law for degree.
Lemma 2.1 (Tal [26 Lemma 3.1(1)] ). For nonconstant total Boolean functions f f f and g g g , deg ( f ∘ g ) = deg ( f ) deg ( g ) \deg(f\circ g)=\deg(f)\deg(g) deg ( f ∘ g ) = deg ( f ) deg ( g ) .
Midrijanis’s deterministic algorithm [20 ] gives
Q E ( f ) ≤ D ( f ) ≤ 2 deg ( f ) 3 . (16) Q_E(f) \le D(f) \le2\deg(f)^3. \tag*{(16)} Q E ( f ) ≤ D ( f ) ≤ 2 deg ( f ) 3 . (16)
A certificate at an input is a set of coordinates whose values force the output. We write C ( f ) C(f) C ( f ) for the maximum, over inputs, of the minimum certificate size; in particular C ( f ) ≤ D ( f ) C(f) \le D(f) C ( f ) ≤ D ( f ) .
The second lower-bound measure that governs our recursive algorithms is the general adversary bound:
Adv ± ( f ) = max Γ ≠ 0 ∥ Γ ∥ max j ∥ Γ ∘ Δ j ∥ . (17) \operatorname{Adv}^{\pm}(f) = \max_{\Gamma\ne0} \frac{\lVert\Gamma\rVert}{\max_j \lVert\Gamma\circ\Delta_j\rVert}. \tag*{(17)} Adv ± ( f ) = Γ = 0 max max j ∥ Γ ∘ Δ j ∥ ∥ Γ ∥ . (17)
Here Γ \Gamma Γ is real symmetric, indexed by inputs, and satisfies Γ x y = 0 \Gamma_{xy} = 0 Γ x y = 0 when f ( x ) = f ( y ) f(x) = f(y) f ( x ) = f ( y ) ; the matrix Δ j \Delta_j Δ j indicates x j ≠ y j x_j \ne y_j x j = y j . The symbol ∘ \circ ∘ denotes entrywise product, and the norm is the operator norm.
We use the standard characterization and composition theorems [19 , 24 ] :
Q ( f ) = Θ ( Adv ± ( f ) ) , Adv ± ( f ∘ g ) = Adv ± ( f ) Adv ± ( g ) . (18) Q(f) = \Theta(\operatorname{Adv}^{\pm}(f)), \qquad\operatorname{Adv}^{\pm}(f \circ g) = \operatorname{Adv}^{\pm}(f)\operatorname{Adv}^{\pm}(g). \tag*{(18)} Q ( f ) = Θ ( Adv ± ( f )) , Adv ± ( f ∘ g ) = Adv ± ( f ) Adv ± ( g ) . (18)
Their constants are universal. We also use the standard bounds Adv ± ( f ) ≤ N \operatorname{Adv}^{\pm}(f) \le N Adv ± ( f ) ≤ N for N N N -bit functions and Adv ± ( f ) ≤ 2 Q E ( f ) \operatorname{Adv}^{\pm}(f) \le2Q_E(f) Adv ± ( f ) ≤ 2 Q E ( f ) . Consequently, for each fixed h h h , Q ( h ∘ k ) = Θ ( Adv ± ( h ) k ) Q(h^{\circ k}) = \Theta(\operatorname{Adv}^{\pm}(h)^k) Q ( h ∘ k ) = Θ ( Adv ± ( h ) k ) with constants independent of k k k .
The polynomial and adversary methods thus provide complementary lower bounds. Their exact composition laws will identify the candidate exponential rate for a recursive function; the main algorithm will give the matching upper rate.
An exact quantum algorithm for composed functions
An approximate computation of an inner block can save queries, but an exact outer algorithm cannot simply tolerate the resulting error. The construction in this section corrects that error coherently. Its cost has two contributions: simulating the outer queries with approximate inner algorithms, and reading a small number of inner blocks to implement the correction.
Throughout this section, f : { 0 , 1 } n → { 0 , 1 } f : \{0,1\}^n \to\{0,1\} f : { 0 , 1 } n → { 0 , 1 } and g : { 0 , 1 } m → { 0 , 1 } g : \{0,1\}^m \to\{0,1\} g : { 0 , 1 } m → { 0 , 1 } are nonconstant total Boolean functions. Write
D = deg ( f ) , E f = Q E ( f ) , ε = 1 4 n , t = Q ε ( g ) . D = \deg(f), \qquad E_f = Q_E(f), \qquad\varepsilon= \frac{1}{4n}, \qquad t = Q_\varepsilon(g). D = deg ( f ) , E f = Q E ( f ) , ε = 4 n 1 , t = Q ε ( g ) .
Theorem 3.1 (Exact evaluation of composed functions). For all such f f f and g g g ,
Q E ( f ∘ g ) ≤ 6 m D + 12 E f t . (19) Q_E(f \circ g) \le6mD + 12E_f t. \tag*{(19)} Q E ( f ∘ g ) ≤ 6 m D + 12 E f t . (19) Moreover, there is a clean phase algorithm for f ∘ g f \circ g f ∘ g with this query cost. The same construction applies to any specified t A t_A t A -query algorithm for g g g with error at most $1/(4n)$, with t A t_A t A in place of $t.
The algorithm
Let z i z_i z i be the correct sign of the i i i th inner output, and let b i b_i b i be the output bias of an approximate inner algorithm. The desired answer is H ( z ) H(z) H ( z ) , where H H H is the signed polynomial of f f f . Multilinearity gives an exact expansion of H ( z ) H(z) H ( z ) about b b b . Each term is indexed by a set S S S of at most D D D inner blocks and consists of two factors: a derivative ∂ S H ( b ) \partial_S H(b) ∂ S H ( b ) , and a product of residuals z i − b i z_i - b_i z i − b i over i ∈ S i \in S i ∈ S .
We implement these two factors on separate work registers. The derivative is a correlation of the Boolean function H H H with a parity, so its absolute value is at most one. More importantly, it can be implemented by replacing each query of a clean outer circuit with a suitable inner operation; this costs 4 E f t 4E_ft 4 E f t queries, independently of ∣ S ∣ |S| ∣ S ∣ and n n n . The residuals are small, and reading the blocks in S S S lets us implement their normalized product with 2 m ∣ S ∣ 2m|S| 2 m ∣ S ∣ additional queries.
The algorithm then combines all sets S S S in a coherent superposition. The weights depend only on ∣ S ∣ |S| ∣ S ∣ and ε \varepsilon ε , and their sum is less than two. Padding this sum to exactly two produces a circuit whose return amplitude is H ( z ) / 2 H(z)/2 H ( z ) /2 . Thus its success probability is the known constant 1 / 4 1/4 1/4 , while its amplitude retains the sign of the answer. A standard exact amplification step converts this amplitude into the clean phase H ( z ) H(z) H ( z ) .
The rest of the proof establishes the expansion, implements one branch, and then combines the branches. All appearances of z i z_i z i and b i b_i b i in the analysis below describe the input and the inner algorithm; the construction does not first compute the vectors z z z or b b b .
An exact expansion with bounded coefficients
Let H H H be the signed multilinear polynomial of f f f :
H ( y ) = ( − 1 ) f ( ( 1 − y ) / 2 ) = ∑ T ⊆ [ n ] H ^ ( T ) y T , y ∈ { − 1 , 1 } n , y T = ∏ i ∈ T y i . H(y)=(-1)^{f((1-y)/2)}=\sum_{T\subseteq[n]}\widehat{H}(T)y_T,\qquad y\in\{-1,1\}^{n},\qquad y_T=\prod_{i\in T}y_i. H ( y ) = ( − 1 ) f (( 1 − y ) /2 ) = T ⊆ [ n ] ∑ H ( T ) y T , y ∈ { − 1 , 1 } n , y T = i ∈ T ∏ y i .
We use the same symbol for its multilinear extension to R n \mathbb{R}^{n} R n . Fix a coherent t t t -query algorithm A A A for g g g with error at most ε \varepsilon ε . For an input x = ( x ( 1 ) , … , x ( n ) ) x=(x^{(1)},\ldots,x^{(n)}) x = ( x ( 1 ) , … , x ( n ) ) to the composed function, put
z i = ( − 1 ) g ( x ( i ) ) , b i = E [ ( − 1 ) A ( x ( i ) ) ] , e i = z i − b i . (20) z_i=(-1)^{g(x^{(i)})},\qquad b_i=\mathbb{E}[(-1)^{A(x^{(i)})}],\qquad e_i=z_i-b_i. \tag*{(20)} z i = ( − 1 ) g ( x ( i ) ) , b i = E [( − 1 ) A ( x ( i ) ) ] , e i = z i − b i . (20)
Here the expectation refers to measuring the output of A A A . If its error probability on block i i i is p i p_i p i , then b i = z i ( 1 − 2 p i ) b_i=z_i(1-2p_i) b i = z i ( 1 − 2 p i ) and e i = 2 z i p i e_i=2z_ip_i e i = 2 z i p i . In particular,
b i ∈ [ − 1 , 1 ] , ∣ e i ∣ ≤ 2 ε . b_i\in[-1,1],\qquad|e_i|\le2\varepsilon. b i ∈ [ − 1 , 1 ] , ∣ e i ∣ ≤ 2 ε .
The small size of e i e_i e i will control the weight of every correction term.
For S ⊆ [ n ] S\subseteq[n] S ⊆ [ n ] , write ∂ S = ∏ i ∈ S ∂ / ∂ y i \partial_S=\prod_{i\in S}\partial/\partial y_i ∂ S = ∏ i ∈ S ∂ / ∂ y i and e S = ∏ i ∈ S e i e_S=\prod_{i\in S}e_i e S = ∏ i ∈ S e i , with ∂ ∅ H = H \partial_{\varnothing}H=H ∂ ∅ H = H and e ∅ = 1 e_{\varnothing}=1 e ∅ = 1 . Expanding each monomial of H ( b + e ) H(b+e) H ( b + e ) yields
H ( z ) = ∑ S ⊆ [ n ] ∣ S ∣ ≤ D e S ∂ S H ( b ) . (21) H(z)=\sum_{\substack{S\subseteq[n]\\ |S|\le D}}e_S\partial_SH(b). \tag*{(21)} H ( z ) = S ⊆ [ n ] ∣ S ∣ ≤ D ∑ e S ∂ S H ( b ) . (21)
There is no remainder: H H H has degree D D D . There are also no factorials, since a variable occurs at most once in each monomial. The following identity expresses every derivative in (21) as a bounded correlation, which is the form needed by the quantum circuit.
Lemma 3.2 (Derivative correlations). For S ⊆ [ n ] S\subseteq[n] S ⊆ [ n ] and b ∈ [ − 1 , 1 ] n b\in[-1,1]^n b ∈ [ − 1 , 1 ] n , let Y 1 , … , Y n Y_1,\ldots,Y_n Y 1 , … , Y n be independent signs such that Y i Y_i Y i is uniform for i ∈ S i\in S i ∈ S and E Y i = b i \mathbb{E}Y_i=b_i E Y i = b i for $i\notin S. Then
∂ S H ( b ) = E [ H ( Y ) ∏ i ∈ S Y i ] . (22) \partial_SH(b)=\mathbb{E}\left[H(Y)\prod_{i\in S}Y_i\right]. \tag*{(22)} ∂ S H ( b ) = E [ H ( Y ) i ∈ S ∏ Y i ] . (22) Consequently, ∣ ∂ S H ( b ) ∣ ≤ 1 |\partial_SH(b)|\le1 ∣ ∂ S H ( b ) ∣ ≤ 1 .
Proof. It suffices to evaluate the correlation on a monomial Y T Y_T Y T . If S ⊈ T S \nsubseteq T S ⊈ T , choose i ∈ S ∖ T i \in S \setminus T i ∈ S ∖ T . The uniform sign Y i Y_i Y i occurs exactly once in Y T Y S Y_TY_S Y T Y S , so independence makes the expectation zero. If S ⊆ T S \subseteq T S ⊆ T , each sign indexed by S S S occurs twice and cancels, leaving expectation ∏ i ∈ T ∖ S b i \prod_{i\in T\setminus S} b_i ∏ i ∈ T ∖ S b i . By linearity,
E [ H ( Y ) Y S ] = ∑ T ⊇ S H ^ ( T ) ∏ i ∈ T ∖ S b i = ∂ S H ( b ) . \mathbb{E}[H(Y)Y_S] = \sum_{T\supseteq S} \widehat{H}(T) \prod_{i\in T\setminus S} b_i = \partial_S H(b). E [ H ( Y ) Y S ] = T ⊇ S ∑ H ( T ) i ∈ T ∖ S ∏ b i = ∂ S H ( b ) .
The integrand H ( Y ) Y S H(Y)Y_S H ( Y ) Y S takes values in { − 1 , 1 } \{-1,1\} { − 1 , 1 } , proving the bound.
Implementing the derivative correlation
The correlation lemma suggests preparing all n n n inner outputs and then running the outer circuit. That preparation would cost n t nt n t queries. The next lemma obtains the same return amplitude by conjugating each outer query separately, so that only the number of queries in the outer algorithm enters the bound.
Lemma 3.3. For every S ⊆ [ n ] S \subseteq[n] S ⊆ [ n ] , there is a unitary G S , x G_{S,x} G S , x with return amplitude ∂ S H ( b ) \partial_S H(b) ∂ S H ( b ) that uses at most 4 E f t 4E_f t 4 E f t queries to x x x . The construction can be controlled coherently by a register containing S S S .
Proof. A circuit with the desired amplitude. Allocate an answer qubit q i q_i q i and an inner workspace w i w_i w i for each block. When i ∉ S i \notin S i ∈ / S , let B i = A i B_i=A_i B i = A i be the algorithm A A A on block x ( i ) x^{(i)} x ( i ) , acting on ( q i , w i ) (q_i,w_i) ( q i , w i ) . When i ∈ S i \in S i ∈ S , let B i B_i B i be a Hadamard gate on q i q_i q i and the identity on w i w_i w i . Define
B S = ⨂ i = 1 n B i , P S = ∏ i ∈ S Z q i . B_S = \bigotimes_{i=1}^{n} B_i,\qquad P_S = \prod_{i\in S} Z_{q_i}. B S = i = 1 ⨂ n B i , P S = i ∈ S ∏ Z q i .
If the answer qubits in B S ∣ 0 ⟩ B_S|0\rangle B S ∣0 ⟩ were measured, the signs Y i = ( − 1 ) q i Y_i=(-1)^{q_i} Y i = ( − 1 ) q i would have exactly the product distribution of Lemma 3.2.
Let C f ( q ) C_f(q) C f ( q ) be an exact E f E_f E f -query algorithm for f f f , with its own workspace. Its clean phase circuit is
W f ( q ) = C f ( q ) † Z o u t C f ( q ) , W_f(q) = C_f(q)^\dagger Z_{\mathrm{out}} C_f(q), W f ( q ) = C f ( q ) † Z out C f ( q ) ,
where Z o u t Z_{\mathrm{out}} Z out acts on the outer answer qubit. This circuit uses 2 E f 2E_f 2 E f queries to the virtual input q q q . For every basis string q q q ,
W f ( q ) ( ∣ q ⟩ ⊗ ∣ 0 ⟩ o u t e r ) = ( − 1 ) f ( q ) ∣ q ⟩ ⊗ ∣ 0 ⟩ o u t e r . W_f(q)(|q\rangle\otimes|0\rangle_{\mathrm{outer}}) = (-1)^{f(q)}|q\rangle\otimes|0\rangle_{\mathrm{outer}}. W f ( q ) ( ∣ q ⟩ ⊗ ∣0 ⟩ outer ) = ( − 1 ) f ( q ) ∣ q ⟩ ⊗ ∣0 ⟩ outer .
Because the outer workspace is restored to zero, the same statement holds coherently when q q q is in superposition or entangled with the inner workspaces. The factor P S P_S P S contributes the additional sign ∏ i ∈ S ( − 1 ) q i \prod_{i\in S}(-1)^{q_i} ∏ i ∈ S ( − 1 ) q i . Consequently,
⟨ 0 ∣ B S † P S W f ( q ) B S ∣ 0 ⟩ = E [ H ( Y ) Y S ] = ∂ S H ( b ) . (23) \langle0|B_S^\dagger P_S W_f(q) B_S|0\rangle= \mathbb{E}[H(Y)Y_S] = \partial_S H(b). \tag*{(23)} ⟨ 0∣ B S † P S W f ( q ) B S ∣0 ⟩ = E [ H ( Y ) Y S ] = ∂ S H ( b ) . (23)
The state ∣ 0 ⟩ |0\rangle ∣0 ⟩ in this expression includes both inner and outer workspaces.
Implementing the circuit query by query. Equation (23) is used to identify the amplitude; we do not implement it by preparing B S ∣ 0 ⟩ B_S|0\rangle B S ∣0 ⟩ . Instead, factor P S W f P_SW_f P S W f into its individual gates and insert B S B S † B_SB_S^\dagger B S B S † between consecutive factors. This expresses its conjugate as a product of conjugated gates. Every input-independent outer gate commutes with B S B_S B S and is therefore unchanged.
It remains to implement the conjugate of a virtual query. If J J J is the outer query-index register, that query is
O q = ∣ 0 ⟩ ⟨ 0 ∣ J ⊗ I + ∑ i = 1 n ∣ i ⟩ ⟨ i ∣ J ⊗ Z q i . O_q = |0\rangle\langle0|_J \otimes I + \sum_{i=1}^{n} |i\rangle\langle i|_J \otimes Z_{q_i}. O q = ∣0 ⟩ ⟨ 0 ∣ J ⊗ I + i = 1 ∑ n ∣ i ⟩ ⟨ i ∣ J ⊗ Z q i .
Since B S B_S B S is a tensor product over the blocks, its conjugate is
B S † O Q B S = ∣ 0 ⟩ ⟨ 0 ∣ J ⊗ I + ∑ i = 1 n ∣ i ⟩ ⟨ i ∣ J ⊗ B i † Z q i B i . (24) B_S^\dagger O_Q B_S = \lvert0\rangle\langle0\rvert_J \otimes I + \sum_{i=1}^{n} \lvert i\rangle\langle i\rvert_J \otimes B_i^\dagger Z_{q_i} B_i. \tag*{(24)} B S † O Q B S = ∣ 0 ⟩ ⟨ 0 ∣ J ⊗ I + i = 1 ∑ n ∣ i ⟩ ⟨ i ∣ J ⊗ B i † Z q i B i . (24)
Thus only the workspace selected by J J J is affected. If i ∉ S i \notin S i ∈ / S , the selected operation is A i † Z q i A i A_i^\dagger Z_{q_i} A_i A i † Z q i A i , which uses 2 t 2t 2 t queries. If i ∈ S i \in S i ∈ S , it is H Z H = X q i HZH = X_{q_i} H Z H = X q i , which is query-free. These alternatives can be implemented coherently in one 2 t 2t 2 t -query schedule: the raw input query is addressed to the selected block, and inactive branches query the dummy coordinate. The remaining factor also has a query-free conjugate,
B S † P S B S = ∏ i ∈ S X q i . B_S^\dagger P_S B_S = \prod_{i\in S} X_{q_i}. B S † P S B S = i ∈ S ∏ X q i .
Replacing all 2 E f 2E_f 2 E f virtual queries therefore costs at most 4 E f t 4E_f t 4 E f t queries to x x x .
The work registers persist between virtual queries. Their states need not be zero when a later selected operation is applied: the identities above hold as operator identities on the entire Hilbert space. This is why the query-by-query implementation agrees exactly with the circuit in (23) , despite never preparing all inner outputs at once. Finally, the choice between the two operations in (24) , as well as all free gates, can be controlled on a register storing S S S . This proves the coherent version of the lemma.
Implementing the normalized residuals
The derivative circuit supplies the first factor in each Taylor term. For the second factor, it is enough to realize e i / ( 2 ε ) e_i/(2\varepsilon) e i / ( 2 ε ) as a return amplitude. Reading block i i i makes this possible with no further calls to the approximate algorithm.
Lemma 3.4. For a selected inner block u ∈ { 0 , 1 } m u \in\{0,1\}^{m} u ∈ { 0 , 1 } m , there is a 2 m 2m 2 m -query unitary with return amplitude
( − 1 ) g ( u ) − E [ ( − 1 ) A ( u ) ] 2 ε . \frac{(-1)^{g(u)}-\mathbb{E}[(-1)^{A(u)}]}{2\varepsilon}. 2 ε ( − 1 ) g ( u ) − E [( − 1 ) A ( u ) ] .
Proof. Read all m m m bits of u u u into a register using m m m queries. For each possible value of that register, define
r ( u ) = ( − 1 ) g ( u ) − E [ ( − 1 ) A ( u ) ] 2 ε . r(u)=\frac{(-1)^{g(u)}-\mathbb{E}[(-1)^{A(u)}]}{2\varepsilon}. r ( u ) = 2 ε ( − 1 ) g ( u ) − E [( − 1 ) A ( u ) ] .
The error guarantee for A A A implies r ( u ) ∈ [ − 1 , 1 ] r(u)\in[-1,1] r ( u ) ∈ [ − 1 , 1 ] . Apply to a fresh qubit the real rotation
R u = ( r ( u ) − 1 − r ( u ) 2 1 − r ( u ) 2 r ( u ) ) , R_u=
\begin{pmatrix}
r(u) & -\sqrt{1-r(u)^2}\\
\sqrt{1-r(u)^2} & r(u)
\end{pmatrix}, R u = ( r ( u ) 1 − r ( u ) 2 − 1 − r ( u ) 2 r ( u ) ) ,
controlled by the register holding u u u , and then uncompute that register with another m m m queries. The return amplitude on the fresh qubit is r ( u ) r(u) r ( u ) , and the block register has returned to zero.
This controlled rotation is an allowed input-independent operation: g g g and A A A are fixed, so the numbers r ( u ) r(u) r ( u ) form a fixed finite table. The algorithm does not estimate an error probability at run time. The table may be expensive to describe or implement in a gate model, but such input-independent computation is free in the query model used here.
Now fix a set S S S with ∣ S ∣ ≤ D \lvert S\rvert\le D ∣ S ∣ ≤ D . Apply the residual construction to each block in S S S , with a fresh work register for each application, and apply the derivative circuit on a separate register. For a fixed input x x x , return amplitudes on these registers multiply. The resulting branch unitary V S , x V_{S,x} V S , x therefore has return amplitude
a S ( x ) = ∂ S H ( b ) ∏ i ∈ S e i 2 ε (25) a_S(x)=\partial_S H(b)\prod_{i\in S}\frac{e_i}{2\varepsilon} \tag*{(25)} a S ( x ) = ∂ S H ( b ) i ∈ S ∏ 2 ε e i (25)
and query cost at most
B = 2 m D + 4 E f t . (26) B=2mD+4E_f t. \tag*{(26)} B = 2 m D + 4 E f t . (26)
All branches use the same schedule: D D D residual slots, followed by the derivative circuit. Unused residual slots make dummy queries. Thus selecting the branches coherently costs the maximum branch budget B B B , rather than the sum of their budgets.
Combining the branches and obtaining an exact answer
Proof of Theorem 3.1. Coherent summation. To recover the Taylor expansion from (25) , give branch S S S the weight w S = ( 2 ε ) ∣ S ∣ w_S=(2\varepsilon)^{|S|} w S = ( 2 ε ) ∣ S ∣ . These weights are input-independent and nonnegative. Their total satisfies
L = ∑ j = 0 D ( n j ) ( 2 ε ) j ≤ ( 1 + 2 ε ) n ≤ exp ( 2 n ε ) = e 1 / 2 < 2. (27) L=\sum_{j=0}^{D}\binom{n}{j}(2\varepsilon)^j\leq(1+2\varepsilon)^n\leq\exp(2n\varepsilon)=e^{1/2}<2. \tag*{(27)} L = j = 0 ∑ D ( j n ) ( 2 ε ) j ≤ ( 1 + 2 ε ) n ≤ exp ( 2 n ε ) = e 1/2 < 2. (27)
Add a branch indexed by ⊥ \perp ⊥ , of weight 2 − L 2-L 2 − L , whose unitary has zero return amplitude; a Pauli X X X on a fresh qubit suffices. Prepare the selector by an input-independent unitary P P P satisfying
P ∣ 0 ⟩ = ∑ S ⊆ [ n ] ∣ S ∣ ≤ D w S 2 ∣ S ⟩ + 2 − L 2 ∣ ⊥ ⟩ . P|0\rangle=\sum_{\substack{S\subseteq[n]\\ |S|\leq D}}\sqrt{\frac{w_S}{2}}|S\rangle+\sqrt{\frac{2-L}{2}}|\perp\rangle. P ∣0 ⟩ = S ⊆ [ n ] ∣ S ∣ ≤ D ∑ 2 w S ∣ S ⟩ + 2 2 − L ∣ ⊥ ⟩ .
Apply the selected branch unitary and then P † P^\dagger P † . By coherent selection, the resulting unitary U x U_x U x has return amplitude
α x : = ⟨ 0 ∣ U x ∣ 0 ⟩ = 1 2 ∑ ∣ S ∣ ≤ D w S a S ( x ) = 1 2 ∑ ∣ S ∣ ≤ D e S ∂ S H ( b ) = H ( z ) 2 ∈ { − 1 / 2 , 1 / 2 } . (28) \begin{aligned}
\alpha_x&:=\langle0|U_x|0\rangle=\frac{1}{2}\sum_{|S|\leq D}w_Sa_S(x)\\
&=\frac{1}{2}\sum_{|S|\leq D}e_S\partial_SH(b)=\frac{H(z)}{2}\in\{-1/2,1/2\}. \tag*{(28)}
\end{aligned} α x := ⟨ 0∣ U x ∣0 ⟩ = 2 1 ∣ S ∣ ≤ D ∑ w S a S ( x ) = 2 1 ∣ S ∣ ≤ D ∑ e S ∂ S H ( b ) = 2 H ( z ) ∈ { − 1/2 , 1/2 } . (28)
The second equality cancels the residual normalizations in (25) ; the last equality is the exact Taylor identity (21) . The whole circuit uses at most B B B queries.
Exact amplification. The magnitude of α x \alpha_x α x is now known and independent of x x x . We use the standard three-call specialization of exact amplitude amplification [9 ] , also used by Pednekar and Podder [22 ] . Let Π = ∣ 0 ⟩ ⟨ 0 ∣ \Pi=|0\rangle\langle0| Π = ∣0 ⟩ ⟨ 0∣ project onto the joint all-zero state and set R = 2 Π − I R=2\Pi-I R = 2Π − I . For
K x = − U x R U x † R U x , K_x=-U_xRU_x^\dagger R U_x, K x = − U x R U x † R U x ,
the amplification identity gives
⟨ 0 ∣ K x ∣ 0 ⟩ = 3 α x − 4 α x ∣ α x ∣ 2 = 3 α x − 4 α x 3 , (29) \langle0|K_x|0\rangle=3\alpha_x-4\alpha_x|\alpha_x|^2=3\alpha_x-4\alpha_x^3, \tag*{(29)} ⟨ 0∣ K x ∣0 ⟩ = 3 α x − 4 α x ∣ α x ∣ 2 = 3 α x − 4 α x 3 , (29)
where the last equality uses that α x \alpha_x α x is real. Substituting α x = H ( z ) / 2 \alpha_x=H(z)/2 α x = H ( z ) /2 gives return amplitude H ( z ) H(z) H ( z ) . Since K x K_x K x is unitary and this amplitude has absolute value one, no amplitude remains in any orthogonal state. Hence
K x ∣ 0 ⟩ = H ( z ) ∣ 0 ⟩ = ( − 1 ) ( f ∘ g ) ( x ) ∣ 0 ⟩ . K_x|0\rangle=H(z)|0\rangle=(-1)^{(f\circ g)(x)}|0\rangle. K x ∣0 ⟩ = H ( z ) ∣0 ⟩ = ( − 1 ) ( f ∘ g ) ( x ) ∣0 ⟩ .
This is the required clean phase. The two copies of U x U_x U x and one copy of U x † U_x^\dagger U x † use at most 3 B = 6 m D + 12 E f t 3B = 6mD + 12E_f t 3 B = 6 m D + 12 E f t queries.
Finally, the standard controlled clean-phase construction from § 2 converts K x K_x K x into an exact decision algorithm with the same query cost. This proves (19) and both claims of the theorem. □ \square □
An error threshold controlled by the outer degree
Theorem 3.1 requires an inner error of order 1 / n 1/n 1/ n . The dependence on n n n comes from summing over subsets of outer coordinates: the normalization contains ∑ j ≤ D ( n j ) ( 2 ε ) j \sum_{j\le D} \binom{n}{j}(2\varepsilon)^j ∑ j ≤ D ( j n ) ( 2 ε ) j . This section replaces that expansion by one indexed by the query positions of an exact outer algorithm. Its clean phase implementation has only 2 Q E ( f ) 2Q_E(f) 2 Q E ( f ) such positions.
The central point is that the number of query positions and the degree play different roles. The former controls the normalization of the expansion; the latter controls how many corrections a branch must perform. More precisely, we construct a formal interpolation whose return amplitude is
H ( b + λ ( z − b ) ) . H(b+\lambda(z-b)). H ( b + λ ( z − b )) .
This scalar polynomial has degree at most D = deg ( f ) D=\deg(f) D = deg ( f ) , even though the interpolating query operators need not be polynomial in λ \lambda λ . We may therefore discard all terms of total order greater than D D D after taking the return amplitude. A uniform bound on the operator coefficients makes the remaining terms implementable at constant normalization. The resulting error threshold initially depends on Q E ( f ) Q_E(f) Q E ( f ) ; the known polynomial relation between Q E ( f ) Q_E(f) Q E ( f ) and degree then converts it to a threshold depending on D D D , at constant overhead.
Theorem 4.1 (Composition with a degree-controlled error threshold). Let f : { 0 , 1 } n → { 0 , 1 } f:\{0,1\}^n\to\{0,1\} f : { 0 , 1 } n → { 0 , 1 } and g : { 0 , 1 } m → { 0 , 1 } g:\{0,1\}^m\to\{0,1\} g : { 0 , 1 } m → { 0 , 1 } be nonconstant total Boolean functions , and write D = deg ( f ) D=\deg(f) D = deg ( f ) and E f = Q E ( f ) E_f=Q_E(f) E f = Q E ( f ) . Then
Q E ( f ∘ g ) ≤ 6 m D + 12 E f Q 1 / ( 1024 E f 2 ) ( g ) . (30) Q_E(f\circ g)\le6mD+12E_f Q_{1/(1024E_f^2)}(g). \tag*{(30)} Q E ( f ∘ g ) ≤ 6 m D + 12 E f Q 1/ ( 1024 E f 2 ) ( g ) . (30) In particular,
Q E ( f ∘ g ) = O ( m deg ( f ) + Q E ( f ) Q 1 / ( 4 deg ( f ) ) ( g ) ) . (31) Q_E(f\circ g)=O\left(m\deg(f)+Q_E(f)Q_{1/(4\deg(f))}(g)\right). \tag*{(31)} Q E ( f ∘ g ) = O ( m deg ( f ) + Q E ( f ) Q 1/ ( 4 d e g ( f )) ( g ) ) . (31) An explicit choice of the universal constants is
Q E ( f ∘ g ) ≤ 6 m D + 804 E f Q 1 / ( 4 D ) ( g ) . (32) Q_E(f\circ g)\le6mD+804E_f Q_{1/(4D)}(g). \tag*{(32)} Q E ( f ∘ g ) ≤ 6 m D + 804 E f Q 1/ ( 4 D ) ( g ) . (32) The constructions also give clean phase algorithms with these query costs.
Overview of the algorithm
Fix an inner algorithm A A A of query cost t t t and error at most ε = 1 / ( 1024 E f 2 ) \varepsilon=1/(1024E_f^2) ε = 1/ ( 1024 E f 2 ) . We use its compute–phase–uncompute reflection as an approximate inner query. The proof has four parts.
First, for every inner input u u u , we interpolate between this reflection and one that acts on the initial state with the correct sign z u = ( − 1 ) g ( u ) z_u=(-1)^{g(u)} z u = ( − 1 ) g ( u ) . The expectation of the interpolated reflection changes linearly with the interpolation parameter. Second, we show that the Taylor coefficients of these reflections admit input-independent norm bounds whose sum is O ( ε ) O(\sqrt{\varepsilon}) O ( ε ) . Third, we substitute the reflections into the clean outer circuit and show that its return amplitude has degree at most D D D . Finally, we implement the terms of Taylor order at most D D D and combine them coherently. The interpolation is a device for specifying the correction operators; the algorithm does not need to implement an interpolating reflection at an arbitrary parameter. A zero-order coefficient is implemented directly by A † Z o u t A A^\dagger Z_{\mathrm{out}}A A † Z out A . A positive-order coefficient is implemented by reading the selected inner block and using the resulting string to control a fixed unitary dilation. A retained term contains at most D D D positive-order factors, so these full-block reads cost at most 2 m D 2mD 2 m D . The remaining query cost is at most 4 E f t 4E f_t 4 E f t . The coefficient bounds make the total normalization less than two, and exact amplitude amplification completes the construction.
An interpolation of the inner reflection
For an inner input u u u , let A u A_u A u denote the unitary circuit of A A A , including all its work registers. Define
z u = ( − 1 ) g ( u ) , p u = p e r r ( u ) , V u = A u † Z o u t A u . z_u=(-1)^{g(u)}, \qquad p_u=p_{\mathrm{err}}(u), \qquad V_u=A_u^\dagger Z_{\mathrm{out}}A_u. z u = ( − 1 ) g ( u ) , p u = p err ( u ) , V u = A u † Z out A u .
Thus V u V_u V u is a Hermitian unitary of query cost 2 t 2t 2 t , and
⟨ 0 ∣ V u ∣ 0 ⟩ = z u ( 1 − 2 p u ) = : b u . (33) \langle0|V_u|0\rangle=z_u(1-2p_u)=:b_u. \tag*{(33)} ⟨ 0∣ V u ∣0 ⟩ = z u ( 1 − 2 p u ) =: b u . (33)
We construct a family of reflections for which this expectation moves from the approximate sign b u b_u b u to the exact sign z u z_u z u .
Lemma 4.2 (Interpolating reflection). For every inner input u u u , there is an operator-valued function V u ( λ ) V_u(\lambda) V u ( λ ) with the following properties:
V u ( 0 ) = V u V_u(0)=V_u V u ( 0 ) = V u ;
V u ( λ ) V_u(\lambda) V u ( λ ) is a Hermitian unitary for real 0 ≤ λ ≤ 1 0\leq\lambda\leq1 0 ≤ λ ≤ 1 ;
if e u = z u − b u = 2 z u p u e_u=z_u-b_u=2z_up_u e u = z u − b u = 2 z u p u , then
⟨ 0 ∣ V u ( λ ) ∣ 0 ⟩ = b u + λ e u ; (34) \langle0|V_u(\lambda)|0\rangle=b_u+\lambda e_u; \tag*{(34)} ⟨ 0∣ V u ( λ ) ∣0 ⟩ = b u + λ e u ; (34) V u ( 1 ) ∣ 0 ⟩ = z u ∣ 0 ⟩ V_u(1)|0\rangle=z_u|0\rangle V u ( 1 ) ∣0 ⟩ = z u ∣0 ⟩ .
Moreover, V u ( λ ) V_u(\lambda) V u ( λ ) has a Taylor series about zero that converges absolutely in operator norm for ∣ λ ∣ ≤ 1 |\lambda|\leq1 ∣ λ ∣ ≤ 1 .
Proof. Write p = p u p=p_u p = p u and z = z u z=z_u z = z u . If p = 0 p=0 p = 0 , then V u ∣ 0 ⟩ = z ∣ 0 ⟩ V_u|0\rangle=z|0\rangle V u ∣0 ⟩ = z ∣0 ⟩ , and the constant family V u ( λ ) = V u V_u(\lambda)=V_u V u ( λ ) = V u has every required property. We may therefore assume 0 < p ≤ ε < 1 / 2 0<p\leq\varepsilon<1/2 0 < p ≤ ε < 1/2 .
Only a two-dimensional subspace needs to change. Define
∣ r u ⟩ = z V u ∣ 0 ⟩ − ( 1 − 2 p ) ∣ 0 ⟩ 2 p ( 1 − p ) . |r_u\rangle=\frac{zV_u|0\rangle-(1-2p)|0\rangle}{2\sqrt{p(1-p)}}. ∣ r u ⟩ = 2 p ( 1 − p ) z V u ∣0 ⟩ − ( 1 − 2 p ) ∣0 ⟩ .
The numerator is orthogonal to ∣ 0 ⟩ |0\rangle ∣0 ⟩ by (33) ; its squared norm is 4 p ( 1 − p ) 4p(1-p) 4 p ( 1 − p ) because V u V_u V u is unitary. Thus ∣ 0 ⟩ , ∣ r u ⟩ |0\rangle,|r_u\rangle ∣0 ⟩ , ∣ r u ⟩ is an orthonormal pair. Their span, denoted P u P_u P u , is invariant under V u V_u V u . Indeed, the definition gives V u ∣ 0 ⟩ V_u|0\rangle V u ∣0 ⟩ in this span, and applying V u V_u V u again determines V u ∣ r u ⟩ V_u|r_u\rangle V u ∣ r u ⟩ . In this basis,
V u ∣ P u = z ( 1 − 2 p 2 p ( 1 − p ) 2 p ( 1 − p ) − 1 + 2 p ) . V_u\big|_{P_u}
=
z\begin{pmatrix}
1-2p & 2\sqrt{p(1-p)}\\
2\sqrt{p(1-p)} & -1+2p
\end{pmatrix}. V u P u = z ( 1 − 2 p 2 p ( 1 − p ) 2 p ( 1 − p ) − 1 + 2 p ) .
Since V u V_u V u is Hermitian, P u ⊥ P_u^\perp P u ⊥ is invariant as well.
We now reduce the parameter p p p continuously to zero. On P u \mathcal{P}_u P u , set
V u ( λ ) ∣ P u = z ( 1 − 2 p + 2 p λ 2 p ( 1 − λ ) ( 1 − p + p λ ) 2 p ( 1 − λ ) ( 1 − p + p λ ) − 1 + 2 p − 2 p λ ) , (35) \left.V_u(\lambda)\right|_{\mathcal{P}_u}=z\begin{pmatrix} 1-2p+2p\lambda& 2\sqrt{p}\sqrt{(1-\lambda)(1-p+p\lambda)} \\ 2\sqrt{p}\sqrt{(1-\lambda)(1-p+p\lambda)} & -1+2p-2p\lambda\end{pmatrix}, \tag*{(35)} V u ( λ ) ∣ P u = z ( 1 − 2 p + 2 p λ 2 p ( 1 − λ ) ( 1 − p + p λ ) 2 p ( 1 − λ ) ( 1 − p + p λ ) − 1 + 2 p − 2 p λ ) , (35)
and leave the action on P u ⊥ \mathcal{P}_u^\perp P u ⊥ unchanged. For real λ ∈ [ 0 , 1 ] \lambda\in[0,1] λ ∈ [ 0 , 1 ] , the displayed matrix is
z ( 1 − 2 p ′ 2 p ′ ( 1 − p ′ ) 2 p ′ ( 1 − p ′ ) − 1 + 2 p ′ ) , p ′ = p ( 1 − λ ) . z\begin{pmatrix} 1-2p' & 2\sqrt{p'(1-p')} \\ 2\sqrt{p'(1-p')} & -1+2p' \end{pmatrix}, \qquad p'=p(1-\lambda). z ( 1 − 2 p ′ 2 p ′ ( 1 − p ′ ) 2 p ′ ( 1 − p ′ ) − 1 + 2 p ′ ) , p ′ = p ( 1 − λ ) .
Its square is the identity, so it remains a Hermitian reflection. At λ = 0 \lambda=0 λ = 0 it equals the original matrix. Its first diagonal entry is b u + 2 z u p u λ b_u+2z_up_u\lambda b u + 2 z u p u λ , which proves (34) . At λ = 1 \lambda=1 λ = 1 , its off-diagonal entries vanish and its action on ∣ 0 ⟩ \lvert0\rangle ∣ 0 ⟩ is multiplication by z u z_u z u .
For the convergence statement, factor the off-diagonal entry as
2 z p ( 1 − p ) 1 − λ 1 + q λ , q = p 1 − p < 1. (36) 2z\sqrt{p(1-p)}\sqrt{1-\lambda}\sqrt{1+q\lambda}, \qquad q=\frac{p}{1-p}<1. \tag*{(36)} 2 z p ( 1 − p ) 1 − λ 1 + q λ , q = 1 − p p < 1. (36)
The binomial series of 1 − λ \sqrt{1-\lambda} 1 − λ converges absolutely on the closed unit disk. The series of 1 + q λ \sqrt{1+q\lambda} 1 + q λ has radius 1 / q > 1 1/q>1 1/ q > 1 . Their product therefore converges absolutely for ∣ λ ∣ ≤ 1 |\lambda|\leq1 ∣ λ ∣ ≤ 1 . The diagonal entries are affine and the orthogonal complement is constant, proving convergence in operator norm. □
A uniform bound on the Taylor coefficients
A bound on the coefficients for each individual input would not yet suffice: the amplitudes used to prepare the branch selector must be fixed before seeing the input. We therefore bound every coefficient by a common sequence that depends only on the promised error ε \varepsilon ε .
Lemma 4.3 (Uniform coefficient majorant). Write
V u ( λ ) = V u ( 0 ) + ∑ k ≥ 1 λ k C u , k . (37) V_u(\lambda)=V_u(0)+\sum_{k\geq1}\lambda^k C_{u,k}. \tag*{(37)} V u ( λ ) = V u ( 0 ) + k ≥ 1 ∑ λ k C u , k . (37) There are nonnegative numbers w k w_k w k , depending only on ε \varepsilon ε , such that
∥ C u , k ∥ ≤ w k for every u , k , ∑ k ≥ 1 w k ≤ 8 ε . (38) \lVert C_{u,k}\rVert\leq w_k \quad\text{for every }u,k,\qquad\sum_{k\geq1}w_k\leq8\sqrt{\varepsilon}. \tag*{(38)} ∥ C u , k ∥ ≤ w k for every u , k , k ≥ 1 ∑ w k ≤ 8 ε . (38) Each C u , k C_{u,k} C u , k is Hermitian.
Proof. The only nonconstant entries occur in the two-dimensional matrix (35) . To bound its off-diagonal coefficients uniformly over p ≤ ε p\leq\varepsilon p ≤ ε , put
q ∗ = ε 1 − ε , a j = ∣ ( 1 / 2 j ) ∣ ( j ≥ 0 ) , γ k = ∑ j = 0 k a j a k − j q ∗ k − j . q_*=\frac{\varepsilon}{1-\varepsilon},\qquad a_j=\left|\binom{1/2}{j}\right|\ (j\geq0),\qquad\gamma_k=\sum_{j=0}^{k}a_j a_{k-j}q_*^{k-j}. q ∗ = 1 − ε ε , a j = ( j 1/2 ) ( j ≥ 0 ) , γ k = j = 0 ∑ k a j a k − j q ∗ k − j . Here a 0 = γ 0 = 1 a_0=\gamma_0=1 a 0 = γ 0 = 1 . The coefficient of λ k \lambda^k λ k in 1 − λ 1 + ( p / ( 1 − p ) ) λ \sqrt{1-\lambda}\sqrt{1+(p/(1-p))\lambda} 1 − λ 1 + ( p / ( 1 − p )) λ has absolute value at most γ k \gamma_k γ k : apply the triangle inequality to the product of the two binomial series and use p / ( 1 − p ) ≤ q ∗ p/(1-p)\leq q_* p / ( 1 − p ) ≤ q ∗ . After restoring the factor in (36) , the off-diagonal coefficient has operator norm at most 2 ε γ k 2\sqrt{\varepsilon}\,\gamma_k 2 ε γ k .
The diagonal part contributes only at order one, with norm 2 p 2p 2 p . Thus the following choice bounds the complete coefficient:
w k = 2 ε 1 { k = 1 } + 2 ε γ k , k ≥ 1. (39) w_k=2\varepsilon\mathbf{1}_{\{k=1\}}+2\sqrt{\varepsilon}\,\gamma_k,\qquad k\geq1. \tag*{(39)} w k = 2 ε 1 { k = 1 } + 2 ε γ k , k ≥ 1. (39)
For p = 0 p=0 p = 0 all positive-order coefficients vanish, so the same bound applies. For p > 0 p>0 p > 0 they vanish on P u ⊥ \mathcal{P}_u^\perp P u ⊥ ; hence there is no additional contribution from the rest of the workspace.
It remains to sum these bounds. The absolute binomial coefficients satisfy
∑ j ≥ 0 a j = 2 , ∑ j ≥ 0 a j q ∗ j = 2 − 1 − q ∗ ≤ 2. \sum_{j\ge0} a_j=2,\qquad\sum_{j\ge0}a_jq_*^j=2-\sqrt{1-q_*}\le2. j ≥ 0 ∑ a j = 2 , j ≥ 0 ∑ a j q ∗ j = 2 − 1 − q ∗ ≤ 2.
The second identity is valid because q ∗ < 1 q_*<1 q ∗ < 1 , as ε ≤ 1 / 1024 \varepsilon\le1/1024 ε ≤ 1/1024 . The convolution defining γ k \gamma_k γ k therefore gives
∑ k ≥ 1 γ k = ( ∑ j ≥ 0 a j ) ( ∑ j ≥ 0 a j q ∗ j ) − 1 = 3 − 2 1 − q ∗ ≤ 3. \sum_{k\ge1}\gamma_k=\left(\sum_{j\ge0}a_j\right)\left(\sum_{j\ge0}a_jq_*^j\right)-1=3-2\sqrt{1-q_*}\le3. k ≥ 1 ∑ γ k = ( j ≥ 0 ∑ a j ) ( j ≥ 0 ∑ a j q ∗ j ) − 1 = 3 − 2 1 − q ∗ ≤ 3.
Substituting into (39) , we obtain
∑ k ≥ 1 w k ≤ 2 ε + 6 ε ≤ 8 ε . \sum_{k\ge1}w_k\le2\varepsilon+6\sqrt{\varepsilon}\le8\sqrt{\varepsilon}. k ≥ 1 ∑ w k ≤ 2 ε + 6 ε ≤ 8 ε .
Finally, the matrix in (35) has Hermitian Taylor coefficients: each is a real linear combination of the fixed diagonal and off-diagonal Hermitian matrices on P u \mathcal{P}_u P u . This also proves the assertion on the full workspace.
The return amplitude has low degree
Fix a composed input x = ( x ( 1 ) , … , x ( n ) ) x=(x^{(1)},\ldots,x^{(n)}) x = ( x ( 1 ) , … , x ( n ) ) . We allocate one persistent inner workspace per block. The same workspace is used whenever the outer circuit queries that block. Write V i ( λ ) = V x ( i ) ( λ ) V_i(\lambda)=V_{x^{(i)}}(\lambda) V i ( λ ) = V x ( i ) ( λ ) for the reflection on the i i i th workspace. With J J J denoting the outer query-index register and zero its dummy index, the virtual oracle is
O x ( λ ) = ∣ 0 ⟩ ⟨ 0 ∣ J ⊗ I + ∑ i = 1 n ∣ i ⟩ ⟨ i ∣ J ⊗ V i ( λ ) . (40) O_x(\lambda)=|0\rangle\langle0|_J\otimes I+\sum_{i=1}^{n}|i\rangle\langle i|_J\otimes V_i(\lambda). \tag*{(40)} O x ( λ ) = ∣0 ⟩ ⟨ 0 ∣ J ⊗ I + i = 1 ∑ n ∣ i ⟩ ⟨ i ∣ J ⊗ V i ( λ ) . (40)
Let C f C_f C f be an exact E f E_f E f -query algorithm for f f f . Replace each of the T = 2 E f T=2E_f T = 2 E f queries in its clean phase circuit C f † Z o u t C f C_f^\dagger Z_{\mathrm{out}}C_f C f † Z out C f by O x ( λ ) O_x(\lambda) O x ( λ ) , and denote the resulting circuit by U x ( λ ) U_x(\lambda) U x ( λ ) . The outer gates act only on the outer registers. For real λ ∈ [ 0 , 1 ] \lambda\in[0,1] λ ∈ [ 0 , 1 ] , every substituted oracle is unitary.
Lemma 4.4 (Polynomial return amplitude). Let H H H be the signed multilinear polynomial of f f f , and set b i = z i ( 1 − 2 p i ) b_i=z_i(1-2p_i) b i = z i ( 1 − 2 p i ) and e i = 2 z i p i e_i=2z_ip_i e i = 2 z i p i for each inner block. Then
P x ( λ ) : = ⟨ 0 ∣ U x ( λ ) ∣ 0 ⟩ = H ( b + λ e ) . (41) P_x(\lambda):=\langle0|U_x(\lambda)|0\rangle=H(b+\lambda e). \tag*{(41)} P x ( λ ) := ⟨ 0∣ U x ( λ ) ∣0 ⟩ = H ( b + λ e ) . (41) In particular, P x P_x P x has degree at most D D D and P x ( 1 ) = H ( z ) = ( − 1 ) ( f ∘ g ) ( x ) P_x(1)=H(z)=(-1)^{(f\circ g)(x)} P x ( 1 ) = H ( z ) = ( − 1 ) ( f ∘ g ) ( x ) .
Proof. Fix real λ ∈ [ 0 , 1 ] \lambda\in[0,1] λ ∈ [ 0 , 1 ] . The reflections V 1 ( λ ) , … , V n ( λ ) V_1(\lambda),\ldots,V_n(\lambda) V 1 ( λ ) , … , V n ( λ ) act on disjoint registers, so they commute and admit a joint spectral decomposition. Their joint eigenvalues are sign strings y ∈ { − 1 , 1 } n y\in\{-1,1\}^n y ∈ { − 1 , 1 } n . Conditioned on such a sign string, (40) is precisely the usual outer phase oracle with input signs y y y . The exact outer circuit consequently returns its workspace to zero and contributes the clean phase H ( y ) H(y) H ( y ) .
To compute the return amplitude, it remains to average these phases over the spectral distribution of the initial inner state. That state is a product of all-zero states, so its spectral signs Y 1 , … , Y n Y_1,\ldots,Y_n Y 1 , … , Y n are independent. Their expectations are
E Y i = ⟨ 0 ∣ V i ( λ ) ∣ 0 ⟩ = b i + λ e i . \mathbb{E}Y_i=\langle0|V_i(\lambda)|0\rangle=b_i+\lambda e_i. E Y i = ⟨ 0∣ V i ( λ ) ∣0 ⟩ = b i + λ e i .
We therefore have
P x ( λ ) = E H ( Y ) = ∑ S ⊆ [ n ] H ^ ( S ) ∏ i ∈ S ( b i + λ e i ) = H ( b + λ e ) . P_x(\lambda)=\mathbb{E}H(Y)=\sum_{S\subseteq[n]}\widehat{H}(S)\prod_{i\in S}(b_i+\lambda e_i)=H(b+\lambda e). P x ( λ ) = E H ( Y ) = S ⊆ [ n ] ∑ H ( S ) i ∈ S ∏ ( b i + λ e i ) = H ( b + λ e ) .
The second equality uses independence, and the last uses multilinearity of H H H . Every nonzero monomial has at most D D D variables, proving the degree bound. At λ = 1 \lambda=1 λ = 1 the argument of H H H is b + e = z b+e=z b + e = z , giving the exact composed sign.
For the coefficient comparison below, we also use this identity as an identity of power series. Lemma 4.2 makes the circuit product analytic on ∣ λ ∣ < 1 |\lambda|<1 ∣ λ ∣ < 1 . Its return amplitude agrees there with the polynomial H ( b + λ e ) H(b+\lambda e) H ( b + λ e ) , since the two analytic functions agree on the real interval [ 0 , 1 ) [0,1) [ 0 , 1 ) . Their Taylor coefficients are therefore equal. Absolute convergence on the closed unit disk permits evaluation at λ = 1 \lambda=1 λ = 1 .
Implementing the truncated operator expansion
We now turn the preceding scalar identity into a finite quantum circuit. Expanding a virtual query gives zero-order coefficient O x ( 0 ) O_x(0) O x ( 0 ) and, for k ≥ 1 k\ge1 k ≥ 1 , coefficient
C x , k = ∑ i = 1 n ∣ i ⟩ ⟨ i ∣ J ⊗ C x ( i ) , k . C_{x,k}=\sum_{i=1}^{n}|i\rangle\langle i|_J\otimes C_{x^{(i)},k}. C x , k = i = 1 ∑ n ∣ i ⟩ ⟨ i ∣ J ⊗ C x ( i ) , k .
The dummy-index block of C x , k C_{x,k} C x , k is zero. This is a direct sum over the query index, not a sum acting on the same index subspace; hence ∥ C x , k ∥ ≤ w k \lVert C_{x,k}\rVert\le w_k ∥ C x , k ∥ ≤ w k .
Which terms are retained. A term in the expanded outer circuit is indexed by k = ( k 1 , … , k T ) ∈ Z ≥ 0 T k=(k_1,\ldots,k_T)\in\mathbb{Z}_{\ge0}^{T} k = ( k 1 , … , k T ) ∈ Z ≥ 0 T . In query position j j j , it uses the coefficient of order k j k_j k j ; all input-independent outer gates retain their original positions. The resulting factors are multiplied in circuit order. Their total Taylor order is ∣ k ∣ = ∑ j k j |k|=\sum_j k_j ∣ k ∣ = ∑ j k j . Let a k ( x ) a_k(x) a k ( x ) be the return amplitude of this unnormalized product.
Retain all terms with ∣ k ∣ ≤ D |k|\le D ∣ k ∣ ≤ D . There are finitely many, and
∑ ∣ k ∣ ≤ D a k ( x ) = P x ( 1 ) = H ( z ) . (42) \sum_{|k|\le D}a_k(x)=P_x(1)=H(z). \tag*{(42)} ∣ k ∣ ≤ D ∑ a k ( x ) = P x ( 1 ) = H ( z ) . (42)
To justify this equality, first expand the whole circuit. The coefficient majorant makes the expansion absolutely convergent, so we may group terms by total order. The sum at each order is the corresponding Taylor coefficient of P x P_x P x . Lemma 4.4 says that these scalar coefficients vanish above order D D D . Thus truncation preserves the return amplitude at one. No claim is made that the individual high-order operator products vanish.
How a coefficient is implemented. Set w 0 = 1 w_0=1 w 0 = 1 . A zero-order factor is implemented with 2 t 2t 2 t queries by applying A A A , the output phase, and A † A^\dagger A † to the selected block’s workspace. That workspace need not still be zero: V u = A u † Z o u t A u V_u=A_u^\dagger Z_{\mathrm{out}}A_u V u = A u † Z out A u is an operator identity, so this implementation is valid on every intermediate state.
For a positive-order factor, the normalized coefficient K u , k = C u , k / w k K_{u,k}=C_{u,k}/w_k K u , k = C u , k / w k is a Hermitian contraction. Fix its unitary dilation
D ( K u , k ) = ( K u , k − I − K u , k 2 I − K u , k 2 K u , k ) . \mathcal{D}(K_{u,k})=
\begin{pmatrix}
K_{u,k} & -\sqrt{I-K_{u,k}^{2}}\\
\sqrt{I-K_{u,k}^{2}} & K_{u,k}
\end{pmatrix}. D ( K u , k ) = K u , k I − K u , k 2 − I − K u , k 2 K u , k .
The displayed blocks refer to a new ancilla qubit. Its zero-to-zero block is K u , k K_{u,k} K u , k . To apply this dilation, coherently read the selected input block into a register, apply the dilation controlled by the resulting string u u u , and uncompute the register. This costs 2 m 2m 2 m queries. For every possible u u u and k k k , the matrix of the dilation is fixed in advance as part of the circuit description. Thus its controlled application is an input-independent unitary once the string u u u has been queried. Arbitrary input-independent unitaries are free in the query model. At the dummy index, use a query-free dilation whose zero-to-zero block is the zero operator.
Each positive-order position receives a fresh dilation ancilla, and no later operation acts on that ancilla. Consequently, taking the zero-to-zero block on all these ancillas gives exactly the ordered product of the normalized coefficients. This observation is important: reusing a dilation ancilla could allow amplitude that had left its zero state to return later, producing additional terms. With fresh ancillas, the branch indexed by k k k has return amplitude
a k ( x ) w k , w k = ∏ j = 1 T w k j . \frac{a_k(x)}{w_k}, \qquad w_k = \prod_{j=1}^{T} w_{k_j}. w k a k ( x ) , w k = j = 1 ∏ T w k j .
A branch with zero weight contributes nothing and may be omitted.
Why the branch cost depends on degree. Every positive-order position contributes at least one to ∣ k ∣ |k| ∣ k ∣ . A retained branch therefore contains at most D D D such positions. There are at most T T T zero-order positions, so a uniform upper bound on the branch cost is
B = 2 m D + 2 t T = 2 m D + 4 E f t . (43) B = 2mD + 2tT = 2mD + 4E_f t. \tag*{(43)} B = 2 m D + 2 tT = 2 m D + 4 E f t . (43)
This bound also applies to a coherent choice of branch. To see this, pad each complete branch to B B B raw input queries. Between successive raw queries, apply the gates appropriate to that branch, controlled by the branch selector, and route the next query to its required input coordinate. Dummy queries supply the padding. All branches then use the same raw-query schedule. Padding each virtual-query position separately would unnecessarily charge the larger of the two slot costs at every position; aligning the complete branches preserves (43) .
Proof of Theorem 4.1 . Choose A A A with error ε = 1 / ( 1024 E f 2 ) \varepsilon= 1/(1024E_f^2) ε = 1/ ( 1024 E f 2 ) and query cost t = Q ε ( g ) t = Q_\varepsilon(g) t = Q ε ( g ) . We have implemented each retained term at the common cost B B B in (43) . We first bound the total weight needed to combine these terms:
L = ∑ ∣ k ∣ ≤ D ∏ j = 1 T w k j ≤ ( 1 + ∑ k ≥ 1 w k ) T ≤ ( 1 + 8 ε ) 2 E f ≤ exp ( 16 E f ε ) = e 1 / 2 < 2. (44) \begin{aligned}
L &= \sum_{|k|\le D} \prod_{j=1}^{T} w_{k_j} \\
&\le\left(1+\sum_{k\ge1} w_k\right)^T \le(1+8\sqrt{\varepsilon})^{2E_f} \le\exp(16E_f\sqrt{\varepsilon}) = e^{1/2} < 2. \tag*{(44)}
\end{aligned} L = ∣ k ∣ ≤ D ∑ j = 1 ∏ T w k j ≤ ( 1 + k ≥ 1 ∑ w k ) T ≤ ( 1 + 8 ε ) 2 E f ≤ exp ( 16 E f ε ) = e 1/2 < 2. (44)
The first inequality only adds nonnegative terms. The second is the uniform majorant from Lemma 4.3. Crucially, L L L and all the branch weights are independent of the composed input.
Prepare a selector with amplitude w k / 2 \sqrt{w_k/2} w k /2 on each retained branch. Complete its normalization with a query-free branch of weight 2 − L 2-L 2 − L and return amplitude zero. Apply the selected branch circuit and unprepare the selector. The resulting return amplitude is
1 2 ∑ ∣ k ∣ ≤ D w k a k ( x ) w k = H ( z ) 2 . \frac{1}{2}\sum_{|k|\le D} w_k\frac{a_k(x)}{w_k} = \frac{H(z)}{2}. 2 1 ∣ k ∣ ≤ D ∑ w k w k a k ( x ) = 2 H ( z ) .
where the equality is (42) . The three-call identity (29) , a specialization of exact amplitude amplification [9 ] , turns this into return amplitude H ( z ) H(z) H ( z ) . Since ∣ H ( z ) ∣ = 1 |H(z)| = 1 ∣ H ( z ) ∣ = 1 , the whole final state is H ( z ) ∣ 0 ⟩ H(z)|0\rangle H ( z ) ∣0 ⟩ ; all work registers are clean. The cost is 3 B = 6 m D + 12 E f t 3B = 6mD + 12E_ft 3 B = 6 m D + 12 E f t , proving (30) .
We next replace the error parameter by one depending only on degree. The known deterministic degree bound [20 ] gives
E f ≤ D ( f ) ≤ 2 deg ( f ) 3 = 2 D 3 , (45) E_f \le D(f) \le2\deg(f)^3 = 2D^3, \tag*{(45)} E f ≤ D ( f ) ≤ 2 deg ( f ) 3 = 2 D 3 , (45)
where D ( f ) D(f) D ( f ) denotes deterministic query complexity. It is therefore enough to reduce the inner error to 1 / ( 4096 D 6 ) 1/(4096D^6) 1/ ( 4096 D 6 ) . Start with an algorithm of error at most 1 / ( 4 D ) 1/(4D) 1/ ( 4 D ) , run 67 independent copies, and take their majority. For D ≥ 2 D \ge2 D ≥ 2 , an incorrect majority requires at least 34 failed copies, so its probability is at most
2 67 ( 1 4 D ) 34 = 1 2 D 34 ≤ 1 4096 D 6 ≤ 1 1024 E f 2 . 2^{67}\left(\frac{1}{4D}\right)^{34} = \frac{1}{2D^{34}} \le\frac{1}{4096D^6} \le\frac{1}{1024E_f^2}. 2 67 ( 4 D 1 ) 34 = 2 D 34 1 ≤ 4096 D 6 1 ≤ 1024 E f 2 1 .
For D = 1 D = 1 D = 1 , the standard majority tail bound gives error at most exp ( − 67 / 8 ) < 1 / 4096 \exp(-67/8) < 1/4096 exp ( − 67/8 ) < 1/4096 , which is again sufficient. The repetitions and the majority computation can be performed coherently, retaining the work registers of all copies. Their total query cost is 67 Q 1 / ( 4 D ) ( g ) 67Q_{1/(4D)}(g) 67 Q 1/ ( 4 D ) ( g ) . Substituting this cost into (30) proves (32) , and hence (31) .
The correction cost in this proof is a full-block read, not merely an exact evaluation of the inner output. The operator C u , k / w k C_{u,k/w_k} C u , k / w k depends on the error direction ∣ r u ⟩ |r_u\rangle ∣ r u ⟩ and the error probability p u p_u p u , as well as on g ( u ) g(u) g ( u ) . Knowing g ( u ) g(u) g ( u ) alone does not specify the dilation that the correction must apply. This is the specific obstacle to replacing m m m by Q E ( g ) Q_E(g) Q E ( g ) in the present construction; we return to that question in § 12 .
An improved exact algorithm for recursive NAE
Let N A E 3 : { 0 , 1 } 3 → { 0 , 1 } \mathrm{NAE}_3:\{0,1\}^3 \to\{0,1\} NAE 3 : { 0 , 1 } 3 → { 0 , 1 } be the not-all-equal function, which is zero precisely on 000 and 111. Define F 0 ( x ) = x F_0(x)=x F 0 ( x ) = x and F d = N A E 3 ∘ F d − 1 F_d=\mathrm{NAE}_3\circ F_{d-1} F d = NAE 3 ∘ F d − 1 for d ≥ 1 d\ge1 d ≥ 1 . Thus F d F_d F d is computed by the complete ternary tree of depth d d d with a copy of N A E 3 \mathrm{NAE}_3 NAE 3 at each internal vertex. Write
E d = Q E ( F d ) , a = 3 2 . E_d = Q_E(F_d), \qquad a = \frac{3}{\sqrt{2}}. E d = Q E ( F d ) , a = 2 3 .
Ambainis [3 , 4 ] gave an exact algorithm using O ( 2 11 d / 8 ) = O ( 2.593 … d ) O(2^{11d/8}) = O(2.593\ldots^d) O ( 2 11 d /8 ) = O ( 2.593 … d ) queries. We obtain an upper bound whose exponential rate matches the general adversary lower bound. The useful feature of this family is that its degree, bounded-error complexity, and input length grow at three different exponential rates. We exploit this difference by applying the composition theorem at a carefully chosen level of the tree.
Theorem 5.1. For all d ≥ 0 d \ge0 d ≥ 0 ,
Ω ( a d ) ≤ Q E ( F d ) ≤ a d exp ( O ( ( log ( d + 2 ) ) 2 ) ) . (46) \Omega(a^d) \le Q_E(F_d) \le a^d \exp\left(O\left((\log(d+2))^2\right)\right). \tag*{(46)} Ω ( a d ) ≤ Q E ( F d ) ≤ a d exp ( O ( ( log ( d + 2 ) ) 2 ) ) . (46) Consequently, for N = 3 d N=3^d N = 3 d ,
Q E ( F d ) = N log 3 ( 3 / 2 ) + o ( 1 ) , log 3 ( 3 / 2 ) = 0.684535 … . Q_E(F_d) = N^{\log_3(3/\sqrt{2})+o(1)}, \qquad\log_3(3/\sqrt{2}) = 0.684535\ldots. Q E ( F d ) = N l o g 3 ( 3/ 2 ) + o ( 1 ) , log 3 ( 3/ 2 ) = 0.684535 … .
Degree and adversary bounds
The construction uses the following standard parameters of recursive NAE.
Lemma 5.2. For every d ≥ 0 d \ge0 d ≥ 0 ,
deg ( F d ) = 2 d , Adv ± ( F d ) = a d , Q ( F d ) = Θ ( a d ) , \operatorname{deg}(F_d)=2^d,\qquad\operatorname{Adv}^{\pm}(F_d)=a^d,\qquad Q(F_d)=\Theta(a^d), deg ( F d ) = 2 d , Adv ± ( F d ) = a d , Q ( F d ) = Θ ( a d ) , where the constants in the last comparison are independent of d d d .
The degree-two polynomial of N A E 3 \mathrm{NAE}_3 NAE 3 and the value Adv ± ( N A E 3 ) = 3 / 2 \operatorname{Adv}^{\pm}(\mathrm{NAE}_3)=3/\sqrt{2} Adv ± ( NAE 3 ) = 3/ 2 are known; the latter is listed for the output-complementary function E Q U A L 3 \mathrm{EQUAL}_3 EQUAL 3 in Reichardt and Špalek [25 Table 1] . The displayed identities follow from the standard degree and adversary composition theorems and the characterization Q = Θ ( Adv ± ) Q=\Theta(\operatorname{Adv}^{\pm}) Q = Θ ( Adv ± ) [19 , 24 , 26 ] .
The recursive construction
Consider a split d = k + ℓ d=k+\ell d = k + ℓ . The top k k k levels form an outer tree F k F_k F k , and each of its leaves is replaced by an inner tree F ℓ F_\ell F ℓ . Thus F d = F k ∘ F ℓ F_d=F_k\circ F_\ell F d = F k ∘ F ℓ . We construct the exact algorithm for F k F_k F k recursively. For F ℓ F_\ell F ℓ , we use the bounded-error algorithm from Lemma 5.2, followed by standard coherent error reduction. The accuracy required by Theorem 4.1 is
ε k = 1 4 deg ( F k ) = 1 4 ⋅ 2 k . \varepsilon_k=\frac{1}{4\deg(F_k)}=\frac{1}{4\cdot2^k}. ε k = 4 deg ( F k ) 1 = 4 ⋅ 2 k 1 .
Since log ( 1 / ε k ) = O ( k + 1 ) \log(1/\varepsilon_k)=O(k+1) log ( 1/ ε k ) = O ( k + 1 ) , this inner algorithm uses O ( ( k + 1 ) a ℓ ) O((k+1)a^\ell) O (( k + 1 ) a ℓ ) queries. Substituting the outer degree 2 k 2^k 2 k , the inner input length 3 ℓ 3^\ell 3 ℓ , and this query cost into Theorem 4.1 gives, for 1 ≤ k < d 1\le k<d 1 ≤ k < d ,
E d ≤ C ( 2 k 3 d − k + k E k a d − k ) (47) E_d\le C\left(2^k3^{d-k}+kE_ka^{d-k}\right) \tag*{(47)} E d ≤ C ( 2 k 3 d − k + k E k a d − k ) (47)
where C C C is an absolute constant. The first term pays for reading the inner blocks used in the exact correction. The second term pays for substituting the approximate inner computations into the exact outer algorithm.
Our target is a cost close to a d a^d a d . The second term already has this exponential scale if E k E_k E k has scale a k a^k a k . We therefore choose the split so that the correction term is no larger than a d a^d a d . Solving 2 k 3 d − k = a d 2^k3^{d-k}=a^d 2 k 3 d − k = a d for k k k suggests
β = log ( 3 / a ) log ( 3 / 2 ) = 0.854755 … , k = ⌈ β d ⌉ , ℓ = d − k . (48) \beta=\frac{\log(3/a)}{\log(3/2)}=0.854755\ldots,\qquad k=\lceil\beta d\rceil,\qquad\ell=d-k. \tag*{(48)} β = log ( 3/2 ) log ( 3/ a ) = 0.854755 … , k = ⌈ β d ⌉ , ℓ = d − k . (48)
Rounding k k k upward only decreases the correction term, since 2 < 3 2<3 2 < 3 . Choose a fixed base depth d 0 d_0 d 0 large enough that 1 ≤ k < d 1\le k<d 1 ≤ k < d for d > d 0 d>d_0 d > d 0 . At depths at most d 0 d_0 d 0 , the algorithm reads all leaves. At a larger depth, it recursively constructs the exact algorithm for F k F_k F k and combines it with the above approximate algorithm for F ℓ F_\ell F ℓ . This specifies an exact algorithm at every depth: the exact recursive call has smaller depth, and every correction branch reads at most 2 k 2^k 2 k inner blocks of 3 ℓ 3^\ell 3 ℓ bits each.
Proof of Theorem 5.1. The choice of k k k in (48) gives
2 k 3 d − k a d = exp ( d log ( 3 / a ) − k log ( 3 / 2 ) ) ≤ 1. \frac{2^k3^{d-k}}{a^d}=\exp\bigl(d\log(3/a)-k\log(3/2)\bigr)\le1. a d 2 k 3 d − k = exp ( d log ( 3/ a ) − k log ( 3/2 ) ) ≤ 1.
It remains to control the overhead accumulated by the recursive exact calls. Normalize by the desired exponential factor and write u d = E d / a d u_d=E_d/a^d u d = E d / a d . Equation (47) becomes
u d ≤ C ( 1 + k u k ) . (49) u_d \le C(1+ku_k). \tag*{(49)} u d ≤ C ( 1 + k u k ) . (49)
Let V d = max { 1 , u d } V_d=\max\{1,u_d\} V d = max { 1 , u d } . Increasing a constant C 1 C_1 C 1 if necessary, we have
V d ≤ C 1 ( d + 1 ) V ⌈ β d ⌉ ( d > d 0 ) . V_d \le C_1(d+1)V_{\lceil\beta d\rceil}\qquad(d>d_0). V d ≤ C 1 ( d + 1 ) V ⌈ β d ⌉ ( d > d 0 ) .
Thus each recursive call incurs a factor O ( d ) O(d) O ( d ) in the normalized cost, while reducing the depth by a constant factor. To make this precise, put d 0 ′ = d d'_0=d d 0 ′ = d and d j + 1 ′ = ⌈ β d j ′ ⌉ d'_{j+1}=\lceil\beta d'_j\rceil d j + 1 ′ = ⌈ β d j ′ ⌉ , stopping when d j ′ ≤ d 0 d'_j\le d_0 d j ′ ≤ d 0 . Enlarge the fixed base threshold so that d 0 > 2 / ( 1 − β ) d_0>2/(1-\beta) d 0 > 2/ ( 1 − β ) . The accumulated rounding errors satisfy
d j ′ ≤ β j d + 1 1 − β . d'_j\le\beta^j d+\frac{1}{1-\beta}. d j ′ ≤ β j d + 1 − β 1 .
Hence there are L = O ( log ( d + 2 ) ) L=O(\log(d+2)) L = O ( log ( d + 2 )) stages. Multiplying the factors along this sequence, and using d j ′ ≤ d d'_j\le d d j ′ ≤ d before termination, gives
V d ≤ ( max 0 ≤ u ≤ d 0 V u ) ∏ j = 0 L − 1 C 1 ( d j ′ + 1 ) ≤ exp ( O ( ( log ( d + 2 ) ) 2 ) ) . V_d\le\left(\max_{0\le u\le d_0}V_u\right)\prod_{j=0}^{L-1}C_1(d'_j+1)\le\exp\left(O((\log(d+2))^2)\right). V d ≤ ( 0 ≤ u ≤ d 0 max V u ) j = 0 ∏ L − 1 C 1 ( d j ′ + 1 ) ≤ exp ( O (( log ( d + 2 ) ) 2 ) ) .
Multiplication by a d a^d a d proves the upper bound. The lower bound follows from Lemma 5.2 , since Q E ( F d ) ≥ Q ( F d ) = Ω ( a d ) Q_E(F_d)\ge Q(F_d)=\Omega(a^d) Q E ( F d ) ≥ Q ( F d ) = Ω ( a d ) . □
Ambainis’s construction [4 ] composes algorithms having a fixed return amplitude on each output class and uses exact amplitude amplification to improve their composition parameters. Here the approximate inner algorithm may have an input-dependent error probability. The correction in Theorem 4.1 removes this error exactly. Choosing the split in (48) makes that correction affordable without changing the exponential rate of the bounded-error algorithm.
Exact algorithms for fixed recursive functions
The same construction applies to every family obtained by recursively composing a fixed total Boolean gadget. We first state the resulting comparison with randomized query complexity. The proof will identify the exact exponential growth rate of the quantum algorithm, and then use known randomized lower bounds to control that rate and its overhead.
Theorem 6.1 (Exact quantum upper bounds in terms of randomized complexity). Fix a total Boolean function h : { 0 , 1 } r → { 0 , 1 } h:\{0,1\}^r\to\{0,1\} h : { 0 , 1 } r → { 0 , 1 } that depends on at least two variables. Set
F k = h k , δ = deg ( h ) , A = Adv ± ( h ) , F_k=h^k,\qquad\delta=\deg(h),\qquad A=\operatorname{Adv}^{\pm}(h), F k = h k , δ = deg ( h ) , A = Adv ± ( h ) , and define
p h = { log ( r / δ ) log ( δ / A ) , δ > A , 0 , δ ≤ A . (50) p_h=
\begin{cases}
\frac{\log(r/\delta)}{\log(\delta/A)}, & \delta>A,\\
0, & \delta\le A.
\end{cases} \tag*{(50)} p h = { l o g ( δ / A ) l o g ( r / δ ) , 0 , δ > A , δ ≤ A . (50) Then there is a constant C h > 0 C_h>0 C h > 0 , independent of k k k , such that
Q E ( F k ) ≤ C h R ( F k ) 2 ( k + 1 ) p h ( k ≥ 1 ) . (51) Q_E(F_k)\le C_hR(F_k)^2(k+1)^{p_h}\qquad(k\ge1). \tag*{(51)} Q E ( F k ) ≤ C h R ( F k ) 2 ( k + 1 ) p h ( k ≥ 1 ) . (51)
In particular,
Q E ( F k ) = O h ( R ( F k ) 2 [ log ( R ( F k ) + 2 ) ] p h ) , Q E ( F k ) ≤ R ( F k ) 2 + o h ( 1 ) (52) Q_E(F_k)=O_h\left(R(F_k)^2[\log(R(F_k)+2)]^{p_h}\right),\qquad Q_E(F_k)\le R(F_k)^{2+o_h(1)} \tag*{(52)} Q E ( F k ) = O h ( R ( F k ) 2 [ log ( R ( F k ) + 2 ) ] p h ) , Q E ( F k ) ≤ R ( F k ) 2 + o h ( 1 ) (52)
where the last bound is as k → ∞ k\to\infty k → ∞ . If δ < A 2 \delta<A^2 δ < A 2 or δ = r \delta=r δ = r , the stronger bound Q E ( F k ) = O h ( R ( F k ) 2 ) Q_E(F_k)=O_h(R(F_k)^2) Q E ( F k ) = O h ( R ( F k ) 2 ) holds without a logarithmic factor.
The gadget is fixed throughout this statement. In particular, the constant C h C_h C h and the logarithmic exponent p h p_h p h may depend on h h h . The result does not assert a universal quadratic bound for individual Boolean functions.
The exact recursive rate
Let h : { 0 , 1 } r → { 0 , 1 } h:\{0,1\}^r\to\{0,1\} h : { 0 , 1 } r → { 0 , 1 } be a fixed nonconstant Boolean function, and let H 0 ( x ) = x H_0(x)=x H 0 ( x ) = x and H d = h ∘ d H_d=h^{\circ d} H d = h ∘ d . Write
T d = Q E ( H d ) , δ = deg ( h ) , A = Adv ± ( h ) , M = max { δ , A } . T_d=Q_E(H_d),\qquad\delta=\deg(h),\qquad A=\operatorname{Adv}^{\pm}(h),\qquad M=\max\{\delta,A\}. T d = Q E ( H d ) , δ = deg ( h ) , A = Adv ± ( h ) , M = max { δ , A } .
Degree composition forces a lower bound of order δ d \delta^d δ d , and adversary composition forces one of order A d A^d A d . The next theorem shows that the larger of these two bases also suffices for an exact algorithm, up to a subexponential factor in the depth. All implicit constants in its quantitative bounds may depend on h h h .
Theorem 6.2. For every fixed nonconstant Boolean function h h h ,
Q E lim ( h ) : = lim d → ∞ Q E ( h ∘ d ) 1 / d = max { deg ( h ) , Adv ± ( h ) } . (53) Q_E^{\lim}(h):=\lim_{d\to\infty}Q_E(h^{\circ d})^{1/d}=\max\{\deg(h),\operatorname{Adv}^{\pm}(h)\}. \tag*{(53)} Q E l i m ( h ) := d → ∞ lim Q E ( h ∘ d ) 1/ d = max { deg ( h ) , Adv ± ( h )} . (53) More precisely, the following bounds hold:
If δ < A < r \delta<A<r δ < A < r , then
Ω ( A d ) ≤ T d ≤ A d exp ( O ( ( log ( d + 2 ) ) 2 ) ) . \Omega(A^d)\le T_d\le A^d\exp\left(O((\log(d+2))^2)\right). Ω ( A d ) ≤ T d ≤ A d exp ( O (( log ( d + 2 ) ) 2 ) ) . If A < δ A<\delta A < δ , then
1 2 δ d ≤ T d ≤ O ( δ d ( d + 1 ) p ) , p = log ( r / δ ) log ( δ / A ) . \frac{1}{2}\delta^d\le T_d\le O\left(\delta^d(d+1)^p\right),\qquad p=\frac{\log(r/\delta)}{\log(\delta/A)}. 2 1 δ d ≤ T d ≤ O ( δ d ( d + 1 ) p ) , p = log ( δ / A ) log ( r / δ ) . If δ = A < r \delta=A<r δ = A < r , then
1 2 δ d ≤ T d ≤ δ d exp ( O ( d log ( d + 2 ) ) ) . \frac{1}{2}\delta^d\le T_d\le\delta^d\exp\left(O\left(\sqrt{d\log(d+2)}\right)\right). 2 1 δ d ≤ T d ≤ δ d exp ( O ( d log ( d + 2 ) ) ) . If M = r M=r M = r , then T d = Θ ( r d ) T_d=\Theta(r^d) T d = Θ ( r d ) .
Proof. We derive one recurrence and choose its depth split differently in the three nontrivial parameter regimes.
Lower bounds and the common recurrence. The standard composition theorems give deg ( H d ) = δ d \deg(H_d)=\delta^d deg ( H d ) = δ d and Adv ± ( H d ) = A d \operatorname{Adv}^{\pm}(H_d)=A^d Adv ± ( H d ) = A d . The polynomial method and adversary characterization therefore imply
T d ≥ 1 2 δ d , T d = Ω ( A d ) , T d = Ω ( M d ) . (54) T_d\ge\frac{1}{2}\delta^d,\qquad T_d=\Omega(A^d),\qquad T_d=\Omega(M^d). \tag*{(54)} T d ≥ 2 1 δ d , T d = Ω ( A d ) , T d = Ω ( M d ) . (54)
For the upper bound, write d = k + ℓ d=k+\ell d = k + ℓ , with 1 ≤ k < d 1\le k<d 1 ≤ k < d , and view H d H_d H d as H k ∘ H ℓ H_k\circ H_\ell H k ∘ H ℓ . Its outer degree is δ k \delta^k δ k ; each inner block contains r ℓ r^\ell r ℓ input bits and has bounded-error query complexity Θ ( A ℓ ) \Theta(A^\ell) Θ ( A ℓ ) . Standard error reduction to 1 / ( 4 δ k ) 1/(4\delta^k) 1/ ( 4 δ k ) uses O h ( k A ℓ ) O_h(kA^\ell) O h ( k A ℓ ) queries. Thus Theorem 4.1 gives
T d ≤ C ( δ k r d − k + k T k A d − k ) . (55) T_d\le C\left(\delta^k r^{d-k}+kT_kA^{d-k}\right). \tag*{(55)} T d ≤ C ( δ k r d − k + k T k A d − k ) . (55)
for a constant C ≥ 1 C \ge1 C ≥ 1 depending only on h h h . The first term is the exact correction cost; the second uses the recursively constructed exact outer algorithm. At any fixed set of initial depths, we may instead read all input bits.
Adversary-dominated growth: δ < A < r \delta< A < r δ < A < r . Here the desired exponential base is A A A . As in the NAE construction, we choose the split so that the correction term is at most A d A^d A d :
β h = log ( r / A ) log ( r / δ ) ∈ ( 0 , 1 ) , k = ⌈ β h d ⌉ . \beta_h = \frac{\log(r/A)}{\log(r/\delta)} \in(0,1), \qquad k = \lceil\beta_h d \rceil. β h = log ( r / δ ) log ( r / A ) ∈ ( 0 , 1 ) , k = ⌈ β h d ⌉ .
For all sufficiently large d d d , this is a valid split, and
δ k r d − k A d = exp ( d log ( r / A ) − k log ( r / δ ) ) ≤ 1. \frac{\delta^k r^{d-k}}{A^d} = \exp\bigl(d\log(r/A)-k\log(r/\delta)\bigr) \le1. A d δ k r d − k = exp ( d log ( r / A ) − k log ( r / δ ) ) ≤ 1.
Writing u d = T d / A d u_d = T_d/A^d u d = T d / A d , we obtain u d ≤ C ( 1 + k u k ) u_d \le C(1 + ku_k) u d ≤ C ( 1 + k u k ) . This is precisely the normalized recurrence (49) , with β h \beta_h β h in place of β \beta β . The exact recursive depth decreases by a constant factor, so there are O h ( log ( d + 2 ) ) O_h(\log(d+2)) O h ( log ( d + 2 )) stages, each contributing at most a factor O h ( d + 1 ) O_h(d+1) O h ( d + 1 ) . The product of these factors is exp ( O h ( ( log ( d + 2 ) ) 2 ) ) \exp(O_h((\log(d+2))^2)) exp ( O h (( log ( d + 2 ) ) 2 )) , proving the first upper bound.
Degree-dominated growth: A < δ A < \delta A < δ . If δ = r \delta= r δ = r , reading all input bits gives T d ≤ δ d T_d \le\delta^d T d ≤ δ d , as required with p = 0 p = 0 p = 0 . Assume henceforth that δ < r \delta< r δ < r . Normalize by the degree term, writing u d = T d / δ d u_d = T_d/\delta^d u d = T d / δ d . With ℓ = d − k \ell= d-k ℓ = d − k , the recurrence becomes
u d ≤ C ( r / δ ) ℓ + C ( d − ℓ ) ( A / δ ) ℓ u d − ℓ . u_d \le C(r/\delta)^\ell+ C(d-\ell)(A/\delta)^\ell u_{d-\ell}. u d ≤ C ( r / δ ) ℓ + C ( d − ℓ ) ( A / δ ) ℓ u d − ℓ .
The two terms now favor opposite choices of ℓ \ell ℓ . A large inner depth makes the correction expensive, but it decreases the coefficient of the recursive term because A / δ < 1 A/\delta< 1 A / δ < 1 . We choose the smallest order of depth that makes this coefficient at most 1 / 2 1/2 1/2 :
ℓ = ⌈ log ( 2 C d ) log ( δ / A ) ⌉ , k = d − ℓ . \ell= \left\lceil\frac{\log(2Cd)}{\log(\delta/A)} \right\rceil, \qquad k = d-\ell. ℓ = ⌈ log ( δ / A ) log ( 2 C d ) ⌉ , k = d − ℓ .
For sufficiently large d d d , this gives 1 ≤ k < d 1 \le k < d 1 ≤ k < d . Moreover,
C ( d − ℓ ) ( A / δ ) ℓ ≤ 1 2 , C ( r / δ ) ℓ ≤ C 2 ( d + 1 ) p , p = log ( r / δ ) log ( δ / A ) , C(d-\ell)(A/\delta)^\ell\le\frac{1}{2}, \qquad C(r/\delta)^\ell\le C_2(d+1)^p, \qquad p = \frac{\log(r/\delta)}{\log(\delta/A)}, C ( d − ℓ ) ( A / δ ) ℓ ≤ 2 1 , C ( r / δ ) ℓ ≤ C 2 ( d + 1 ) p , p = log ( δ / A ) log ( r / δ ) ,
where C 2 C_2 C 2 absorbs the ceiling and depends only on h h h . Therefore
u d ≤ C 2 ( d + 1 ) p + 1 2 u d − ℓ . u_d \le C_2(d+1)^p + \frac{1}{2}u_{d-\ell}. u d ≤ C 2 ( d + 1 ) p + 2 1 u d − ℓ .
This inequality closes a polynomial induction. Choose K ≥ 2 C 2 K \ge2C_2 K ≥ 2 C 2 large enough that u j ≤ K ( j + 1 ) p u_j \le K(j+1)^p u j ≤ K ( j + 1 ) p at every initial depth. Since p ≥ 0 p \ge0 p ≥ 0 , the induction hypothesis gives
u d ≤ C 2 ( d + 1 ) p + 1 2 K ( d − ℓ + 1 ) p ≤ K ( d + 1 ) p . u_d \le C_2(d+1)^p + \frac{1}{2}K(d-\ell+1)^p \le K(d+1)^p. u d ≤ C 2 ( d + 1 ) p + 2 1 K ( d − ℓ + 1 ) p ≤ K ( d + 1 ) p .
Multiplying by δ d \delta^d δ d proves the second bound.
Equal growth rates: δ = A < r \delta= A < r δ = A < r . The preceding contraction is unavailable when A = δ A = \delta A = δ . Set u d = T d / δ d u_d = T_d/\delta^d u d = T d / δ d and λ = log ( r / δ ) > 0 \lambda= \log(r/\delta) > 0 λ = log ( r / δ ) > 0 . Equation (55) now gives
u d ≤ C ( e λ ℓ + d u d − ℓ ) . (56) u_d \le C\left(e^{\lambda\ell} + d\,u_{d-\ell}\right). \tag*{(56)} u d ≤ C ( e λ ℓ + d u d − ℓ ) . (56)
We allow a larger overhead and prove that u d ≤ exp ( O h ( d log ( d + 2 ) ) ) u_d \le\exp(O_h(\sqrt{d}\log(d+2))) u d ≤ exp ( O h ( d log ( d + 2 ))) . The split must make the decrease in this proposed bound large enough to absorb the factor d d d , while keeping the correction term within the same bound.
For real u ≥ 2 u \ge2 u ≥ 2 , put Φ ( u ) = u log u \Phi(u)=\sqrt{u}\log u Φ ( u ) = u log u and choose ℓ = ⌈ Φ ( d ) ⌉ \ell=\lceil\Phi(d)\rceil ℓ = ⌈ Φ ( d )⌉ . At sufficiently large depths, ℓ ≤ d / 2 \ell\le d/2 ℓ ≤ d /2 , and throughout [ d − ℓ , d ] [d-\ell,d] [ d − ℓ , d ] we have
Φ ′ ( u ) = log u + 1 2 u log u ≥ 1 3 log d d . \Phi'(u)=\frac{\log u+1}{2\sqrt{u}\log u}\ge\frac{1}{3}\sqrt{\frac{\log d}{d}}. Φ ′ ( u ) = 2 u log u log u + 1 ≥ 3 1 d log d .
Integrating this bound over an interval of length ℓ \ell ℓ yields
Φ ( d ) − Φ ( d − ℓ ) ≥ 1 3 log d . (57) \Phi(d)-\Phi(d-\ell)\ge\frac{1}{3}\log d. \tag*{(57)} Φ ( d ) − Φ ( d − ℓ ) ≥ 3 1 log d . (57)
This logarithmic decrease is what pays for the factor d d d in the recursive term.
Fix K > max { λ , 6 } K>\max\{\lambda,6\} K > max { λ , 6 } . We will prove u d ≤ C 3 e K Φ ( d ) u_d\le C_3e^{K\Phi(d)} u d ≤ C 3 e K Φ ( d ) by induction, where C 3 ≥ 1 C_3\ge1 C 3 ≥ 1 covers the finitely many small depths. Assuming the bound at depth d − ℓ d-\ell d − ℓ , divide the two terms in (56) by C 3 e K Φ ( d ) C_3e^{K\Phi(d)} C 3 e K Φ ( d ) . The correction term is at most
C e λ e − ( K − λ ) Φ ( d ) , C e^\lambda e^{-(K-\lambda)\Phi(d)}, C e λ e − ( K − λ ) Φ ( d ) ,
because ℓ ≤ Φ ( d ) + 1 \ell\le\Phi(d)+1 ℓ ≤ Φ ( d ) + 1 . The recursive term is at most
C d e − K ( Φ ( d ) − Φ ( d − ℓ ) ) ≤ C d 1 − K / 3 . C d e^{-K(\Phi(d)-\Phi(d-\ell))}\le C d^{1-K/3}. C d e − K ( Φ ( d ) − Φ ( d − ℓ )) ≤ C d 1 − K /3 .
Both expressions tend to zero. Choose a fixed threshold beyond which each is at most 1 / 2 1/2 1/2 , and then choose C 3 C_3 C 3 to cover all smaller depths. The sum is at most one, completing the induction and the third upper bound.
Full input-length growth: M = r M=r M = r . Reading the r d r^d r d input bits gives T d ≤ r d T_d\le r^d T d ≤ r d , and (54) supplies the matching lower bound.
In every parameter regime, the resulting bounds have the form Ω ( M d ) ≤ T d ≤ M d exp ( o h ( d ) ) \Omega(M^d)\le T_d\le M^d\exp(o_h(d)) Ω ( M d ) ≤ T d ≤ M d exp ( o h ( d )) . Taking d d d th roots establishes both existence of the limit and the identity (53) . □ \square □
Comparison with randomized query complexity
We now compare the algorithm with randomized query complexity. Only the following known lower bounds on randomized algorithms are needed; no composition theorem for R R R is required.
Lemma 6.3. There is a universal constant c 0 > 0 c_0>0 c 0 > 0 such that every total Boolean function F F F satisfies
deg ( F ) ≤ 9 R ( F ) 2 , Adv ± ( F ) ≤ c 0 R ( F ) . (58) \deg(F)\le9R(F)^2,\qquad\operatorname{Adv}^{\pm}(F)\le c_0R(F). \tag*{(58)} deg ( F ) ≤ 9 R ( F ) 2 , Adv ± ( F ) ≤ c 0 R ( F ) . (58) Consequently, for nonconstant F F F , Q E lim ( F ) ≤ max { 9 , c 0 } R ( F ) 2 Q_E^{\lim}(F)\le\max\{9,c_0\}R(F)^2 Q E l i m ( F ) ≤ max { 9 , c 0 } R ( F ) 2 .
The degree bound is the standard consequence of Huang’s inequality deg ( F ) ≤ s ( F ) 2 \deg(F)\le s(F)^2 deg ( F ) ≤ s ( F ) 2 [17 ] and the randomized block-sensitivity lower bound bs ( F ) ≤ 3 R ( F ) \operatorname{bs}(F)\le3R(F) bs ( F ) ≤ 3 R ( F ) [21 ] . The adversary bound follows from its characterization of bounded-error quantum complexity and Q ( F ) ≤ R ( F ) Q(F)\le R(F) Q ( F ) ≤ R ( F ) [19 , 24 ] . The final assertion uses Theorem 6.2 .
Proof of Theorem 6.1. Write r k = R ( F k ) r_k=R(F_k) r k = R ( F k ) . Apply Lemma 6.3 to the entire depth-k k k function, whose degree and adversary bound compose exactly. This gives
δ k = deg ( F k ) ≤ 9 r k 2 , A k = Adv ± ( F k ) ≤ c 0 r k . (59) \delta^k=\deg(F_k)\le9r_k^2,\qquad A^k=\operatorname{Adv}^{\pm}(F_k)\le c_0r_k. \tag*{(59)} δ k = deg ( F k ) ≤ 9 r k 2 , A k = Adv ± ( F k ) ≤ c 0 r k . (59)
The first inequality controls the degree contribution to our algorithm; the second controls its adversary contribution.
Suppose first that δ > A \delta> A δ > A . By the second case of Theorem 6.2 ,
Q E ( F k ) ≤ K h δ k ( k + 1 ) p h ≤ 9 K h r k 2 ( k + 1 ) p h . Q_E(F_k) \le K_h\delta^k(k+1)^{p_h} \le9K_hr_k^2(k+1)^{p_h}. Q E ( F k ) ≤ K h δ k ( k + 1 ) p h ≤ 9 K h r k 2 ( k + 1 ) p h .
This proves (51) in the degree-dominated case. If δ = r \delta= r δ = r , then p h = 0 p_h = 0 p h = 0 , so the same argument already gives a bound without a logarithmic loss.
Now suppose that δ ≤ A \delta\le A δ ≤ A . The rate theorem gives
Q E ( F k ) ≤ A k exp ( o h ( k ) ) . Q_E(F_k) \le A^k\exp(o_h(k)). Q E ( F k ) ≤ A k exp ( o h ( k )) .
A total Boolean function of degree at most one depends on at most one variable. Our hypothesis therefore implies δ ≥ 2 \delta\ge2 δ ≥ 2 , and in this case A ≥ 2 A \ge2 A ≥ 2 . The extra factor A k A^k A k available in the target quadratic bound absorbs the entire subexponential overhead: there is a constant K h K_h K h such that exp ( o h ( k ) ) ≤ K h A k \exp(o_h(k)) \le K_hA^k exp ( o h ( k )) ≤ K h A k for every k ≥ 1 k \ge1 k ≥ 1 . Using the second inequality in (59) , we obtain
Q E ( F k ) ≤ K h A 2 k ≤ K h c 0 2 r k 2 . Q_E(F_k) \le K_hA^{2k} \le K_hc_0^2r_k^2. Q E ( F k ) ≤ K h A 2 k ≤ K h c 0 2 r k 2 .
This includes the boundary case δ = A \delta= A δ = A : even its overhead exp ( O h ( k log ( k + 2 ) ) ) \exp(O_h(\sqrt{k\log(k+2)})) exp ( O h ( k log ( k + 2 ) )) is smaller than A k A^k A k for all sufficiently large k k k .
For the additional conclusion when A < δ < A 2 A < \delta< A^2 A < δ < A 2 , use the same slack in the adversary lower bound. Here
δ k ( k + 1 ) p h = A 2 k ( δ / A 2 ) k ( k + 1 ) p h = O h ( A 2 k ) , \delta^k(k+1)^{p_h} = A^{2k}(\delta/A^2)^k(k+1)^{p_h} = O_h(A^{2k}), δ k ( k + 1 ) p h = A 2 k ( δ / A 2 ) k ( k + 1 ) p h = O h ( A 2 k ) ,
since the exponentially decreasing factor ( δ / A 2 ) k (\delta/A^2)^k ( δ / A 2 ) k absorbs the polynomial in k k k . Thus Q E ( F k ) = O h ( r k 2 ) Q_E(F_k) = O_h(r_k^2) Q E ( F k ) = O h ( r k 2 ) also holds in this range.
Finally, we convert the polynomial overhead in the depth into a polylogarithmic overhead in randomized complexity. Since δ ≥ 2 \delta\ge2 δ ≥ 2 , the first inequality in (59) implies
r k ≥ δ k / 2 / 3 , k + 1 = O h ( log ( r k + 2 ) ) . r_k \ge\delta^{k/2}/3,\qquad k+1 = O_h(\log(r_k+2)). r k ≥ δ k /2 /3 , k + 1 = O h ( log ( r k + 2 )) .
Substitution proves (52) . The exponent p h p_h p h is fixed, while r k r_k r k tends to infinity, so the logarithmic factor and the fixed multiplicative constant are r k o h ( 1 ) r_k^{o_h(1)} r k o h ( 1 ) .
If h h h is constant, its recursive powers are constant. If it depends on exactly one variable, every recursive power is a projection or a negated projection, and both query complexities are one. These cases satisfy the quadratic comparison directly.
Remark 6.4. Theorem 6.1 applies to the powers of a fixed gadget h h h . Its constants and logarithmic exponent may depend on h h h .
Transfer principles for exact-query lower bounds
The preceding algorithm identifies the exponential growth of exact query complexity under repeated composition. We now use that growth rate to characterize inequalities that hold for all total Boolean functions. The principle is simple: apply a proposed universal inequality to successive powers of one fixed function, and then take roots. The constant in the universal inequality disappears, leaving a numerical condition on the original function.
Recall from Theorem 6.2 that
Q E lim ( f ) = lim k → ∞ Q E ( f ∘ k ) 1 / k = max { deg ( f ) , Adv ± ( f ) } . (60) Q_E^{\lim}(f)=\lim_{k\to\infty}Q_E(f^{\circ k})^{1/k}=\max\{\deg(f),\operatorname{Adv}^{\pm}(f)\}. \tag*{(60)} Q E l i m ( f ) = k → ∞ lim Q E ( f ∘ k ) 1/ k = max { deg ( f ) , Adv ± ( f )} . (60)
For a constant function we set Q E lim ( f ) = 0 Q_E^{\lim}(f)=0 Q E l i m ( f ) = 0 . Two properties explain why this parameter is useful. First, the polynomial and adversary lower bounds [7 , 19 , 24 ] imply
Q E lim ( f ) ≤ 2 Q E ( f ) . (61) Q_E^{\lim}(f)\le2Q_E(f). \tag*{(61)} Q E l i m ( f ) ≤ 2 Q E ( f ) . (61)
Second, exact composition of degree and of the adversary bound gives
Q E lim ( f ∘ k ) = Q E lim ( f ) k . (62) Q_E^{\lim}(f^{\circ k})=Q_E^{\lim}(f)^k. \tag*{(62)} Q E l i m ( f ∘ k ) = Q E l i m ( f ) k . (62)
Thus Q E lim Q_E^{\lim} Q E l i m is bounded by a constant multiple of exact query complexity, but, unlike exact query complexity itself, it is exactly multiplicative under self-composition.
Theorem 7.1 (A criterion for universal exact-query bounds). Fix a real number α > 0 \alpha>0 α > 0 and a nonnegative complexity measure L L L on total Boolean functions. Assume that L L L vanishes on constant functions and that
L ( f ∘ k ) ≥ L ( f ) k for every total Boolean function f and every integer k ≥ 1. (63) L(f^{\circ k})\ge L(f)^k \qquad\text{for every total Boolean function }f\text{ and every integer }k\ge1. \tag*{(63)} L ( f ∘ k ) ≥ L ( f ) k for every total Boolean function f and every integer k ≥ 1. (63) Then the following assertions are equivalent.
There is a constant C > 0 C>0 C > 0 , depending at most on L L L and α \alpha α , such that every total Boolean function F F F satisfies
L ( F ) ≤ C Q E ( F ) α . (64) L(F)\le CQ_E(F)^\alpha. \tag*{(64)} L ( F ) ≤ C Q E ( F ) α . (64) In particular, C C C is independent of F F F and its number of variables.
Every total Boolean function f f f satisfies
L ( f ) ≤ Q E lim ( f ) α = max { deg ( f ) , Adv ± ( f ) } α . (65) L(f)\le Q_E^{\lim}(f)^\alpha=\max\{\deg(f),\operatorname{Adv}^{\pm}(f)\}^\alpha. \tag*{(65)} L ( f ) ≤ Q E l i m ( f ) α = max { deg ( f ) , Adv ± ( f ) } α . (65) Moreover, assertion 2 implies assertion 1 with C = 2 α C=2^\alpha C = 2 α .
The coefficient one in assertion 2 is essential. A strict violation by one finite function excludes every universal constant in assertion 1. The theorem therefore converts a question about an asymptotic exponent into a search for a finite witness.
Proof. Suppose first that assertion 1 holds, and fix a nonconstant function f f f . Apply the universal inequality to f ∘ k f^{\circ k} f ∘ k , rather than to f f f itself. By the assumed growth of L L L ,
L ( f ) k ≤ L ( f ∘ k ) ≤ C Q E ( f ∘ k ) α . L(f)^k\le L(f^{\circ k})\le CQ_E(f^{\circ k})^\alpha. L ( f ) k ≤ L ( f ∘ k ) ≤ C Q E ( f ∘ k ) α .
Taking k k k th roots gives
L ( f ) ≤ C 1 / k ( Q E ( f ∘ k ) 1 / k ) α . L(f)\le C^{1/k}\left(Q_E(f^{\circ k})^{1/k}\right)^\alpha. L ( f ) ≤ C 1/ k ( Q E ( f ∘ k ) 1/ k ) α .
Both f f f and C C C are fixed while k k k tends to infinity. The first factor on the right tends to one; the second tends to Q E lim ( f ) α Q_E^{\lim}(f)^\alpha Q E l i m ( f ) α by Theorem 6.2 . This proves assertion 2.
For the converse, no composition is needed. Apply assertion 2 directly to F F F and then use (61) :
L ( F ) ≤ Q E lim ( F ) α ≤ 2 α Q E ( F ) α . L(F)\le Q_E^{\lim}(F)^\alpha\le2^\alpha Q_E(F)^\alpha. L ( F ) ≤ Q E l i m ( F ) α ≤ 2 α Q E ( F ) α .
This is assertion 1 with the stated constant. Constant functions satisfy both assertions because L L L and Q E Q_E Q E vanish on them.
A strict violation L ( f ) > Q E lim ( f ) α L(f) > Q_E^{\lim}(f)^\alpha L ( f ) > Q E l i m ( f ) α supplies a separating family F k = f ∘ k F_k = f^{\circ k} F k = f ∘ k . In fact, for η = 1 2 log ( L ( f ) / Q E lim ( f ) α ) > 0 \eta= \frac{1}{2}\log\left(L(f)/Q_E^{\lim}(f)^\alpha\right) > 0 η = 2 1 log ( L ( f ) / Q E l i m ( f ) α ) > 0 and all sufficiently large k k k ,
L ( F k ) ≥ e η k Q E ( F k ) α . (66) L(F_k) \ge e^{\eta k}Q_E(F_k)^\alpha. \tag*{(66)} L ( F k ) ≥ e η k Q E ( F k ) α . (66)
This follows from L ( F k ) ≥ L ( f ) k L(F_k) \ge L(f)^k L ( F k ) ≥ L ( f ) k and Q E ( F k ) = Q E lim ( f ) k exp ( o f ( k ) ) Q_E(F_k) = Q_E^{\lim}(f)^k\exp(o_f(k)) Q E ( F k ) = Q E l i m ( f ) k exp ( o f ( k )) .
Fractional block sensitivity and normalization
For block sensitivity, the appropriate finite-function criterion uses fractional block sensitivity. We first recall the definitions and the composition facts needed for this passage; the latter are known results of Tal and Kulkarni–Tal [18 , 26 ] .
A nonempty set B B B of coordinates is sensitive at x x x if f ( x B ) ≠ f ( x ) f(x^B) \ne f(x) f ( x B ) = f ( x ) , where x B x^B x B is obtained by flipping the coordinates in B B B . Sensitivity s ( f , x ) s(f,x) s ( f , x ) counts sensitive singletons. Block sensitivity bs ( f , x ) \operatorname{bs}(f,x) bs ( f , x ) is the largest number of pairwise disjoint sensitive blocks. Fractional block sensitivity replaces disjointness by a packing constraint: sensitive blocks receive nonnegative weights, and the total weight using any one coordinate is at most one. Thus
fbs ( f , x ) = max { ∑ B sensitive at x w B : w B ≥ 0 , ∑ B ∋ i w B ≤ 1 for every i } . (67) \operatorname{fbs}(f,x) = \max\left\{\sum_{B\text{ sensitive at }x} w_B : w_B \ge0,\ \sum_{B\ni i} w_B \le1\text{ for every }i\right\}. \tag*{(67)} fbs ( f , x ) = max { B sensitive at x ∑ w B : w B ≥ 0 , B ∋ i ∑ w B ≤ 1 for every i } . (67)
The function measures are the maxima of their inputwise versions. For an n n n -bit function they satisfy
s ( f ) ≤ bs ( f ) ≤ fbs ( f ) ≤ n . (68) s(f) \le\operatorname{bs}(f) \le\operatorname{fbs}(f) \le n. \tag*{(68)} s ( f ) ≤ bs ( f ) ≤ fbs ( f ) ≤ n . (68)
We will use this chain to identify all three measures whenever a function is sensitive to every coordinate at one input.
To iterate a fractional packing at zero, the output at zero must also be zero: this ensures that the outer copy is evaluated at the same input at every level. The following is the iterated form of Tal’s normalized composition inequality [26 Claim 5.7(ii)] ; see also Kulkarni–Tal [18 Lemma 2.6(4)] .
Lemma 7.2 (Fractional composition at the zero input; Tal [26 ] ). Let h : { 0 , 1 } n → { 0 , 1 } h:\{0,1\}^n\to\{0,1\} h : { 0 , 1 } n → { 0 , 1 } satisfy h ( 0 n ) = 0 h(0^n)=0 h ( 0 n ) = 0 , and put q = fbs ( h , 0 n ) q=\operatorname{fbs}(h,0^n) q = fbs ( h , 0 n ) . Then, for every integer k ≥ 1 k\ge1 k ≥ 1 ,
fbs ( h ∘ k , 0 n k ) ≥ q k . \operatorname{fbs}(h^{\circ k},0^{n^k}) \ge q^k. fbs ( h ∘ k , 0 n k ) ≥ q k .
Theorem 7.3 (A fractional criterion for universal block-sensitivity bounds). Fix α > 0 \alpha>0 α > 0 . A universal constant C > 0 C>0 C > 0 satisfying bs ( F ) ≤ C Q E ( F ) α \operatorname{bs}(F)\le C Q_E(F)^\alpha bs ( F ) ≤ C Q E ( F ) α for every total Boolean function F F F exists if and only if every total Boolean function f f f satisfies fbs ( f ) ≤ Q E lim ( f ) α \operatorname{fbs}(f)\le Q_E^{\lim}(f)^\alpha fbs ( f ) ≤ Q E l i m ( f ) α . Equivalently,
bs ( F ) = O ( Q E ( F ) α ) for every F \operatorname{bs}(F)=O(Q_E(F)^\alpha)\quad\text{for every }F bs ( F ) = O ( Q E ( F ) α ) for every F fbs ( f ) ≤ max { deg ( f ) , Adv ± ( f ) } α for every f . (69) \operatorname{fbs}(f)\le\max\{\operatorname{deg}(f),\operatorname{Adv}^{\pm}(f)\}^\alpha\quad\text{for every }f. \tag*{(69)} fbs ( f ) ≤ max { deg ( f ) , Adv ± ( f ) } α for every f . (69)
Proof. Assume the universal bound on bs \operatorname{bs} bs . Fix a nonconstant n n n -bit function f f f . We will normalize an input attaining fbs ( f ) \operatorname{fbs}(f) fbs ( f ) , compose at that input, and then use the known comparison of fractional and ordinary block sensitivity along recursive powers.
Normalize the maximizing input. Choose x ⋆ x^\star x ⋆ such that fbs ( f , x ⋆ ) = fbs ( f ) \operatorname{fbs}(f,x^\star)=\operatorname{fbs}(f) fbs ( f , x ⋆ ) = fbs ( f ) , and define
h ( z ) = f ( z ⊕ x ⋆ ) ⊕ f ( x ⋆ ) . h(z)=f(z\oplus x^\star)\oplus f(x^\star). h ( z ) = f ( z ⊕ x ⋆ ) ⊕ f ( x ⋆ ) .
Input complementation moves x ⋆ x^\star x ⋆ to zero, and output complementation makes the value there zero. These operations preserve degree, the adversary bound, and the sensitive-block structure. Consequently,
h ( 0 ) = 0 , fbs ( h , 0 ) = fbs ( f ) , Q E lim ( h ) = Q E lim ( f ) . h(0)=0,\qquad\operatorname{fbs}(h,0)=\operatorname{fbs}(f),\qquad Q^{\lim}_{E}(h)=Q^{\lim}_{E}(f). h ( 0 ) = 0 , fbs ( h , 0 ) = fbs ( f ) , Q E l i m ( h ) = Q E l i m ( f ) .
Lemma 7.2 gives fbs ( h ∘ k ) ≥ fbs ( f ) k \operatorname{fbs}(h^{\circ k})\ge\operatorname{fbs}(f)^k fbs ( h ∘ k ) ≥ fbs ( f ) k .
Pass from fractional to ordinary block sensitivity. Tal [26 ] , Claim 5.10 proved that the two measures differ by at most a constant along powers of a fixed function. In the form recorded by Kulkarni–Tal [18 ] , Claim 2.7, this says
fbs ( h ∘ k ) ≤ c ( n ) bs ( h ∘ k ) , (70) \operatorname{fbs}(h^{\circ k})\le c(n)\operatorname{bs}(h^{\circ k}), \tag*{(70)} fbs ( h ∘ k ) ≤ c ( n ) bs ( h ∘ k ) , (70)
where c ( n ) c(n) c ( n ) depends only on the arity n n n of the base function and is independent of k k k . Combining this known result with the assumed universal bound yields
fbs ( f ) k ≤ c ( n ) bs ( h ∘ k ) ≤ c ( n ) C Q E ( h ∘ k ) α . \operatorname{fbs}(f)^k\le c(n)\operatorname{bs}(h^{\circ k})\le c(n)C Q_E(h^{\circ k})^\alpha. fbs ( f ) k ≤ c ( n ) bs ( h ∘ k ) ≤ c ( n ) C Q E ( h ∘ k ) α .
Now take k k k th roots and let k k k tend to infinity. Since the base function is fixed, ( c ( n ) C ) 1 / k (c(n)C)^{1/k} ( c ( n ) C ) 1/ k tends to one, and the recursive-rate theorem gives fbs ( f ) ≤ Q E lim ( h ) α = Q E lim ( f ) α \operatorname{fbs}(f)\le Q^{\lim}_{E}(h)^\alpha=Q^{\lim}_{E}(f)^\alpha fbs ( f ) ≤ Q E l i m ( h ) α = Q E l i m ( f ) α .
Conversely, the pointwise fractional bound immediately implies
bs ( f ) ≤ fbs ( f ) ≤ Q E lim ( f ) α ≤ 2 α Q E ( f ) α . \operatorname{bs}(f)\le\operatorname{fbs}(f)\le Q^{\lim}_{E}(f)^\alpha\le2^\alpha Q_E(f)^\alpha. bs ( f ) ≤ fbs ( f ) ≤ Q E l i m ( f ) α ≤ 2 α Q E ( f ) α .
Constant functions cause no exception. This is the normalization and root argument of Kulkarni–Tal [18 ] , Lemma 3.1, applied here with our exact recursive rate.
Corollary 7.4 (The same universal exponent for three sensitivity measures). For each α > 0 \alpha>0 α > 0 , the following four statements are equivalent:
s ( F ) = O ( Q E ( F ) α ) s(F)=O(Q_E(F)^\alpha) s ( F ) = O ( Q E ( F ) α ) for every total Boolean function F F F ;
bs ( F ) = O ( Q E ( F ) α ) \operatorname{bs}(F)=O(Q_E(F)^\alpha) bs ( F ) = O ( Q E ( F ) α ) for every total Boolean function F F F ;
fbs ( F ) = O ( Q E ( F ) α ) \operatorname{fbs}(F)=O(Q_E(F)^\alpha) fbs ( F ) = O ( Q E ( F ) α ) for every total Boolean function F F F ;
fbs ( f ) ≤ max { deg ( f ) , Adv ± ( f ) } α \operatorname{fbs}(f)\le\max\{\deg(f),\operatorname{Adv}^{\pm}(f)\}^\alpha fbs ( f ) ≤ max { deg ( f ) , Adv ± ( f ) } α for every total Boolean function f f f .
Each implicit constant is independent of the function and its arity.
Proof. Theorem 7.3 , equation (61) , and the chain s ≤ bs ≤ fbs s\le\operatorname{bs}\le\operatorname{fbs} s ≤ bs ≤ fbs give all implications except 1 ⇒ 2 1\Rightarrow2 1 ⇒ 2 . For this remaining implication, suppose that s ( H ) ≤ C Q E ( H ) α s(H)\le C Q_E(H)^\alpha s ( H ) ≤ C Q E ( H ) α holds for every total Boolean function H H H .
Fix F F F , and choose an input x x x with disjoint sensitive blocks B 1 , … , B t B_1,\ldots,B_t B 1 , … , B t , where t = bs ( F ) t=\operatorname{bs}(F) t = bs ( F ) . Identify each block with a new variable, defining
H ( y ) = F ( x ⋃ j : y j = 1 B j ) . H(y)=F\left(x^{\bigcup_{j:y_j=1}B_j}\right). H ( y ) = F ( x ⋃ j : y j = 1 B j ) .
Every one of the t t t variables is sensitive at zero, so s ( H ) = t s(H)=t s ( H ) = t . Moreover, each input bit of F F F becomes a constant, a variable of H H H , or its complement. The standard query simulation for such substitutions therefore gives Q E ( H ) ≤ Q E ( F ) Q_E(H)\le Q_E(F) Q E ( H ) ≤ Q E ( F ) , also for queries in superposition. Applying the assumed sensitivity bound to H H H now yields
bs ( F ) = s ( H ) ≤ C Q E ( H ) α ≤ C Q E ( F ) α . \operatorname{bs}(F)=s(H)\le C Q_E(H)^\alpha\le C Q_E(F)^\alpha. bs ( F ) = s ( H ) ≤ C Q E ( H ) α ≤ C Q E ( F ) α .
This proves 1 ⇒ 2 1\Rightarrow2 1 ⇒ 2 and completes the equivalence.
A 3/2 separation between sensitivity and exact quantum queries
We apply the transfer principle to construct total functions G k G_k G k on N k N_k N k variables for which
s ( G k ) = bs ( G k ) = fbs ( G k ) = N k , Q E ( G k ) = N k 2 / 3 + o ( 1 ) . s(G_k)=\operatorname{bs}(G_k)=\operatorname{fbs}(G_k)=N_k,\qquad Q_E(G_k)=N_k^{2/3+o(1)}. s ( G k ) = bs ( G k ) = fbs ( G k ) = N k , Q E ( G k ) = N k 2/3 + o ( 1 ) .
Theorem 8.1 quantifies the loss in the exponent-3/2 lower bound. This improves the exponent 8 log 2 ( 3 ) / 11 = 1.152700 … 8\log_2(3)/11=1.152700\ldots 8 log 2 ( 3 ) /11 = 1.152700 … supplied by Ambainis’s STOC 2013 algorithm for recursive NAE [3 , 4 ] . That algorithm uses O ( 2048 k / 8 ) = O ( 2 11 k / 8 ) O(2048^{k/8})=O(2^{11k/8}) O ( 204 8 k /8 ) = O ( 2 11 k /8 ) queries on 3 k 3^k 3 k variables, all sensitive at zero.
There are two steps in the construction. Recursive NAE supplies full sensitivity and a small exact-query rate, but its degree is smaller than its adversary bound. An additional OR layer brings these two parameters into balance: an OR on m m m bits multiplies degree by m m m and the adversary bound by m \sqrt{m} m . Choosing m m m at the balancing point improves the separation exponent to 3 / 2 3/2 3/2 . We first use the resulting functions as finite witnesses for the transfer theorem, and then give a direct quantitative bound for the same family.
Full sensitivity of recursive NAE
Let F k = NAE 3 ∘ k F_k=\operatorname{NAE}_3^{\circ k} F k = NAE 3 ∘ k and a = 3 / 2 a=3/\sqrt{2} a = 3/ 2 . § 5 gives
deg ( F k ) = 2 k , Adv ± ( F k ) = a k , Ω ( a k ) ≤ Q E ( F k ) ≤ a k exp ( O ( ( log ( k + 2 ) ) 2 ) ) . (71) \deg(F_k)=2^k,\qquad\operatorname{Adv}^{\pm}(F_k)=a^k,\qquad\Omega(a^k)\leq Q_E(F_k)\leq a^k\exp\left(O\left((\log(k+2))^2\right)\right). \tag*{(71)} deg ( F k ) = 2 k , Adv ± ( F k ) = a k , Ω ( a k ) ≤ Q E ( F k ) ≤ a k exp ( O ( ( log ( k + 2 ) ) 2 ) ) . (71)
Recursive NAE is fully sensitive at zero, a property already used by Ambainis [4 Section 3.1] . The standard sensitivity, certificate, and decision-tree inequalities therefore give
s ( F k ) = bs ( F k ) = fbs ( F k ) = 3 k , (72) s(F_k)=\operatorname{bs}(F_k)=\operatorname{fbs}(F_k)=3^k, \tag*{(72)} s ( F k ) = bs ( F k ) = fbs ( F k ) = 3 k , (72)
C ( F k ) = D ( F k ) = 3 k . (73) C(F_k)=D(F_k)=3^k. \tag*{(73)} C ( F k ) = D ( F k ) = 3 k . (73)
Write L = { s , bs , fbs , C , D } \mathcal{L}=\{s,\operatorname{bs},\operatorname{fbs},C,D\} L = { s , bs , fbs , C , D } and ρ N A E = log 3 / log ( 3 / 2 ) = 1.4608454206 … \rho_{\mathrm{NAE}}=\log3/\log(3/\sqrt{2})=1.4608454206\ldots ρ NAE = log 3/ log ( 3/ 2 ) = 1.4608454206 … . Since 3 = a ρ N A E 3=a^{\rho_{\mathrm{NAE}}} 3 = a ρ NAE , (71) gives
Q E ( F k ) ρ N A E exp ( O ( ( log log ( Q E ( F k ) + 3 ) ) 2 ) ) ≤ L ( F k ) ≤ O ( Q E ( F k ) ρ N A E ) ( L ∈ L ) . (74) \frac{Q_E(F_k)^{\rho_{\mathrm{NAE}}}}{\exp\left(O\left((\log\log(Q_E(F_k)+3))^2\right)\right)}
\leq L(F_k)\leq O\left(Q_E(F_k)^{\rho_{\mathrm{NAE}}}\right)
\qquad(L\in\mathcal{L}). \tag*{(74)} exp ( O ( ( log log ( Q E ( F k ) + 3 ) ) 2 ) ) Q E ( F k ) ρ NAE ≤ L ( F k ) ≤ O ( Q E ( F k ) ρ NAE ) ( L ∈ L ) . (74)
The lower bound implies L ( F k ) ≥ Q E ( F k ) α L(F_k)\geq Q_E(F_k)^\alpha L ( F k ) ≥ Q E ( F k ) α for each fixed α < ρ N A E \alpha<\rho_{\mathrm{NAE}} α < ρ NAE and sufficiently large k k k . For the sensitivity measures, the three-bit witness fbs ( NAE 3 ) = 3 > Q E lim ( NAE 3 ) α \operatorname{fbs}(\operatorname{NAE}_3)=3>Q_E^{\lim}(\operatorname{NAE}_3)^\alpha fbs ( NAE 3 ) = 3 > Q E l i m ( NAE 3 ) α also gives this conclusion through Corollary 7.4 . In fact, the same quantitative bound gives
lim k → ∞ L ( F k ) Q E ( F k ) α = ∞ ( α < ρ N A E , L ∈ L ) , \lim_{k\to\infty}\frac{L(F_k)}{Q_E(F_k)^\alpha}=\infty
\qquad(\alpha<\rho_{\mathrm{NAE}},\ L\in\mathcal{L}), k → ∞ lim Q E ( F k ) α L ( F k ) = ∞ ( α < ρ NAE , L ∈ L ) ,
since Q E ( F k ) Q_E(F_k) Q E ( F k ) tends to infinity and the loss in (74) is subpolynomial in Q E ( F k ) Q_E(F_k) Q E ( F k ) .
A finite witness for the transfer principle
Consider F k ∘ OR m F_k\circ\operatorname{OR}_m F k ∘ OR m . Degree and adversary composition give
deg ( F k ∘ OR m ) = 2 k m , Adv ± ( F k ∘ OR m ) = a k m . \deg(F_k\circ\operatorname{OR}_m)=2^k m,\qquad\operatorname{Adv}^{\pm}(F_k\circ\operatorname{OR}_m)=a^k\sqrt{m}. deg ( F k ∘ OR m ) = 2 k m , Adv ± ( F k ∘ OR m ) = a k m .
To minimize their maximum relative to the number 3 k m 3^k m 3 k m of sensitive variables, we balance the two expressions. Solving 2 k m = a k m 2^k m=a^k\sqrt{m} 2 k m = a k m gives m = ( a / 2 ) 2 k = ( 9 / 8 ) k m=(a/2)^{2k}=(9/8)^k m = ( a /2 ) 2 k = ( 9/8 ) k . Define
m k = ⌈ ( 9 / 8 ) k ⌉ , G k = F k ∘ OR m k , N k = 3 k m k . (75) m_k=\left\lceil(9/8)^k\right\rceil,\qquad G_k=F_k\circ\operatorname{OR}_{m_k},\qquad N_k=3^k m_k. \tag*{(75)} m k = ⌈ ( 9/8 ) k ⌉ , G k = F k ∘ OR m k , N k = 3 k m k . (75)
Rounding upward ensures that degree is at least the adversary bound. Consequently,
Q E lim ( G k ) = 2 k m k . Q^{\lim}_{E}(G_k)=2^k m_k. Q E l i m ( G k ) = 2 k m k .
Every raw input bit is sensitive at zero: flipping it changes its OR output, and F k F_k F k is sensitive to that changed outer bit. Hence s ( G k ) = bs ( G k ) = fbs ( G k ) = N k s(G_k)=\operatorname{bs}(G_k)=\operatorname{fbs}(G_k)=N_k s ( G k ) = bs ( G k ) = fbs ( G k ) = N k . Since N k = Θ ( ( 27 / 8 ) k ) N_k=\Theta((27/8)^k) N k = Θ (( 27/8 ) k ) and Q E lim ( G k ) = Θ ( ( 9 / 4 ) k ) Q^{\lim}_{E}(G_k)=\Theta((9/4)^k) Q E l i m ( G k ) = Θ (( 9/4 ) k ) , we have fbs ( G k ) = Θ ( ( Q E lim ( G k ) ) 3 / 2 ) \operatorname{fbs}(G_k)=\Theta((Q^{\lim}_{E}(G_k))^{3/2}) fbs ( G k ) = Θ (( Q E l i m ( G k ) ) 3/2 ) .
For any fixed α < 3 / 2 \alpha<3/2 α < 3/2 , choose an index k 0 k_0 k 0 large enough that g = G k 0 g=G_{k_0} g = G k 0 satisfies fbs ( g ) > Q E lim ( g ) α \operatorname{fbs}(g)>Q^{\lim}_{E}(g)^\alpha fbs ( g ) > Q E l i m ( g ) α . Corollary 7.4 rules out a universal exponent-α \alpha α bound for s s s , bs \operatorname{bs} bs , or fbs \operatorname{fbs} fbs in terms of Q E Q_E Q E . Recursive powers of this fixed g g g supply a separating family.
The transfer theorem alone does not give a uniform quantitative bound for the changing sequence G k G_k G k , since its fixed-gadget constants may depend on k k k . For that purpose we apply the composition algorithm directly.
An explicit family attaining exponent $3/2`
Theorem 8.1 (Exponent-3 / 2 3/2 3/2 separation). Let G k G_k G k and N k N_k N k be as in (75) . For every L ∈ L = { s , bs , fbs , C , D } L\in\mathcal{L}=\{s,\operatorname{bs},\operatorname{fbs},C,D\} L ∈ L = { s , bs , fbs , C , D } ,
L ( G k ) = N k = Θ ( ( 27 / 8 ) k ) . (76) L(G_k)=N_k=\Theta((27/8)^k). \tag*{(76)} L ( G k ) = N k = Θ (( 27/8 ) k ) . (76) Moreover,
deg ( G k ) = Q E lim ( G k ) = 2 k m k = Θ ( ( 9 / 4 ) k ) , (77) \deg(G_k)=Q^{\lim}_{E}(G_k)=2^k m_k=\Theta((9/4)^k), \tag*{(77)} deg ( G k ) = Q E l i m ( G k ) = 2 k m k = Θ (( 9/4 ) k ) , (77) 1 2 ( 9 / 4 ) k ≤ Q E ( G k ) ≤ ( 9 / 4 ) k exp ( O ( ( log ( k + 2 ) ) 2 ) ) . (78) \frac{1}{2}(9/4)^k\leq Q_E(G_k)\leq(9/4)^k\exp\left(O((\log(k+2))^2)\right). \tag*{(78)} 2 1 ( 9/4 ) k ≤ Q E ( G k ) ≤ ( 9/4 ) k exp ( O (( log ( k + 2 ) ) 2 ) ) . (78) Writing q k = Q E ( G k ) q_k=Q_E(G_k) q k = Q E ( G k ) , we have
q k 3 / 2 exp ( O ( ( log log ( q k + 3 ) ) 2 ) ) ≤ L ( G k ) ≤ O ( q k 3 / 2 ) ( L ∈ L ) . (79) \frac{q_k^{3/2}}{\exp\left(O((\log\log(q_k+3))^2)\right)}\leq L(G_k)\leq O(q_k^{3/2})\qquad(L\in\mathcal{L}). \tag*{(79)} exp ( O (( log log ( q k + 3 ) ) 2 ) ) q k 3/2 ≤ L ( G k ) ≤ O ( q k 3/2 ) ( L ∈ L ) . (79) In particular, for each fixed α < 3 / 2 \alpha<3/2 α < 3/2 and all sufficiently large k k k ,
L ( G k ) ≥ q k α ( L ∈ L ) . (80) L(G_k)\geq q_k^\alpha\qquad(L\in\mathcal{L}). \tag*{(80)} L ( G k ) ≥ q k α ( L ∈ L ) . (80) More precisely, the same family satisfies
lim k → ∞ L ( G k ) q k α = ∞ ( α < 3 / 2 , L ∈ L ) . \lim_{k\to\infty}\frac{L(G_k)}{q_k^\alpha}=\infty\qquad(\alpha<3/2,\ L\in\mathcal{L}). k → ∞ lim q k α L ( G k ) = ∞ ( α < 3/2 , L ∈ L ) . Proof. Sensitivity and the exact-query lower bound. The full sensitivity at zero proved above gives s ( G k ) = bs ( G k ) = fbs ( G k ) = N k s(G_k)=\operatorname{bs}(G_k)=\operatorname{fbs}(G_k)=N_k s ( G k ) = bs ( G k ) = fbs ( G k ) = N k . The inequalities s ≤ C ≤ D ≤ N k s\leq C\leq D\leq N_k s ≤ C ≤ D ≤ N k give the two remaining equalities in (76) . Also,
deg ( G k ) = 2 k m k , Adv ± ( G k ) = a k m k . \deg(G_k)=2^k m_k,\qquad\operatorname{Adv}^{\pm}(G_k)=a^k\sqrt{m_k}. deg ( G k ) = 2 k m k , Adv ± ( G k ) = a k m k . Our choice m k ≥ ( a / 2 ) 2 k m_k\geq(a/2)2^k m k ≥ ( a /2 ) 2 k makes the first quantity larger, so Q E lim ( G k ) = 2 k m k Q^{\lim}_{E}(G_k)=2^k m_k Q E l i m ( G k ) = 2 k m k . Since m k = Θ ( ( 9 / 8 ) k ) m_k=\Theta((9/8)^k) m k = Θ (( 9/8 ) k ) , this proves (77) . The polynomial method gives
Q E ( G k ) ≥ 1 2 deg ( G k ) ≥ 1 2 ( 9 / 4 ) k . Q_E(G_k)\geq\frac{1}{2}\deg(G_k)\geq\frac{1}{2}(9/4)^k. Q E ( G k ) ≥ 2 1 deg ( G k ) ≥ 2 1 ( 9/4 ) k .
An exact algorithm at the balanced rate. Apply Theorem 4.1 to the outer function F k F_k F k and the inner function O R m k \mathrm{OR}_{m_k} OR m k . The required inner error is 1 / ( 4 deg ( F k ) ) = 1 / ( 4 ⋅ 2 k ) 1/(4\deg(F_k))=1/(4\cdot2^k) 1/ ( 4 deg ( F k )) = 1/ ( 4 ⋅ 2 k ) . Quantum search and standard error reduction [9 , 11 ] give
Q 1 / ( 4 ⋅ 2 k ) ( O R m k ) = O ( ( k + 1 ) m k ) . Q_{1/(4\cdot2^k)}(\mathrm{OR}_{m_k})=O((k+1)\sqrt{m_k}). Q 1/ ( 4 ⋅ 2 k ) ( OR m k ) = O (( k + 1 ) m k ) .
The composition bound and (71) now imply
Q E ( G k ) ≤ O ( 2 k m k + ( k + 1 ) m k Q E ( F k ) ) ≤ O ( 2 k m k + ( k + 1 ) a k m k exp ( O ( ( log ( k + 2 ) ) 2 ) ) ) . \begin{aligned}
Q_E(G_k)\leq O\left(2^k m_k+(k+1)\sqrt{m_k}Q_E(F_k)\right) \\
&\leq O\left(2^k m_k+(k+1)a^k\sqrt{m_k}\exp\left(O((\log(k+2))^2)\right)\right).
\end{aligned} Q E ( G k ) ≤ O ( 2 k m k + ( k + 1 ) m k Q E ( F k ) ) ≤ O ( 2 k m k + ( k + 1 ) a k m k exp ( O (( log ( k + 2 ) ) 2 ) ) ) .
The balancing choice has made both principal costs equal at the exponential scale:
2 k m k = Θ ( ( 9 / 4 ) k ) , a k m k = Θ ( ( 9 / 4 ) k ) . 2^k m_k=\Theta\left((9/4)^k\right),\qquad a^k\sqrt{m_k}=\Theta\left((9/4)^k\right). 2 k m k = Θ ( ( 9/4 ) k ) , a k m k = Θ ( ( 9/4 ) k ) .
Absorbing the factor k + 1 k+1 k + 1 into the stated overhead proves the upper bound in (78) .
The separation bound. The identity 27 / 8 = ( 9 / 4 ) 3 / 2 27/8=(9/4)^{3/2} 27/8 = ( 9/4 ) 3/2 and (78) give
( 9 / 4 ) k = Θ ( L ( G k ) 2 / 3 ) , q k ≤ O ( L ( G k ) 2 / 3 ) exp ( O ( ( log ( k + 2 ) ) 2 ) ) . (9/4)^k=\Theta\left(L(G_k)^{2/3}\right),\qquad q_k\leq O\left(L(G_k)^{2/3}\right)\exp\left(O((\log(k+2))^2)\right). ( 9/4 ) k = Θ ( L ( G k ) 2/3 ) , q k ≤ O ( L ( G k ) 2/3 ) exp ( O (( log ( k + 2 ) ) 2 ) ) .
Also log ( q k + 3 ) = Θ ( k + 1 ) \log(q_k+3)=\Theta(k+1) log ( q k + 3 ) = Θ ( k + 1 ) by (78) . Raising the upper bound to the power 3 / 2 3/2 3/2 and rearranging gives the lower bound in (79) . The lower bound on q k q_k q k in (78) gives the other direction. For every α < 3 / 2 \alpha<3/2 α < 3/2 , the factor q k 3 / 2 − α q_k^{3/2-\alpha} q k 3/2 − α eventually exceeds the denominator in (79) , giving (80) . Indeed, for each such α \alpha α ,
log ( L ( G k ) q k α ) ≥ ( 3 / 2 − α ) log q k − O ( ( log log ( q k + 3 ) ) 2 ) . \log\left(\frac{L(G_k)}{q_k^\alpha}\right)\geq(3/2-\alpha)\log q_k-O\left((\log\log(q_k+3))^2\right). log ( q k α L ( G k ) ) ≥ ( 3/2 − α ) log q k − O ( ( log log ( q k + 3 ) ) 2 ) .
Since q k q_k q k tends to infinity, the right-hand side tends to infinity. This proves the stated limit. □
The loss in (79) is ( log ( q k + 3 ) ) O ( log log ( q k + 3 ) ) (\log(q_k+3))^{O(\log\log(q_k+3))} ( log ( q k + 3 ) ) O ( l o g l o g ( q k + 3 )) . Obtaining a fixed power of a logarithm as the loss would require a sharper bound.
The family obtained by fixing a witness and then composing it can also be described explicitly. For g = G k 0 g=G_{k_0} g = G k 0 as above, we have g ( 0 ) = 0 g(0)=0 g ( 0 ) = 0 and full sensitivity at zero. Therefore
s ( g ∘ t ) = bs ( g ∘ t ) = fbs ( g ∘ t ) = N k 0 t , Q E ( g ∘ t ) = Q E lim ( g ) t exp ( o ( t ) ) . s(g^{\circ t})=\operatorname{bs}(g^{\circ t})=\operatorname{fbs}(g^{\circ t})=N_{k_0}^t,\qquad Q_E(g^{\circ t})=Q_E^{\lim}(g)^t\exp(o(t)). s ( g ∘ t ) = bs ( g ∘ t ) = fbs ( g ∘ t ) = N k 0 t , Q E ( g ∘ t ) = Q E l i m ( g ) t exp ( o ( t )) .
These powers certify every chosen exponent below 3 / 2 3/2 3/2 . For the fixed α \alpha α used to choose g g g , we have
lim t → ∞ L ( g ∘ t ) Q E ( g ∘ t ) α = ∞ ( L ∈ { s , bs , fbs } ) , \lim_{t\to\infty}\frac{L(g^{\circ t})}{Q_E(g^{\circ t})^\alpha}=\infty\qquad(L\in\{s,\operatorname{bs},\operatorname{fbs}\}), t → ∞ lim Q E ( g ∘ t ) α L ( g ∘ t ) = ∞ ( L ∈ { s , bs , fbs }) ,
because N k 0 / Q E lim ( g ) α > 1 N_{k_0}/Q_E^{\lim}(g)^\alpha>1 N k 0 / Q E l i m ( g ) α > 1 and the exact cost has only a subexponential overhead in t t t . Theorem 8.1 additionally controls the loss for the original family G k G_k G k , whose balancing parameter changes with k k k .
Corollary 8.2 (A composition counterexample from the same family). The functions in (75) satisfy
Q E ( F k ∘ O R m k ) ≤ Q ( F k ) Q E ( O R m k ) ( 2 2 3 ) k exp ( O ( ( log ( k + 2 ) ) 2 ) ) . (81) Q_E(F_k\circ\mathrm{OR}_{m_k})\leq Q(F_k)Q_E(\mathrm{OR}_{m_k})\left(\frac{2\sqrt{2}}{3}\right)^k\exp\left(O((\log(k+2))^2)\right). \tag*{(81)} Q E ( F k ∘ OR m k ) ≤ Q ( F k ) Q E ( OR m k ) ( 3 2 2 ) k exp ( O (( log ( k + 2 ) ) 2 ) ) . (81) Thus the multiplicative simulation cost exceeds Q E ( F k ∘ O R m k ) Q_E(F_k\circ\mathrm{OR}_{m_k}) Q E ( F k ∘ OR m k ) by a factor exp ( Ω ( k ) ) \exp(\Omega(k)) exp ( Ω ( k )) . In particular,
lim k → ∞ Q E ( F k ∘ O R m k ) Q E ( F k ) Q E ( O R m k ) = 0. \lim_{k\to\infty}\frac{Q_E(F_k\circ\mathrm{OR}_{m_k})}{Q_E(F_k)Q_E(\mathrm{OR}_{m_k})}=0. k → ∞ lim Q E ( F k ) Q E ( OR m k ) Q E ( F k ∘ OR m k ) = 0.
Proof. The standard bounds give Q ( F k ) = Θ ( a k ) Q(F_k)=\Theta(a^k) Q ( F k ) = Θ ( a k ) and Q E ( O R m k ) = Θ ( m k ) Q_E(\mathrm{OR}_{m_k})=\Theta(m_k) Q E ( OR m k ) = Θ ( m k ) [7 , 24 ] . Divide (78) by their product and use m k ≥ ( 9 / 8 ) k m_k\ge(9/8)^k m k ≥ ( 9/8 ) k . The ratio of the exponential factors is
( 9 / 4 ) k a k ( 9 / 8 ) k = ( 2 a ) k = ( 2 2 3 ) k . \frac{(9/4)^k}{a^k(9/8)^k}=\left(\frac{2}{a}\right)^k=\left(\frac{2\sqrt{2}}{3}\right)^k. a k ( 9/8 ) k ( 9/4 ) k = ( a 2 ) k = ( 3 2 2 ) k .
Its base is smaller than one, so the exponential decay dominates the exp ( O ( ( log ( k + 2 ) ) 2 ) ) \exp(O((\log(k+2))^2)) exp ( O (( log ( k + 2 ) ) 2 )) overhead. Finally, Q ( F k ) ≤ Q E ( F k ) Q(F_k)\le Q_E(F_k) Q ( F k ) ≤ Q E ( F k ) gives the stated gap for exact simulation.
A nearly quadratic gap between randomized and exact quantum queries
We next use the recursive algorithm underlying the transfer principles to separate randomized query complexity from exact quantum query complexity. For every fixed 0 < ε < 1 0<\varepsilon<1 0 < ε < 1 , we construct total functions with unbounded exact query complexity and R ≥ Q E 2 − ε R\ge Q_E^{2-\varepsilon} R ≥ Q E 2 − ε . We also give a single family with an explicit subpolynomial loss at exponent two. This improves the previous exponent-3 / 2 3/2 3/2 separation of Ambainis et al. [5 ] , which also follows from the cheat-sheet framework [1 Theorem 24] .
The construction combines two known ingredients with our algorithm. A cheat-sheet gadget has small degree and small bounded-error quantum complexity. Sabotage complexity provides a large randomized lower bound that composes without losing a constant at each level. Our recursive-rate theorem then turns the two small parameters into an exact quantum upper bound. For a fixed target exponent we choose the gadget first. For the quantitative bound at exponent two we choose both its size and its depth.
The recursive separation criterion
We use randomized sabotage complexity, introduced by Ben-David and Kothari [8 ] . In its equivalent search formulation, an algorithm receives a partial assignment compatible with both output values of u u u and must find an unspecified coordinate. The algorithm has zero error; RS ( u ) \operatorname{RS}(u) RS ( u ) is its minimum worst-case expected query cost. The relevant lower bound and composition theorem are
R ( u ) ≥ RS ( u ) 3 , RS ( u ∘ v ) ≥ RS ( u ) RS ( v ) (82) R(u)\ge\frac{\operatorname{RS}(u)}{3},\qquad\operatorname{RS}(u\circ v)\ge\operatorname{RS}(u)\operatorname{RS}(v) \tag*{(82)} R ( u ) ≥ 3 RS ( u ) , RS ( u ∘ v ) ≥ RS ( u ) RS ( v ) (82)
[8 Theorems 3.4 and 4.5] .
In particular, R ( h ∘ k ) ≥ RS ( h ) k / 3 R(h^{\circ k})\ge\operatorname{RS}(h)^k/3 R ( h ∘ k ) ≥ RS ( h ) k /3 [8 Corollary 4.6] . We invoke these known results without reproving them. Their coefficient-one composition bound is important: a loss of a constant at every level would change the exponential base.
Proposition 9.1 (A randomized separation from a fixed gadget). Let h h h be a fixed nonconstant total Boolean function, and set
r = RS ( h ) , ρ = Q E lim ( h ) = max { deg ( h ) , Adv ± ( h ) } . r=\operatorname{RS}(h),\qquad\rho=Q_E^{\lim}(h)=\max\{\deg(h),\operatorname{Adv}^{\pm}(h)\}. r = RS ( h ) , ρ = Q E l i m ( h ) = max { deg ( h ) , Adv ± ( h )} . Then
R ( h ∘ k ) ≥ r k 3 , Q E ( h ∘ k ) = ρ k exp ( o h ( k ) ) . (83) R(h^{\circ k})\ge\frac{r^k}{3},\qquad Q_E(h^{\circ k})=\rho^k\exp(o_h(k)). \tag*{(83)} R ( h ∘ k ) ≥ 3 r k , Q E ( h ∘ k ) = ρ k exp ( o h ( k )) . (83) For every α > 0 \alpha>0 α > 0 with r > ρ α r>\rho^\alpha r > ρ α , there is η > 0 \eta>0 η > 0 such that, for all sufficiently large k k k ,
R ( h ∘ k ) ≥ e η k Q E ( h ∘ k ) α . (84) R(h^{\circ k})\ge e^{\eta k}Q_E(h^{\circ k})^\alpha. \tag*{(84)} R ( h ∘ k ) ≥ e η k Q E ( h ∘ k ) α . (84) In particular, R ( h ∘ k ) / Q E ( h ∘ k ) α → ∞ R(h^{\circ k})/Q_E(h^{\circ k})^\alpha\to\infty R ( h ∘ k ) / Q E ( h ∘ k ) α → ∞ as k → ∞ k\to\infty k → ∞ .
Proof. The first inequality in (83) follows from sabotage composition, and the second is Theorem 6.2 . Set η = 1 2 log ( r / ρ α ) > 0 \eta= \frac{1}{2}\log(r/\rho^\alpha)>0 η = 2 1 log ( r / ρ α ) > 0 . The factor r k / ρ α k = e 2 η k r^k/\rho^{\alpha k}=e^{2\eta k} r k / ρ α k = e 2 η k absorbs both the exp ( o h ( k ) ) \exp(o_h(k)) exp ( o h ( k )) overhead and the constant 1 / 3 1/3 1/3 for sufficiently large k k k . This gives (84) .
This is the separating-family direction of the transfer argument from § 7 . The composable measure is now sabotage complexity, which lower-bounds R R R , while the exact recursive rate supplies the algorithmic upper bound.
A standard cheat-sheet gadget
Let u n = AND n ∘ OR n u_n=\operatorname{AND}_n\circ\operatorname{OR}_n u n = AND n ∘ OR n , viewed as a function on an n × n n\times n n × n Boolean matrix. A certificate specifies either a zero row or one nonzero entry in every row. Let h n h_n h n be its standard cheat-sheet function [1 ] : its input contains O ( log n ) O(\log n) O ( log n ) copies of the matrix and an array of certificate records. The copy outputs specify an address, and h n h_n h n accepts exactly when the record at that address contains valid certificates agreeing with those outputs. This defines a total Boolean function, including on inputs with invalid records. We use the following established estimates.
Lemma 9.2 (Known cheat-sheet estimates). There are total Boolean functions h n h_n h n on v n = n O ( 1 ) v_n=n^{O(1)} v n = n O ( 1 ) bits with
n ≤ deg ( h n ) = O ~ ( n ) , Q ( h n ) = O ~ ( n ) , RS ( h n ) = Ω ~ ( n 2 ) . (85) n\leq\deg(h_n)=\widetilde{O}(n),\qquad Q(h_n)=\widetilde{O}(n),\qquad\operatorname{RS}(h_n)=\widetilde{\Omega}(n^2). \tag*{(85)} n ≤ deg ( h n ) = O ( n ) , Q ( h n ) = O ( n ) , RS ( h n ) = Ω ( n 2 ) . (85) Consequently,
n ≤ ρ n : = Q E lim ( h n ) = O ~ ( n ) , r n : = RS ( h n ) = Ω ~ ( n 2 ) . (86) n\leq\rho_n:=Q_E^{\lim}(h_n)=\widetilde{O}(n),\qquad r_n:=\operatorname{RS}(h_n)=\widetilde{\Omega}(n^2). \tag*{(86)} n ≤ ρ n := Q E l i m ( h n ) = O ( n ) , r n := RS ( h n ) = Ω ( n 2 ) . (86)
The upper bounds are the specialization of [1 Theorem 16 and Lemmas 17 and 19] to Q ( u n ) = O ( n ) Q(u_n)=O(n) Q ( u n ) = O ( n ) and a deterministic certificate verifier of cost O ( n log n ) O(n\log n) O ( n log n ) . For sabotage complexity, the cheat-sheet observation in [8 Section 7.1] gives RS ( u C S ) = Ω ~ ( R ( u ) ) \operatorname{RS}(u_{\mathrm{CS}})=\widetilde{\Omega}(R(u)) RS ( u CS ) = Ω ( R ( u )) ; combine it with R ( u n ) = Θ ( n 2 ) R(u_n)=\Theta(n^2) R ( u n ) = Θ ( n 2 ) [11 ] . These are inputs from the literature, rather than new cheat-sheet bounds.
For clarity, the lower degree bound follows from a simple restriction. Leave the first column of one matrix free and fix its remaining entries to zero. In every other matrix, fix the first column to one. Fix the record at the all-ones address to certify the first-column entries, and make every other record invalid. The restricted function accepts exactly when all n n n free entries are one, so it is AND n \operatorname{AND}_n AND n . Thus deg ( h n ) ≥ n \deg(h_n)\geq n deg ( h n ) ≥ n . Finally, the adversary characterization Adv ± ( h n ) = O ( Q ( h n ) ) \operatorname{Adv}^{\pm}(h_n)=O(Q(h_n)) Adv ± ( h n ) = O ( Q ( h n )) gives (86) .
Both upper bounds in (85) are needed: our exact recursive algorithm is controlled by the larger of degree and the adversary bound. Making only one of these parameters small would not suffice.
Approaching separation exponent two
Theorem 9.3 (A nearly quadratic randomized–exact quantum gap). For every 0 < ε < 1 0<\varepsilon<1 0 < ε < 1 there is a fixed total Boolean function h = h ε h=h_\varepsilon h = h ε with deg ( h ) ≥ 2 \deg(h)\geq2 deg ( h ) ≥ 2 such that, for all sufficiently large k k k ,
R ( h ∘ k ) ≥ Q E ( h ∘ k ) 2 − ε . (87) R(h^{\circ k})\geq Q_E(h^{\circ k})^{2-\varepsilon}. \tag*{(87)} R ( h ∘ k ) ≥ Q E ( h ∘ k ) 2 − ε . (87) For the same fixed gadget,
lim k → ∞ R ( h ∘ k ) Q E ( h ∘ k ) 2 − ε = ∞ . \lim_{k\to\infty}\frac{R(h^{\circ k})}{Q_E(h^{\circ k})^{2-\varepsilon}}=\infty. k → ∞ lim Q E ( h ∘ k ) 2 − ε R ( h ∘ k ) = ∞. There is also a family of total Boolean functions W n W_n W n with unbounded exact query complexity satisfying
R ( W n ) ≥ Q E ( W n ) 2 exp ( O ( log ( Q E ( W n ) + 2 ) log log ( Q E ( W n ) + 3 ) ) ) . (88) R(W_n)\geq\frac{Q_E(W_n)^2}{\exp\!\left(O\!\left(\sqrt{\log(Q_E(W_n)+2)}\log\log(Q_E(W_n)+3)\right)\right)}. \tag*{(88)} R ( W n ) ≥ exp ( O ( log ( Q E ( W n ) + 2 ) log log ( Q E ( W n ) + 3 ) ) ) Q E ( W n ) 2 . (88)
In particular, this one family witnesses every fixed exponent α < 2 \alpha< 2 α < 2 in the sense that
lim n → ∞ R ( W n ) Q E ( W n ) α = ∞ . \lim_{n\to\infty} \frac{R(W_n)}{Q_E(W_n)^\alpha} = \infty. n → ∞ lim Q E ( W n ) α R ( W n ) = ∞.
Proof. By Lemma 9.2 , there are constants C 1 , C 2 > 0 C_1,C_2 > 0 C 1 , C 2 > 0 and a , b ≥ 0 a,b \ge0 a , b ≥ 0 such that for all sufficiently large n n n ,
r n ≥ C 1 n 2 ( log n ) a , n ≤ ρ n ≤ C 2 n ( log n ) b . r_n \ge\frac{C_1n^2}{(\log n)^a}, \qquad n \le\rho_n \le C_2n(\log n)^b. r n ≥ ( log n ) a C 1 n 2 , n ≤ ρ n ≤ C 2 n ( log n ) b .
A fixed gadget for each exponent. For fixed ε > 0 \varepsilon> 0 ε > 0 , the bound
r n ρ n 2 − ε ≥ C 1 C 2 2 − ε n ε ( log n ) a + b ( 2 − ε ) \frac{r_n}{\rho_n^{2-\varepsilon}} \ge\frac{C_1}{C_2^{2-\varepsilon}}\frac{n^\varepsilon}{(\log n)^{a+b(2-\varepsilon)}} ρ n 2 − ε r n ≥ C 2 2 − ε C 1 ( log n ) a + b ( 2 − ε ) n ε
exceeds one for sufficiently large n n n . Fix one such n ≥ 2 n \ge2 n ≥ 2 and apply Proposition 9.1 to h = h n h=h_n h = h n with α = 2 − ε \alpha=2-\varepsilon α = 2 − ε . Degree composition gives Q E ( h ∘ k ) ≥ n k / 2 Q_E(h^{\circ k}) \ge n^{k/2} Q E ( h ∘ k ) ≥ n k /2 . The exponential factor in (84) makes R ( h ∘ k ) / Q E ( h ∘ k ) 2 − ε R(h^{\circ k})/Q_E(h^{\circ k})^{2-\varepsilon} R ( h ∘ k ) / Q E ( h ∘ k ) 2 − ε tend to infinity as the depth increases.
A quantitative bound with varying gadgets. Write δ n = deg ( h n ) \delta_n=\deg(h_n) δ n = deg ( h n ) and let v n v_n v n be the arity of h n h_n h n . Choose an absolute p p p such that v n ≤ n p v_n \le n^p v n ≤ n p for sufficiently large n n n . We need an exact algorithm estimate with constants uniform in n n n . For j ≥ 2 j \ge2 j ≥ 2 , apply Theorem 4.1 with outer function h n ∘ ( j − 1 ) h_n^{\circ(j-1)} h n ∘ ( j − 1 ) and inner function h n h_n h n . The correction cost is O ( v n δ n j − 1 ) O(v_n\delta_n^{j-1}) O ( v n δ n j − 1 ) . The outer degree is δ n j − 1 \delta_n^{j-1} δ n j − 1 , so the required error reduction for h n h_n h n costs O ( j log n ) O(j\log n) O ( j log n ) repetitions of a bounded-error algorithm. Here we use δ n ≤ v n \delta_n \le v_n δ n ≤ v n and Q ( h n ) = O ( Adv ± ( h n ) ) = O ( ρ n ) Q(h_n)=O(\operatorname{Adv}^{\pm}(h_n))=O(\rho_n) Q ( h n ) = O ( Adv ± ( h n )) = O ( ρ n ) . For u j = Q E ( h n ∘ j ) / ρ n j u_j=Q_E(h_n^{\circ j})/\rho_n^j u j = Q E ( h n ∘ j ) / ρ n j this gives, with an absolute C C C ,
u j ≤ C n p + C j log n u j − 1 , u 1 ≤ n p . u_j \le Cn^p+Cj\log n\,u_{j-1}, \qquad u_1 \le n^p. u j ≤ C n p + C j log n u j − 1 , u 1 ≤ n p .
The bound on u 1 u_1 u 1 follows by reading the input. Induction yields u j ≤ n p ( C ′ ( j + 1 ) log n ) j u_j \le n^p(C'(j+1)\log n)^j u j ≤ n p ( C ′ ( j + 1 ) log n ) j for a sufficiently large absolute C ′ C' C ′ ; in the recurrence, the additive term is at most half the proposed bound and the factor C j log n Cj\log n C j log n times the preceding bound is at most the other half.
Take d n = ⌈ log n / log log n ⌉ d_n=\lceil\log n/\log\log n\rceil d n = ⌈ log n / log log n ⌉ for sufficiently large n n n and put W n = h n ∘ d n W_n=h_n^{\circ d_n} W n = h n ∘ d n . Then d n log ( ( d n + 1 ) log n ) = O ( log n ) d_n\log((d_n+1)\log n)=O(\log n) d n log (( d n + 1 ) log n ) = O ( log n ) and d n log log n = O ( log n ) d_n\log\log n=O(\log n) d n log log n = O ( log n ) . Since r n ≥ ρ n 2 exp ( − O ( log log n ) ) r_n\ge\rho_n^2\exp(-O(\log\log n)) r n ≥ ρ n 2 exp ( − O ( log log n )) , the uniform upper bound and sabotage composition give
1 2 n d n ≤ Q E ( W n ) ≤ ρ n 2 d n exp ( O ( log n ) ) , R ( W n ) ≥ ρ n 2 d n exp ( − O ( log n ) ) . (89) \frac{1}{2}n^{d_n}\le Q_E(W_n)\le\rho_n^{2d_n}\exp(O(\log n)), \qquad R(W_n)\ge\rho_n^{2d_n}\exp(-O(\log n)). \tag*{(89)} 2 1 n d n ≤ Q E ( W n ) ≤ ρ n 2 d n exp ( O ( log n )) , R ( W n ) ≥ ρ n 2 d n exp ( − O ( log n )) . (89)
The lower bound on Q E ( W n ) Q_E(W_n) Q E ( W n ) uses degree composition. In particular, log Q E ( W n ) = Θ ( d n log n ) \log Q_E(W_n)=\Theta(d_n\log n) log Q E ( W n ) = Θ ( d n log n ) and log log Q E ( W n ) = Θ ( log log n ) \log\log Q_E(W_n)=\Theta(\log\log n) log log Q E ( W n ) = Θ ( log log n ) . Thus log n = O ( log Q E ( W n ) log log Q E ( W n ) ) \log n=O\left(\sqrt{\log Q_E(W_n)\log\log Q_E(W_n)}\right) log n = O ( log Q E ( W n ) log log Q E ( W n ) ) . Substituting this estimate in (89) gives (88) . In particular, if q n = Q E ( W n ) q_n=Q_E(W_n) q n = Q E ( W n ) , then for each fixed α < 2 \alpha<2 α < 2 ,
log ( R ( W n ) q n α ) ≥ ( 2 − α ) log q n − O ( log ( q n + 2 ) log log ( q n + 3 ) ) . \log\left(\frac{R(W_n)}{q_n^\alpha}\right)\ge(2-\alpha)\log q_n-O\left(\sqrt{\log(q_n+2)\log\log(q_n+3)}\right). log ( q n α R ( W n ) ) ≥ ( 2 − α ) log q n − O ( log ( q n + 2 ) log log ( q n + 3 ) ) .
The loss term is o ( log q n ) o(\log q_n) o ( log q n ) , and q n q_n q n tends to infinity by (89) . Thus the ratio tends to infinity on the same family for every such α \alpha α .
The loss in (88) is subpolynomial in Q E ( W n ) Q_E(W_n) Q E ( W n ) . Obtaining a quadratic separation with a fixed polylogarithmic loss remains open for this construction.
Different inner functions
The subset expansion from Section 3 does not require all inner functions to be identical. When block sizes differ, the correction cost is determined by the blocks that can occur together in an outer monomial. When the inner algorithms have different costs, their error probabilities can be chosen separately. This section makes both features explicit.
Unequal blocks and weighted degree
Let f f f be a nonconstant total Boolean function on n n n bits. For each i ∈ [ n ] i \in[n] i ∈ [ n ] , let g i g_i g i be a nonconstant total Boolean function on m i m_i m i bits, and suppose that the input blocks are disjoint. We consider
F ( x ) = f ( g 1 ( x ( 1 ) ) , … , g n ( x ( n ) ) ) , N = ∑ i = 1 n m i . F(x) = f\left(g_1\left(x^{(1)}\right),\ldots,g_n\left(x^{(n)}\right)\right), \qquad N = \sum_{i=1}^{n} m_i. F ( x ) = f ( g 1 ( x ( 1 ) ) , … , g n ( x ( n ) ) ) , N = i = 1 ∑ n m i .
Write H ( y ) = ∑ T H ^ ( T ) y T H(y) = \sum_T \widehat{H}(T)y_T H ( y ) = ∑ T H ( T ) y T for the signed polynomial of f f f . For positive weights w = ( w 1 , … , w n ) \mathbf{w} = (w_1,\ldots,w_n) w = ( w 1 , … , w n ) , define the weighted degree
D w ( f ) : = max H ^ ( T ) ≠ 0 ∑ i ∈ T w i . (90) D_{\mathbf{w}}(f) := \max_{\widehat{H}(T)\ne0} \sum_{i\in T} w_i. \tag*{(90)} D w ( f ) := H ( T ) = 0 max i ∈ T ∑ w i . (90)
Thus D m ( f ) D_{\mathbf{m}}(f) D m ( f ) is the largest number of input bits contained in the blocks indexed by a single monomial of H H H . This is the appropriate correction cost: a nonzero derivative ∂ S H \partial_S H ∂ S H can occur only when S S S is contained in the support of such a monomial. In particular, D m ( f ) ≤ deg ( f ) max i m i D_{\mathbf{m}}(f) \le\deg(f)\max_i m_i D m ( f ) ≤ deg ( f ) max i m i , and the inequality can be strict.
We also recall the weighted form of the degree-composition identity [26 Lemma 3.1(1)] . If d i = deg ( g i ) d_i = \deg(g_i) d i = deg ( g i ) , then
deg ( F ) = D d ( f ) . (91) \deg(F) = D_{\mathbf{d}}(f). \tag*{(91)} deg ( F ) = D d ( f ) . (91)
This standard polynomial substitution identity will provide lower bounds matching the algorithm in some cases.
Proposition 10.1 (Exact evaluation with different inner functions). Choose 0 < ε i < 1 / 2 0 < \varepsilon_i < 1/2 0 < ε i < 1/2 with ∑ i ε i ≤ 1 / 4 \sum_i \varepsilon_i \le1/4 ∑ i ε i ≤ 1/4 , and put t ∗ : = max i Q ε i ( g i ) t_* := \max_i Q_{\varepsilon_i}(g_i) t ∗ := max i Q ε i ( g i ) . Then
Q E ( F ) ≤ 6 D m ( f ) + 12 Q E ( f ) t ∗ . (92) Q_E(F) \le6D_{\mathbf{m}}(f) + 12Q_E(f)t_*. \tag*{(92)} Q E ( F ) ≤ 6 D m ( f ) + 12 Q E ( f ) t ∗ . (92)
Proof. We use the same branches as in Theorem 3.1 , but normalize the residual for block i i i by its own error bound. There are two quantities to control: the maximum cost of a branch and the sum of the branch weights.
For each i i i , choose an algorithm A i A_i A i with error at most ε i \varepsilon_i ε i , and pad it to t ∗ t_* t ∗ queries using the dummy query coordinate. Fix an input x x x . Let z i = ( − 1 ) g i ( x ( i ) ) z_i = (-1)^{g_i(x^{(i)})} z i = ( − 1 ) g i ( x ( i ) ) be the correct sign, let b i b_i b i be the signed output bias of A i A_i A i , and write e i = z i − b i e_i = z_i - b_i e i = z i − b i . Then ∣ e i ∣ ≤ 2 ε i |e_i| \le2\varepsilon_i ∣ e i ∣ ≤ 2 ε i , and the exact subset expansion is
H ( z ) = ∑ S : ∂ S H ≠ 0 e S ∂ S H ( b ) . (93) H(z) = \sum_{\substack{S:\partial_S H\ne0}} e_S \,\partial_S H(b). \tag*{(93)} H ( z ) = S : ∂ S H = 0 ∑ e S ∂ S H ( b ) . (93)
As before, the quantities b i b_i b i and e i e_i e i are used to analyze the return amplitudes; the algorithm does not first estimate them.
For a fixed set S S S , the derivative-correlation circuit of Lemma 3.3 uses A i A_i A i whenever the outer query register selects block i i i . The padding permits this selection coherently, with one common query schedule. Its cost is at most 4 Q E ( f ) t ∗ 4Q_E(f)t_* 4 Q E ( f ) t ∗ . Independently, Lemma 3.4 implements the return amplitude e i / ( 2 ε i ) e_i/(2\varepsilon_i) e i / ( 2 ε i ) by reading and unreading block i i i , at cost 2 m i 2m_i 2 m i . Multiplying these return amplitudes therefore gives a branch with return amplitude
a S ( x ) = ∂ S H ( b ) ∏ i ∈ S e i 2 ε i . a_S(x)=\partial_S H(b)\prod_{i\in S}\frac{e_i}{2\varepsilon_i}. a S ( x ) = ∂ S H ( b ) i ∈ S ∏ 2 ε i e i .
If ∂ S H ≠ 0 \partial_S H\ne0 ∂ S H = 0 , some set T T T with H ^ ( T ) ≠ 0 \widehat{H}(T)\ne0 H ( T ) = 0 contains S S S . Consequently,
∑ i ∈ S m i ≤ D m ( f ) , \sum_{i\in S}m_i\le D_{\mathrm{m}}(f), i ∈ S ∑ m i ≤ D m ( f ) ,
and every branch uses at most
B = 2 D m ( f ) + 4 Q E ( f ) t ∗ . B=2D_{\mathrm{m}}(f)+4Q_E(f)t_*. B = 2 D m ( f ) + 4 Q E ( f ) t ∗ .
queries. Padding these complete branches to the same schedule makes their coherent selection cost B B B , irrespective of the number of branches.
It remains to bound the normalization. Assign branch S S S the weight w S = ∏ i ∈ S 2 ε i w_S=\prod_{i\in S}2\varepsilon_i w S = ∏ i ∈ S 2 ε i . Then
L : = ∑ S : ∂ S H ≠ 0 w S ≤ ∏ i = 1 n ( 1 + 2 ε i ) ≤ exp ( 2 ∑ i ε i ) ≤ e 1 / 2 < 2. L:=\sum_{S:\partial_S H\ne0}w_S\le\prod_{i=1}^{n}(1+2\varepsilon_i)\le\exp\left(2\sum_i\varepsilon_i\right)\le e^{1/2}<2. L := S : ∂ S H = 0 ∑ w S ≤ i = 1 ∏ n ( 1 + 2 ε i ) ≤ exp ( 2 i ∑ ε i ) ≤ e 1/2 < 2.
Add a zero-return branch of weight 2 − L 2-L 2 − L . The coherent selection identity and (93) now give return amplitude
1 2 ∑ S w S a S ( x ) = H ( z ) 2 . \frac{1}{2}\sum_S w_Sa_S(x)=\frac{H(z)}{2}. 2 1 S ∑ w S a S ( x ) = 2 H ( z ) .
The same three-call exact amplification as in Theorem 3.1 produces the clean sign H ( z ) H(z) H ( z ) at cost 3 B 3B 3 B . This is (92) .
Allocating the error budget
Proposition 10.1 separates the correction cost from the choice of accuracies. Optimizing the latter gives
Q E ( F ) ≤ 6 D m ( f ) + 12 Q E ( f ) min 0 < ε i < 1 / 2 ∑ i ε i ≤ 1 / 4 max i Q ε i ( g i ) . (94) Q_E(F)\le6D_{\mathrm{m}}(f)+12Q_E(f)\min_{\substack{0<\varepsilon_i<1/2\\ \sum_i\varepsilon_i\le1/4}}\max_i Q_{\varepsilon_i}(g_i). \tag*{(94)} Q E ( F ) ≤ 6 D m ( f ) + 12 Q E ( f ) 0 < ε i < 1/2 ∑ i ε i ≤ 1/4 min i max Q ε i ( g i ) . (94)
The minimum is attained: the feasible maximum query costs form a nonempty set of nonnegative integers. The choice ε i = 1 / ( 4 n ) \varepsilon_i=1/(4n) ε i = 1/ ( 4 n ) recovers a uniform accuracy requirement. A better allocation can give the more expensive blocks larger error probabilities while keeping the total error budget bounded.
For a convenient sufficient condition, put q i = Q ( g i ) q_i=Q(g_i) q i = Q ( g i ) . These numbers are positive because each g i g_i g i is nonconstant. Standard error reduction gives Q ε ( g i ) = O ( q i log ( 1 / ε ) ) Q_\varepsilon(g_i)=O(q_i\log(1/\varepsilon)) Q ε ( g i ) = O ( q i log ( 1/ ε )) . Hence a value τ > 0 \tau>0 τ > 0 satisfying
∑ i exp ( − τ / q i ) ≤ 1 4 (95) \sum_i\exp(-\tau/q_i)\le\frac{1}{4} \tag*{(95)} i ∑ exp ( − τ / q i ) ≤ 4 1 (95)
provides the feasible allocation ε i = exp ( − τ / q i ) \varepsilon_i=\exp(-\tau/q_i) ε i = exp ( − τ / q i ) and the bound
Q E ( F ) = O ( D m ( f ) + Q E ( f ) τ ) . Q_E(F)=O\left(D_{\mathrm{m}}(f)+Q_E(f)\tau\right). Q E ( F ) = O ( D m ( f ) + Q E ( f ) τ ) .
The role of τ \tau τ is to give every inner algorithm the same query budget, rather than the same error probability.
For example, suppose a group of r r r blocks has q i ≤ q H q_i \le q_H q i ≤ q H and the remaining n − r n-r n − r blocks have q i ≤ q L q_i \le q_L q i ≤ q L , where 1 ≤ r < n 1 \le r < n 1 ≤ r < n . Taking
τ = max { q H log ( 8 r ) , q L log ( 8 ( n − r ) ) } \tau= \max\{q_H \log(8r),\ q_L \log(8(n-r))\} τ = max { q H log ( 8 r ) , q L log ( 8 ( n − r ))}
makes the contribution of each group to (95) at most 1 / 8 1/8 1/8 . If the expensive blocks are few and the remaining blocks are sufficiently inexpensive, this can improve the O ( q H log n ) O(q_H \log n) O ( q H log n ) budget obtained from uniform error reduction.
Unequal search blocks
Suppose now that each g i g_i g i is either OR m i \operatorname{OR}_{m_i} OR m i or AND m i \operatorname{AND}_{m_i} AND m i . Since d i = m i d_i=m_i d i = m i , the degree identity (91) and the polynomial method [7 ] give
Q E ( F ) ≥ 1 2 D m ( f ) . Q_E(F) \ge\frac{1}{2}D_m(f). Q E ( F ) ≥ 2 1 D m ( f ) .
The standard small-error search bound [13 , 15 ] states that
Q ε i ( g i ) = Θ ( min { m i , m i log ( 1 / ε i ) } ) ( 0 < ε i ≤ 1 / 4 ) . Q_{\varepsilon_i}(g_i)=\Theta\left(\min\left\{m_i,\sqrt{m_i\log(1/\varepsilon_i)}\right\}\right)
\qquad(0<\varepsilon_i\le1/4). Q ε i ( g i ) = Θ ( min { m i , m i log ( 1/ ε i ) } ) ( 0 < ε i ≤ 1/4 ) .
Every feasible allocation in Proposition 10.1 has ε i ≤ 1 / 4 \varepsilon_i\le1/4 ε i ≤ 1/4 , so it gives
t ∗ = O ( max i min { m i , m i log ( 1 / ε i ) } ) . t_* = O\left(\max_i \min\left\{m_i,\sqrt{m_i\log(1/\varepsilon_i)}\right\}\right). t ∗ = O ( i max min { m i , m i log ( 1/ ε i ) } ) .
Thus the approximate-evaluation term is the only possible source of a gap between the upper and lower bounds. Whenever the allocation satisfies Q E ( f ) t ∗ = O ( D m ( f ) ) Q_E(f)t_*=O(D_m(f)) Q E ( f ) t ∗ = O ( D m ( f )) , they match:
Q E ( F ) = Θ ( D m ( f ) ) . (96) Q_E(F)=\Theta(D_m(f)). \tag*{(96)} Q E ( F ) = Θ ( D m ( f )) . (96)
This criterion accommodates unequal block sizes without replacing all of them by the largest size.
Applications to quantum communication
We now apply the query algorithms to two communication constructions. For the explicit recursive NAE families, a coordinatewise AND gadget preserves a disjointness restriction, which gives a linear randomized lower bound. For the nearly quadratic separation, we instead use an inner-product gadget and a randomized lifting theorem. Both constructions use the standard exact query-to-communication simulation for their quantum upper bounds.
Throughout this section, Q E c c Q_E^{\mathrm{cc}} Q E cc denotes exact quantum communication complexity without prior entanglement, and R 1 / 3 c c R_{1/3}^{\mathrm{cc}} R 1/3 cc denotes public-coin randomized communication complexity with worst-case error at most 1 / 3 1/3 1/3 . Protocols may have unrestricted interaction. Local computation is free, and communication costs are worst-case costs.
Standard simulation and lower bounds
For a Boolean function h h h on N N N bits, define its coordinatewise-AND communication lift by
H h ( x , y ) = h ( x 1 ∧ y 1 , … , x N ∧ y N ) , x , y ∈ { 0 , 1 } N . H_h(x,y)=h(x_1\land y_1,\ldots,x_N\land y_N),\qquad x,y\in\{0,1\}^N. H h ( x , y ) = h ( x 1 ∧ y 1 , … , x N ∧ y N ) , x , y ∈ { 0 , 1 } N .
Alice receives x x x and Bob receives y y y . We will use three established facts: query simulation for the quantum upper bound, disjointness for the randomized lower bound, and a rank identity for an exact quantum lower bound.
Lemma 11.1 (Query simulation; Buhrman, Cleve, and Wigderson [12 ] ). For every Boolean function h h h on N N N bits,
Q E c c ( H h ) = O ( log ( N + 1 ) Q E ( h ) ) . (97) Q^{\mathrm{cc}}_{E}(\mathcal{H}_h)=O(\log(N+1)Q_E(h)). \tag*{(97)} Q E cc ( H h ) = O ( log ( N + 1 ) Q E ( h )) . (97) The protocol requires no prior entanglement.
The simulation preserves the error of the query algorithm, so an exact query algorithm gives an exact communication protocol. We invoke the simulation without reproving it.
For the classical lower bound, recall Razborov’s Ω ( N ) \Omega(N) Ω ( N ) randomized lower bound for disjointness even under the promise that the intersection has size zero or one [23 ] . If h ( 0 N ) = 0 h(0^N)=0 h ( 0 N ) = 0 and h ( e i ) = 1 h(e_i)=1 h ( e i ) = 1 for every unit vector e i e_i e i , then restricting the communication inputs to this promise makes H h \mathcal{H}_h H h distinguish these two cases. Together with the trivial O ( N ) O(N) O ( N ) deterministic upper bound, this gives
R 1 / 3 c c ( H h ) = Θ ( N ) , D c c ( H h ) = Θ ( N ) . (98) R^{\mathrm{cc}}_{1/3}(\mathcal{H}_h)=\Theta(N),\qquad D^{\mathrm{cc}}(\mathcal{H}_h)=\Theta(N). \tag*{(98)} R 1/3 cc ( H h ) = Θ ( N ) , D cc ( H h ) = Θ ( N ) . (98)
Thus full sensitivity at zero gives a direct classical lower bound for the AND lift.
The heterogeneous algorithm also has an immediate communication consequence. For F = f ( g 1 , … , g n ) F=f(g_1,\ldots,g_n) F = f ( g 1 , … , g n ) on N = ∑ i m i N=\sum_i m_i N = ∑ i m i input bits, Proposition 10.1 and Lemma 11.1 imply
Q E c c ( H F ) = O ( log ( N + 1 ) [ D m ( f ) + Q E ( f ) max i Q ε i ( g i ) ] ) , ∑ i ε i ≤ 1 4 . (99) Q^{\mathrm{cc}}_{E}(\mathcal{H}_F)=O\left(\log(N+1)\left[D_m(f)+Q_E(f)\max_i Q_{\varepsilon_i}(g_i)\right]\right),
\qquad\sum_i\varepsilon_i\le\frac{1}{4}. \tag*{(99)} Q E cc ( H F ) = O ( log ( N + 1 ) [ D m ( f ) + Q E ( f ) i max Q ε i ( g i ) ] ) , i ∑ ε i ≤ 4 1 . (99)
The error allocation can therefore be optimized exactly as in (94) . Moreover, if f f f and each g i g_i g i are zero at zero and one at every unit vector, then F F F has the same property. In this case (98) gives randomized communication complexity Θ ( N ) \Theta(N) Θ ( N ) .
To obtain an exact quantum lower bound, let mon ( h ) \operatorname{mon}(h) mon ( h ) denote the number of nonzero monomials in the multilinear representation of h h h in { 0 , 1 } \{0,1\} { 0 , 1 } variables.
Lemma 11.2 (AND-lift rank and exact quantum log-rank [10 ] ). For the real Boolean communication matrix M h = ( h ( x ∧ y ) ) x , y M_h=(h(x\wedge y))_{x,y} M h = ( h ( x ∧ y ) ) x , y ,
rank ( M h ) = mon ( h ) . \operatorname{rank}(M_h)=\operatorname{mon}(h). rank ( M h ) = mon ( h ) . Consequently,
Q E c c ( H h ) ≥ 1 2 log 2 mon ( h ) . (100) Q^{\mathrm{cc}}_{E}(\mathcal{H}_h)\ge\frac{1}{2}\log_2\operatorname{mon}(h). \tag*{(100)} Q E cc ( H h ) ≥ 2 1 log 2 mon ( h ) . (100)
The rank identity and the exact quantum log-rank bound are, respectively, Corollary 6 and Theorem 2 of Buhrman and de Wolf [10 ] . We use these established results without proof. Their unassisted consequence suffices for the communication model considered here.
Recursive NAE and the balanced family
Recall the families
F k = NAE 3 ∘ k , m k = ⌈ ( 9 / 8 ) k ⌉ , G k = F k ∘ OR m k , N k = 3 k m k . F_k=\operatorname{NAE}_3^{\circ k},\qquad m_k=\left\lceil(9/8)^k\right\rceil,\qquad G_k=F_k\circ\operatorname{OR}_{m_k},\qquad N_k=3^k m_k. F k = NAE 3 ∘ k , m k = ⌈ ( 9/8 ) k ⌉ , G k = F k ∘ OR m k , N k = 3 k m k .
Both are zero at zero and one at every unit vector. Their AND lifts therefore have linear randomized complexity. The purpose of the next theorem is to quantify the exact quantum savings and, for the balanced family, prove a matching lower exponent.
Theorem 11.3 (Exact protocols for the recursive families). Let a = 3 / 2 a = 3/\sqrt{2} a = 3/ 2 . For F k F_k F k on N = 3 k N = 3^k N = 3 k bits,
Q E c c ( H F k ) ≤ N log 3 a exp ( O ( ( log log N ) 2 ) ) , (101) Q^{\mathrm{cc}}_E(\mathcal{H}_{F_k}) \le N^{\log_3 a}\exp\left(O\left((\log\log N)^2\right)\right), \tag*{(101)} Q E cc ( H F k ) ≤ N l o g 3 a exp ( O ( ( log log N ) 2 ) ) , (101) R 1 / 3 c c ( H F k ) = Θ ( N ) . R^{\mathrm{cc}}_{1/3}(\mathcal{H}_{F_k}) = \Theta(N). R 1/3 cc ( H F k ) = Θ ( N ) . For G k G_k G k on N = N k N = N_k N = N k bits,
Ω ( N 2 / 3 ) ≤ Q E c c ( H G k ) ≤ N 2 / 3 exp ( O ( ( log log N ) 2 ) ) , (102) \Omega(N^{2/3}) \le Q^{\mathrm{cc}}_E(\mathcal{H}_{G_k}) \le N^{2/3}\exp\left(O\left((\log\log N)^2\right)\right), \tag*{(102)} Ω ( N 2/3 ) ≤ Q E cc ( H G k ) ≤ N 2/3 exp ( O ( ( log log N ) 2 ) ) , (102) and R 1 / 3 c c ( H G k ) = Θ ( N ) R^{\mathrm{cc}}_{1/3}(\mathcal{H}_{G_k}) = \Theta(N) R 1/3 cc ( H G k ) = Θ ( N ) . In both cases D c c = Θ ( N ) D^{\mathrm{cc}} = \Theta(N) D cc = Θ ( N ) . Writing q k = Q E c c ( H G k ) q_k = Q^{\mathrm{cc}}_E(\mathcal{H}_{G_k}) q k = Q E cc ( H G k ) , the balanced family satisfies
q k 3 / 2 exp ( O ( ( log log ( q k + 3 ) ) 2 ) ) ≤ R 1 / 3 c c ( H G k ) ≤ O ( q k 3 / 2 ) . (103) \frac{q_k^{3/2}}{\exp\left(O\left((\log\log(q_k+3))^2\right)\right)} \le R^{\mathrm{cc}}_{1/3}(\mathcal{H}_{G_k}) \le O(q_k^{3/2}). \tag*{(103)} exp ( O ( ( log log ( q k + 3 ) ) 2 ) ) q k 3/2 ≤ R 1/3 cc ( H G k ) ≤ O ( q k 3/2 ) . (103)
Proof. The classical claims follow from the sensitivity calculation in § 8 and (98) . We first establish the quantum upper bounds, and then count monomials to obtain the lower bound for G k G_k G k . By Theorem 5.1 and query simulation,
Q E c c ( H F k ) ≤ O ( k ) a k exp ( O ( ( log ( k + 2 ) ) 2 ) ) . Q^{\mathrm{cc}}_E(\mathcal{H}_{F_k}) \le O(k)a^k\exp\left(O\left((\log(k+2))^2\right)\right). Q E cc ( H F k ) ≤ O ( k ) a k exp ( O ( ( log ( k + 2 ) ) 2 ) ) .
Since N = 3 k N = 3^k N = 3 k , we have a k = N log 3 a a^k = N^{\log_3 a} a k = N l o g 3 a and k = Θ ( log N ) k = \Theta(\log N) k = Θ ( log N ) . The factor O ( k ) O(k) O ( k ) is absorbed by the displayed subpolynomial overhead, proving (101) . Applying the same simulation to Theorem 8.1 gives
Q E c c ( H G k ) ≤ ( 9 / 4 ) k exp ( O ( ( log ( k + 2 ) ) 2 ) ) . Q^{\mathrm{cc}}_E(\mathcal{H}_{G_k}) \le(9/4)^k\exp\left(O\left((\log(k+2))^2\right)\right). Q E cc ( H G k ) ≤ ( 9/4 ) k exp ( O ( ( log ( k + 2 ) ) 2 ) ) .
Here the additional simulation factor O ( k ) O(k) O ( k ) has again been absorbed. The identities
N k = Θ ( ( 27 / 8 ) k ) , ( 27 / 8 ) 2 / 3 = 9 / 4 N_k = \Theta((27/8)^k), \qquad(27/8)^{2/3} = 9/4 N k = Θ (( 27/8 ) k ) , ( 27/8 ) 2/3 = 9/4
give the upper bound in (102) .
For the lower bound, fix m ≥ 2 m \ge2 m ≥ 2 . Let s j s_j s j count the nonzero monomials in the { 0 , 1 } \{0,1\} { 0 , 1 } polynomial of F j ∘ OR m F_j \circ\operatorname{OR}_m F j ∘ OR m , with F 0 F_0 F 0 the identity function. The initial polynomial
OR m ( z ) = 1 − ∏ i = 1 m ( 1 − z i ) \operatorname{OR}_m(z) = 1 - \prod_{i=1}^{m}(1-z_i) OR m ( z ) = 1 − i = 1 ∏ m ( 1 − z i )
has s 0 = 2 m − 1 s_0 = 2^m - 1 s 0 = 2 m − 1 monomials and no constant term. The polynomial of the ternary gate is
NAE 3 ( u , v , w ) = u + v + w − u v − u w − v w . \operatorname{NAE}_3(u,v,w) = u + v + w - uv - uw - vw. NAE 3 ( u , v , w ) = u + v + w − uv − u w − v w .
At the next recursive level, the three child polynomials have disjoint variable sets and zero constant term. A monomial from a linear term is supported in exactly one child; a monomial from a quadratic term is supported in exactly two children. These two types cannot cancel. Within a fixed child or pair of children, the support uniquely determines the constituent monomials, so cancellation cannot occur there either. We therefore obtain the exact recurrence
s j + 1 = 3 s j + 3 s j 2 . s_{j+1} = 3s_j + 3s_j^2. s j + 1 = 3 s j + 3 s j 2 .
For a lower bound, it is enough to retain the inequality s j + 1 ≥ s j 2 s_{j+1} \ge s_j^2 s j + 1 ≥ s j 2 . Iterating it gives
log 2 s k ≥ 2 k log 2 ( 2 m − 1 ) ≥ 2 k − 1 m . \log_2 s_k \ge2^k\log_2(2^m-1) \ge2^{k-1}m. log 2 s k ≥ 2 k log 2 ( 2 m − 1 ) ≥ 2 k − 1 m .
Lemma 11.2 now yields
Q E c c ( H F k ∘ O R m ) ≥ 2 k − 2 m . Q^{\mathrm{cc}}_{E}(\mathcal{H}_{F_k\circ\mathrm{OR}_m}) \ge2^{k-2}m. Q E cc ( H F k ∘ OR m ) ≥ 2 k − 2 m .
Finally, set m = m k m=m_k m = m k . Since 2 k m k = Θ ( ( 9 / 4 ) k ) = Θ ( N k 2 / 3 ) 2^k m_k=\Theta((9/4)^k)=\Theta(N_k^{2/3}) 2 k m k = Θ (( 9/4 ) k ) = Θ ( N k 2/3 ) , this is the lower bound in (102) . Since log q k = Θ ( log N ) \log q_k=\Theta(\log N) log q k = Θ ( log N ) , raising the bounds in (102) to the power 3 / 2 3/2 3/2 and using the linear randomized cost gives (103) .
For the same recursive NAE communication function, Ambainis’s STOC 2013 algorithm [4 Section 3.6] used O ( N 0.8675 … log N ) O(N^{0.8675\ldots}\log N) O ( N 0.8675 … log N ) qubits. Equation (101) reduces the exponent to log 3 ( 3 / 2 ) = 0.684535 … \log_3(3/\sqrt{2})=0.684535\ldots log 3 ( 3/ 2 ) = 0.684535 … . Adding the OR layer yields the explicit exponent-3 / 2 3/2 3/2 separation in (102) ; the monomial count certifies the matching exponent for its exact quantum communication complexity.
A nearly quadratic randomized–exact separation
The functions from Theorem 9.3 need not be fully sensitive at zero. We therefore cannot use the preceding disjointness restriction to transfer their randomized query lower bounds. Instead, we use the inner-product gadget
IP b ( u , v ) = ⨁ j = 1 b u j v j , u , v ∈ { 0 , 1 } b . \operatorname{IP}_b(u,v)=\bigoplus_{j=1}^{b}u_jv_j,\qquad u,v\in\{0,1\}^{b}. IP b ( u , v ) = j = 1 ⨁ b u j v j , u , v ∈ { 0 , 1 } b .
For an N N N -bit Boolean function f f f , define
I f , b ( x , y ) = f ( IP b ( x 1 , y 1 ) , … , IP b ( x N , y N ) ) , x , y ∈ ( { 0 , 1 } b ) N . (104) \mathcal{I}_{f,b}(x,y)=f\bigl(\operatorname{IP}_b(x_1,y_1),\ldots,\operatorname{IP}_b(x_N,y_N)\bigr),\qquad x,y\in(\{0,1\}^{b})^N. \tag*{(104)} I f , b ( x , y ) = f ( IP b ( x 1 , y 1 ) , … , IP b ( x N , y N ) ) , x , y ∈ ({ 0 , 1 } b ) N . (104)
Choosing b b b logarithmic in N N N has two advantages: randomized lifting preserves the query lower bound up to this logarithmic factor, and exact query simulation incurs only a logarithmic overhead.
Lemma 11.4 (Randomized lifting and exact simulation [14 Theorem 1.2] ,[12 Theorem 2.1] ). There is an absolute constant c > 0 c>0 c > 0 such that, for b = ⌈ c log 2 ( N + 1 ) ⌉ b=\lceil c\log_2(N+1)\rceil b = ⌈ c log 2 ( N + 1 )⌉ and every nonconstant total Boolean function f f f on N N N bits,
R 1 / 3 c c ( I f , b ) = Θ ( b R ( f ) ) , (105) R^{\mathrm{cc}}_{1/3}(\mathcal{I}_{f,b})=\Theta(bR(f)), \tag*{(105)} R 1/3 cc ( I f , b ) = Θ ( b R ( f )) , (105) Q E c c ( I f , b ) = O ( ( log ( N + 1 ) + b ) Q E ( f ) ) . (106) Q^{\mathrm{cc}}_{E}(\mathcal{I}_{f,b})=O\bigl((\log(N+1)+b)Q_E(f)\bigr). \tag*{(106)} Q E cc ( I f , b ) = O ( ( log ( N + 1 ) + b ) Q E ( f ) ) . (106) The exact quantum protocol requires no prior entanglement.
We record how the cited results specialize to this statement. Inner product has uniform discrepancy at most 2 − b / 2 2^{-b/2} 2 − b /2 , and hence satisfies the low-discrepancy hypothesis of the lifting theorem. Its small error increase is absorbed by constant-factor error reduction. The theorem also permits a constant additive loss in the outer query lower bound; when R ( f ) R(f) R ( f ) is bounded, a sensitive-edge restriction to inner product supplies the necessary Ω ( b ) \Omega(b) Ω ( b ) bound. These standard specializations give the constant-error formulation above. No new lifting or simulation theorem is required.
We will also use the following lower bound for b ≥ 2 b\ge2 b ≥ 2 :
Q E c c ( I f , b ) ≥ 1 2 deg ( f ) log 2 ( 2 b − 1 ) . (107) Q^{\mathrm{cc}}_{E}(\mathcal{I}_{f,b})\ge\frac{1}{2}\deg(f)\log_2(2^b-1). \tag*{(107)} Q E cc ( I f , b ) ≥ 2 1 deg ( f ) log 2 ( 2 b − 1 ) . (107)
To see this, regard I f , b \mathcal{I}_{f,b} I f , b as the coordinatewise AND lift of f ∘ PARITY b f\circ\operatorname{PARITY}_b f ∘ PARITY b . Take a monomial of f f f with support S S S of size deg ( f ) \deg(f) deg ( f ) . The polynomial of PARITY b \operatorname{PARITY}_b PARITY b on { 0 , 1 } b \{0,1\}^b { 0 , 1 } b has a nonzero term for every nonempty subset and zero constant term. The substituted monomial therefore yields ( 2 b − 1 ) ∣ S ∣ (2^b-1)^{|S|} ( 2 b − 1 ) ∣ S ∣ distinct monomials whose sets of nonempty blocks are exactly S S S . Only the monomial of f f f with support S S S can contribute these terms. The rank identity and exact log-rank bound in Lemma 11.2 give (107) .
Theorem 11.5 (Nearly quadratic communication separation). For every 0 < ε < 1 0 < \varepsilon< 1 0 < ε < 1 , there is a family of total Boolean communication functions F k \mathcal{F}_k F k with unbounded exact quantum complexity and
R 1 / 3 c c ( F k ) ≥ ( Q E c c ( F k ) ) 2 − ε (108) R^{\mathrm{cc}}_{1/3}(\mathcal{F}_k) \ge\left(Q^{\mathrm{cc}}_{\mathrm{E}}(\mathcal{F}_k)\right)^{2-\varepsilon} \tag*{(108)} R 1/3 cc ( F k ) ≥ ( Q E cc ( F k ) ) 2 − ε (108) for all sufficiently large k k k . There is also a family W n \mathcal{W}_n W n of total Boolean communication functions with unbounded exact quantum complexity satisfying
R 1 / 3 c c ( W n ) ≥ q n 2 exp ( O ( log ( q n + 2 ) log log ( q n + 3 ) ) ) , q n = Q E c c ( W n ) . (109) R^{\mathrm{cc}}_{1/3}(\mathcal{W}_n) \ge\frac{q_n^2}{\exp\left(O\left(\sqrt{\log(q_n+2)}\log\log(q_n+3)\right)\right)}, \qquad q_n=Q^{\mathrm{cc}}_{\mathrm{E}}(\mathcal{W}_n). \tag*{(109)} R 1/3 cc ( W n ) ≥ exp ( O ( log ( q n + 2 ) log log ( q n + 3 ) ) ) q n 2 , q n = Q E cc ( W n ) . (109) The classical protocols may use public randomness and unrestricted interaction. The exact quantum upper bounds use no prior entanglement.
Proof. A fixed exponent. Apply Theorem 9.3 with ε / 2 \varepsilon/2 ε /2 to obtain f k = h ∘ k f_k=h^{\circ k} f k = h ∘ k on N k N_k N k bits. Put b k = ⌈ c log 2 ( N k + 1 ) ⌉ b_k=\lceil c\log_2(N_k+1)\rceil b k = ⌈ c log 2 ( N k + 1 )⌉ as in Lemma 11.4 , and set F k = I f k , b k \mathcal{F}_k=I_{f_k,b_k} F k = I f k , b k . The lemma gives
R 1 / 3 c c ( F k ) ≥ Ω ( b k Q E ( f k ) 2 − ε / 2 ) , Q E c c ( F k ) ≤ O ( b k Q E ( f k ) ) . (110) R^{\mathrm{cc}}_{1/3}(\mathcal{F}_k) \ge\Omega\left(b_kQ_{\mathrm{E}}(f_k)^{2-\varepsilon/2}\right),\qquad Q^{\mathrm{cc}}_{\mathrm{E}}(\mathcal{F}_k)\le O\left(b_kQ_{\mathrm{E}}(f_k)\right). \tag*{(110)} R 1/3 cc ( F k ) ≥ Ω ( b k Q E ( f k ) 2 − ε /2 ) , Q E cc ( F k ) ≤ O ( b k Q E ( f k ) ) . (110)
The factor Q E ( f k ) ε / 2 Q_{\mathrm{E}}(f_k)^{\varepsilon/2} Q E ( f k ) ε /2 grows exponentially in k k k because deg ( h ) ≥ 2 \deg(h)\ge2 deg ( h ) ≥ 2 . It therefore absorbs the polynomial loss from b k = Θ h ( k ) b_k=\Theta_h(k) b k = Θ h ( k ) and the constants in (110) , yielding (108) . By (107) , the exact communication cost is at least Ω ( b k deg ( h ) k ) \Omega(b_k\deg(h)^k) Ω ( b k deg ( h ) k ) .
A quantitative bound at exponent two. Use W n = h n ∘ d n \mathcal{W}_n=h_n^{\circ d_n} W n = h n ∘ d n from Theorem 9.3 , and let W n = I W n , b n \mathcal{W}_n=I_{W_n,b_n} W n = I W n , b n with b n = ⌈ c log 2 ( v n d n + 1 ) ⌉ b_n=\lceil c\log_2(v_n^{d_n}+1)\rceil b n = ⌈ c log 2 ( v n d n + 1 )⌉ . As n ≤ v n ≤ n p n\le v_n\le n^p n ≤ v n ≤ n p , the block length is b n = Θ ( d n log n ) b_n=\Theta(d_n\log n) b n = Θ ( d n log n ) . Applying Lemma 11.4 to (89) gives
R 1 / 3 c c ( W n ) ≥ b n ρ n 2 d n exp ( − O ( log n ) ) , q n ≤ b n ρ n d n exp ( O ( log n ) ) . R^{\mathrm{cc}}_{1/3}(\mathcal{W}_n)\ge b_n\rho_n^{2d_n}\exp(-O(\log n)),\qquad q_n\le b_n\rho_n^{d_n}\exp(O(\log n)). R 1/3 cc ( W n ) ≥ b n ρ n 2 d n exp ( − O ( log n )) , q n ≤ b n ρ n d n exp ( O ( log n )) .
The factor b n b_n b n is polynomial in log n \log n log n , so these estimates give R 1 / 3 c c ( W n ) ≥ q n 2 exp ( − O ( log n ) ) R^{\mathrm{cc}}_{1/3}(\mathcal{W}_n)\ge q_n^2\exp(-O(\log n)) R 1/3 cc ( W n ) ≥ q n 2 exp ( − O ( log n )) . Equation (107) gives q n = Ω ( b n n d n ) q_n=\Omega(b_nn^{d_n}) q n = Ω ( b n n d n ) . Together with the upper bound, this yields log q n = Θ ( d n log n ) \log q_n=\Theta(d_n\log n) log q n = Θ ( d n log n ) and hence log n = O ( log q n log log q n ) \log n=O(\sqrt{\log q_n\log\log q_n}) log n = O ( log q n log log q n ) . This proves (109) . □
Comparison with earlier work
Anshu et al. [6 Theorem 2] established a separation of exponent 3 / 2 3/2 3/2 between randomized and exact quantum communication complexity for total functions, improving Ambainis’s earlier exponent of approximately 1.15 1.15 1.15 [4 ] . Their exact quantum upper bound also requires no prior entanglement. Theorem 11.5 attains every fixed exponent below two. The new ingredient is the exact query algorithm for the recursive cheat-sheet family; randomized lifting transfers its classical lower bound, and exact query simulation transfers its quantum upper bound.
For the balanced family, (103) gives the exponent-$3/2 comparison with an explicit loss and a matching upper exponent. For the cheat-sheet family, (109) quantifies the loss at exponent two.
Conclusion and open problems
The composition algorithm uses polynomial degree to bound the cost of correcting approximate inner computations. Its degree-dependent error threshold leads to exact algorithms for recursive functions whose exponential rate is determined by degree and the general adversary bound. The transfer principles then turn inequalities for individual gadgets into universal exact-query bounds, while the explicit constructions separate exact quantum complexity from sensitivity measures and from randomized complexity.
Two sources of loss remain in the algorithms. First, the exact correction reads selected inner blocks in full. Second, balancing the recursive costs introduces an overhead beyond the optimal exponential rate. Understanding whether the first loss can be removed would also clarify the second.
Implementing the correction through an exact inner algorithm. Both composition proofs pay m m m queries for each selected inner block. It is natural to ask whether this cost can be replaced by Q E ( g ) Q_E(g) Q E ( g ) .
Conjecture 12.1 (Composition with an exact inner correction). There is an absolute constant C C C such that every pair of nonconstant total Boolean functions f f f and g g g satisfies
Q E ( f ∘ g ) ≤ C ( deg ( f ) Q E ( g ) + Q E ( f ) Q 1 / ( 4 deg ( f ) ) ( g ) ) . Q_E(f \circ g) \le C\left(\deg(f)Q_E(g)+Q_E(f)Q_{1/(4\deg(f))}(g)\right). Q E ( f ∘ g ) ≤ C ( deg ( f ) Q E ( g ) + Q E ( f ) Q 1/ ( 4 d e g ( f )) ( g ) ) .
The obstacle is specific. In the first construction, the normalized residual depends on the error probability of the approximate inner algorithm. In the interpolation construction, the correction operators also depend on its error state. An exact algorithm for g g g supplies the correct Boolean answer, but this does not immediately implement either of these corrections with O ( Q E ( g ) ) O(Q_E(g)) O ( Q E ( g )) queries. A proof of the conjecture must implement the required correction more efficiently or replace it with a different construction.
Removing the recursive overhead. For a fixed gadget h h h , we proved Q E ( h ∘ k ) = O ~ h ( R ( h ∘ k ) 2 ) Q_E(h^{\circ k})=\widetilde{O}_h(R(h^{\circ k})^2) Q E ( h ∘ k ) = O h ( R ( h ∘ k ) 2 ) . The logarithmic factor is unnecessary when deg ( h ) < Adv ± ( h ) 2 \deg(h)<\operatorname{Adv}^{\pm}(h)^2 deg ( h ) < Adv ± ( h ) 2 or when deg ( h ) \deg(h) deg ( h ) equals the arity of h h h . Removing it in the remaining parameter regime is open. A uniform bound Q E ( f ) = O ( R ( f ) 2 ) Q_E(f)=O(R(f)^2) Q E ( f ) = O ( R ( f ) 2 ) for individual total functions would require an argument beyond the fixed-gadget rate identity. The simplest concrete question concerns recursive NAE.
Problem 12.2 (Tight exact complexity of recursive NAE). Does Q E ( NAE 3 ∘ k ) = Θ ( ( 3 / 2 ) k ) Q_E(\operatorname{NAE}_3^{\circ k})=\Theta((3/\sqrt{2})^k) Q E ( NAE 3 ∘ k ) = Θ (( 3/ 2 ) k ) hold?
Conjecture 12.1 would give a positive answer. We spell out this implication because it isolates a recurrence that could also be proved directly. Put F j = NAE 3 ∘ j F_j=\operatorname{NAE}_3^{\circ j} F j = NAE 3 ∘ j , E j = Q E ( F j ) E_j=Q_E(F_j) E j = Q E ( F j ) , and a = 3 / 2 a=3/\sqrt{2} a = 3/ 2 . Fix an outer depth b b b and apply the conjecture to F b ∘ F ℓ F_b\circ F_\ell F b ∘ F ℓ . Since deg ( F b ) = 2 b \deg(F_b)=2^b deg ( F b ) = 2 b and the target inner error is constant once b b b is fixed, adversary composition and error reduction give
E ℓ + b ≤ C 2 b E ℓ + B b a ℓ . E_{\ell+b}\le C2^bE_\ell+B_ba^\ell. E ℓ + b ≤ C 2 b E ℓ + B b a ℓ .
where B b B_b B b is independent of ℓ \ell ℓ . Choose b b b large enough that C 2 b < a b C2^b<a^b C 2 b < a b , which is possible because 2 < a 2<a 2 < a . For the normalized cost u j = E j / a j u_j=E_j/a^j u j = E j / a j , the recurrence becomes
u ℓ + b ≤ θ u ℓ + K b , θ = C 2 b a b < 1 , K b = B b a b . u_{\ell+b}\le\theta u_\ell+K_b,\qquad\theta=\frac{C2^b}{a^b}<1,\qquad K_b=\frac{B_b}{a^b}. u ℓ + b ≤ θ u ℓ + K b , θ = a b C 2 b < 1 , K b = a b B b .
Iterating on each residue class modulo b b b bounds u j u_j u j by a geometric series. This gives E j = O ( a j ) E_j=O(a^j) E j = O ( a j ) , matching the adversary lower bound. Thus proving the displayed fixed-depth recurrence would already settle the question for NAE, without resolving the full composition conjecture.
The sensitivity exponent and its endpoint.
Problem 12.3 (Improving the sensitivity separation). Can one find a family with s ( f ) = Q E ( f ) α − o ( 1 ) s(f) = Q_E(f)^{\alpha-o(1)} s ( f ) = Q E ( f ) α − o ( 1 ) for some α > 3 / 2 \alpha> 3/2 α > 3/2 ? Can the present family attain s ( f ) = Ω ~ ( Q E ( f ) 3 / 2 ) s(f) = \widetilde{\Omega}(Q_E(f)^{3/2}) s ( f ) = Ω ( Q E ( f ) 3/2 ) , or even s ( f ) = Ω ( Q E ( f ) 3 / 2 ) s(f) = \Omega(Q_E(f)^{3/2}) s ( f ) = Ω ( Q E ( f ) 3/2 ) ?
The first question asks for a larger exponent; the second asks whether the overhead in the current exponent-3/2 construction can be removed. The transfer theorem gives a finite-function formulation of the first question’s universal-bound counterpart:
s ( F ) = O ( Q E ( F ) 3 / 2 ) for all F ⟺ fbs ( f ) ≤ max { deg ( f ) , Adv ± ( f ) } 3 / 2 for all f . s(F) = O(Q_E(F)^{3/2})\text{ for all }F \qquad\Longleftrightarrow\qquad\operatorname{fbs}(f) \le\max\{\operatorname{deg}(f), \operatorname{Adv}^{\pm}(f)\}^{3/2}\text{ for all }f. s ( F ) = O ( Q E ( F ) 3/2 ) for all F ⟺ fbs ( f ) ≤ max { deg ( f ) , Adv ± ( f ) } 3/2 for all f .
A gadget violating the right-hand inequality would therefore yield a stronger asymptotic separation. A sharper quantitative upper bound on the exact algorithm for G k G_k G k could improve the loss in (79) . For the randomized separations, an analogous question is whether a fixed power of a logarithm can replace the denominators in (88) and (109) .