Introduction
Context and motivations
Property testing In this era of big data, even just reading the input in its entirety can be prohibitively costly. However, from a practical perspective, we can often tolerate some sort of approximation. The field of property testing focuses on such a setting: here the goal is to distinguish whether the input object (in this work a function or a graph) satisfies some property of interest, or is far from all such objects under some suitable distance measure, by accessing the input as few times as possible. The tester can either accept or reject when the distance of the input from the property does not satisfy the condition. Perhaps surprisingly, it is often possible to design testers whose complexity scales sublinearly with the size of the input. Over the last two and a half decades, property testing has become a vast and active area of research, see [25 , 13 Ron09, 19 RS11, 15 , 16 ] for more details.
Property testing has naturally also been explored in the quantum setting [24 , 10 ] . For several important problems such as junta testing, graph isomorphism, bipartiteness and expansion testing, polynomial quantum speedups are known [2 , 1 , 3 , 14 ] , see the survey [31 ] for a detailed discussion. Naturally, understanding the limit of quantum advantage has been a prime focus in the community.
Our starting point is a function f : [ N ] → [ N ] f : [N] \to[N] f : [ N ] → [ N ] [ N ] = { 1 , … , N } [N] = \{1,\ldots,N\} [ N ] = { 1 , … , N } P \mathcal{P} P ε \varepsilon ε P \mathcal{P} P ε N \varepsilon N εN P \mathcal{P} P f f f ε \varepsilon ε f ∈ P f \in\mathcal{P} f ∈ P ε \varepsilon ε P \mathcal{P} P 2 / 3 2/3 2/3 f f f f ( i ) f(i) f ( i ) i ∈ [ N ] i \in[N] i ∈ [ N ] f f f
Many natural properties of interest, such as injectivity, the absence of k k k
c y = ∣ { i ∈ [ N ] : f ( i ) = y } ∣ , c_y = |\{i \in[N] : f(i) = y\}|, c y = ∣ { i ∈ [ N ] : f ( i ) = y } ∣ , the image size of f f f y y y c y > 0 c_y > 0 c y > 0 f f f k k k c y ≥ k c_y \ge k c y ≥ k c = ( c 1 , c 2 , … ) \mathbf{c} = (c_1,c_2,\ldots) c = ( c 1 , c 2 , … ) frequency vector of f f f symmetric or label-invariant properties and play an important role in both classical and quantum property testing, and have been extensively studied in the literature, see [Val11, VV11, VV17, WY19, CFG+25] and the references therein.
Since these symmetric properties only depend on the multiplicities of the output labels, a natural approach to prove lower bounds for such properties is to consider hard instances based on frequencies and then randomize the positions and labels. Thus the task is to construct two hard input instances (or distributions of instances), one in the property P \mathcal{P} P P \mathcal{P} P
Moment-matching method Moment-matching method is a powerful classical framework that is used to achieve this dichotomy. In general, for some symmetric property P \mathcal{P} P P \mathcal{P} P P \mathcal{P} P ( r − 1 ) (r-1) ( r − 1 ) r r r Ω ( N 1 − 1 / r ) \Omega(N^{1-1/r}) Ω ( N 1 − 1/ r ) f 0 : [ N ] → [ N ] f_0 : [N] \to[N] f 0 : [ N ] → [ N ] f 1 : [ N ] → [ N ] f_1 : [N] \to[N] f 1 : [ N ] → [ N ] Y Y Y [ N ] [N] [ N ] Z b = ∣ f b − 1 ( Y ) ∣ Z_b = |f_b^{-1}(Y)| Z b = ∣ f b − 1 ( Y ) ∣ b ∈ { 0 , 1 } b \in\{0,1\} b ∈ { 0 , 1 } Z 0 = 1 Z_0 = 1 Z 0 = 1 Z 1 Z_1 Z 1 Ω ( N 1 − 1 / 2 ) \Omega(N^{1-1/2}) Ω ( N 1 − 1/2 )
The intuition for this framework stems from the fact that since P \mathcal{P} P moments are all that matter . One can alternatively define X 0 X_0 X 0 X 1 X_1 X 1 Y Y Y f ( [ N ] ) f([N]) f ([ N ]) Y 0 = 1 Y_0 = 1 Y 0 = 1 Y 1 = 2 Y_1 = 2 Y 1 = 2 Z 0 , Z 1 Z_0, Z_1 Z 0 , Z 1 X 0 , X 1 X_0, X_1 X 0 , X 1
The classical moment matching framework was introduced in the seminal work of [RRSS09], where the authors used this framework to prove lower bounds on estimating the support size and the entropy of a distribution, and the number of distinct elements in a sequence. Then [VV11] extended this framework to approximately matching moments and proved lower bounds on various distribution testing problems such as distance estimation. Later, Wu and Yang [WY19] connected the matching moments framework to polynomial approximation and obtained sharp bounds for entropy and support-size estimation. Since then, there have been a flurry of results in the context of proving distribution testing lower bounds that employ this framework [4 , 18 , 21 , 26 , 20 ] . The same framework was used to prove a k k k [28 ] for k = 3 k = 3 k = 3 k k k [33 ] , which they transfer to directed subgraph-freeness via a reduction.
Notably, there are two important ingredients of this framework: (i) when using it, one has to construct suitable random variables so that the framework can be applied; and (ii) the proof of the framework provides that no algorithm can reliably distinguish them by performing only a few queries. While these series of works use different input instance constructions and moment conditions, all of these proofs use the Poissonization trick : instead of considering a fixed number of samples, taking a set of samples distributed according to the Poisson distribution makes the frequencies of different symbols independent, thereby greatly simplifying the proofs.
Toward a quantum analogue Due to the wide success of this framework and its simplicity to use in practice for proving new lower bounds, it was naturally considered whether a similar lower bound framework exists for the quantum query model. Ambainis, Belovs, Regev, and de Wolf [1 ] were the first to propose whether combining the construction of [RRSS09] with quantum lower-bound techniques could be used to obtain stronger bounds for junta testing [1 ] . Without answering directly to this question, several problems, for which the moment matching frameworks can be applied classically, were studied in the quantum setting using mostly the dual polynomial method and quite involved mathematical constructions. First, improved lower bounds for junta testing and several other important problems, like image size testing, were achieved in a subsequent work [11 ] . Later on, [AMS25] establishes lower bounds for collision-freeness and directed subgraph-freeness testing, which was later extended by [PW27]. Thus, quantum lower bounds of some specific problems were tackled, but not directly the general matching moments method. We now briefly discuss the bottleneck.
Recall that the second ingredient of matching-moments-based lower bound proofs is to prove indistinguishability : a classical algorithm that performs too few queries cannot reliably distinguish between the two hard distributions. Since the use of Poissonization makes the number of occurrences of every label independent, it allows to compare the histogram distributions based on the input distributions. Since the property is symmetric, the algorithm’s decision depends only on this histogram. Consequently, if two histogram distributions are close in total variation distance, no algorithm making only a few queries can distinguish them with high probability.
However, a quantum algorithm can query several indices of the input in superposition, without measuring the answer register after each query. In fact, measuring the outcome of each query can remove coherence used by subsequent queries and thereby change the algorithm’s acceptance probability. Thus, even for symmetric properties, a quantum query algorithm cannot be analyzed by merely processing a classical histogram constructed from its samples. A quantum moment-matching argument must therefore control what coherent queries can distinguish, which has not been studied in the literature. Thus, despite a long series of works, the following question remained wide open:
Does there exist a quantum moment matching framework for proving quantum query lower bounds?
Our results
In this work, we answer the above question in the affirmative:
There exists a quantum moment matching framework for proving quantum query lower bounds.
We prove that indeed such a general lower bound framework exists in the quantum query realm, transferring each corresponding classical bound Ω ( N 1 − 1 / r ) \Omega(N^{1-1/r}) Ω ( N 1 − 1/ r ) O ( N 1 / 2 − 1 / ( 2 r ) ) O(N^{1/2-1/(2r))} O ( N 1/2 − 1/ ( 2 r )) Ω ( N 1 / 2 − 1 / ( 2 ( 2 r − 1 ) ) ) \Omega(N^{1/2-1/(2(2^{r-1}))}) Ω ( N 1/2 − 1/ ( 2 ( 2 r − 1 )) )
Quantum analogue of classical moment matching framework We provide two variants of the moment matching theorem: the first one works for a large range of parameters, useful for broader applicability, whereas the second one, while restricted to smaller parameter ranges, yields better bounds on several problems of interest. Let us start with the first variant of our quantum moment matching framework.
In both theorems, we start as in the classical setting. Fix an integer A ≥ 1 A \ge1 A ≥ 1 X 0 , X 1 X_0, X_1 X 0 , X 1 [ A ] [A] [ A ] r ≥ 2 r \ge2 r ≥ 2
E [ X 1 ] E [ X 0 ] = E [ X 1 2 ] E [ X 0 2 ] = ⋯ = E [ X 1 r − 1 ] E [ X 0 r − 1 ] . (1) \frac{\mathbb{E}[X_1]}{\mathbb{E}[X_0]} = \frac{\mathbb{E}[X_1^2]}{\mathbb{E}[X_0^2]} = \cdots= \frac{\mathbb{E}[X_1^{r-1}]}{\mathbb{E}[X_0^{r-1}]}. \tag*{(1)} E [ X 0 ] E [ X 1 ] = E [ X 0 2 ] E [ X 1 2 ] = ⋯ = E [ X 0 r − 1 ] E [ X 1 r − 1 ] . (1) These random variables refer to the statistics of the frequency vector of any candidate function in the hard distributions. Indeed from them, and any given integer N ≥ 1 N \ge1 N ≥ 1 Π 0 , N \Pi_{0,N} Π 0 , N Π 1 , N \Pi_{1,N} Π 1 , N X 0 X_0 X 0 X 1 X_1 X 1 f : [ N ] → [ N ] f : [N] \to[N] f : [ N ] → [ N ]
Theorem 1.1 (Informal statement of Theorem 2.5 ). *Assume that X 0 , X 1 X_0, X_1 X 0 , X 1 (1) . When A = O ( r 2 ) A = O(r^2) A = O ( r 2 ) A = o ( N / log N ) A = o(\sqrt{N/\log N}) A = o ( N / log N ) T T T Π 0 , N \Pi_{0,N} Π 0 , N Π 1 , N \Pi_{1,N} Π 1 , N 2 / 3 2/3 2/3 T = Ω ( N 1 / 2 − 1 / ( 2 r ) ) T = \Omega(N^{1/2-1/(2r)}) T = Ω ( N 1/2 − 1/ ( 2 r ) )
Note that the above result gives a quadratic decrease in the lower bound compared to the classical setting, reflecting the possibility of quantum speedups. The above theorem is similar to the matching moment theorem of [RRS509], and it holds for a large range of parameters A A A r r r Theorem 2.5 for the exact ranges of the parameters). We employ this theorem to prove optimal quantum query lower bounds on image size testing and junta testing.
However, for several properties like k k k
Theorem 1.2 (Informal statement of Theorem 2.6 ). Assume that X 0 , X 1 X_0,X_1 X 0 , X 1 satisfy Equation (1) . For fixed A , r A,r A , r any T T T query quantum algorithm can only distinguish between Π 0 , N \Pi_{0,N} Π 0 , N and Π 1 , N \Pi_{1,N} Π 1 , N with probability at least 2 / 3 2/3 2/3 whenever T = Ω ( N 1 / 2 − 1 / ( 2 ( 2 r − 1 ) ) ) T=\Omega(N^{1/2-1/(2(2r-1))}) T = Ω ( N 1/2 − 1/ ( 2 ( 2 r − 1 )) )
A crucial appeal of this framework lies in its simplicity for proving new quantum query lower bounds. These theorems can be used as black-box : all it needs is input instances that satisfy the conditions of the theorems, and we directly obtain a new quantum query lower bound! This is indeed the case of various applications. In fact, in many cases, it is sufficient to consider the classical moment-matching lower bound construction, and even designing new hard instances is not required.
Applications of the quantum moment matching framework As applications of our two moment matching theorems, we obtain several new quantum query lower bounds, even optimal ones, with either polynomial or logarithmic improvements. Moreover, all these lower bounds are now proven in a more direct and streamlined fashion. Our results are summarized in Table 1 .
Table 1. Query bounds for our applications, with explicit logarithmic factors, a k = ( 2 k − 1 − 1 ) / ( 2 k − 1 ) a_k=(2^{k-1}-1)/(2^k-1) a k = ( 2 k − 1 − 1 ) / ( 2 k − 1 ) k k k k ≥ 3 k\geq3 k ≥ 3 δ > 0 \delta>0 δ > 0
While Theorem 1.2 proves a sharper lower bound compared to Theorem 1.1 , as we mentioned, Theorem 1.2 holds for smaller parameter ranges. For our applications of image size testing and junta testing, applying Theorem 1.2 would not yield optimal lower bounds and Theorem 1.1 needs to be applied. On the other hand, for k k k k k k Theorem 1.2 is required for proving the optimal bounds. Thus, Theorem 1.1 and Theorem 1.2 are incomparable from an application standpoint.
We start with the k k k f : [ N ] → [ M ] f:[N]\to[M] f : [ N ] → [ M ] f f f k k k ε N \varepsilon N εN k k k unidirectional model , where the algorithm can only query the outgoing neighbors of each vertex. The first two problems are testing k k k k k k k k k k k k § 5.2.2 for the definition). Then, we consider planarity and outerplanarity testing: given query access to a graph in the unidirectional model, the algorithm has to distinguish whether the underlying undirected graph is planar or outerplanar , or far from being so. Our results for these problems are summarized in the following theorem, see Table 1 for the best prior classical and quantum bounds.
Theorem 1.3 (Informal statement of Corollary 5.1 and Corollary 5.2 ). The quantum query complexity of property testing:
(i) k k k N N N Ω ( N ( 2 k − 1 ) / ( 2 k − 1 ) ) \Omega(N^{(2^{k-1})/(2^k-1)}) Ω ( N ( 2 k − 1 ) / ( 2 k − 1 ) )
(ii) k k k k k k N N N Ω ( N ( 2 k − 1 − 1 ) / ( 2 k − 1 ) ) \Omega(N^{(2^{k-1}-1)/(2^k-1)}) Ω ( N ( 2 k − 1 − 1 ) / ( 2 k − 1 ) )
(iii) planarity and outerplanarity of N N N Ω ( N 3 / 7 ) \Omega(N^{3/7}) Ω ( N 3/7 )
Suppose we are given query access to a function f : [ N ] → [ M ] f:[N]\to[M] f : [ N ] → [ M ] image size testing problem, our goal is to distinguish whether f f f K K K f f f K K K N N N
Theorem 1.4 (Informal statements of Corollaries 5.5 and 5.7 ). The quantum query complexity of
(i) Image size testing for strings of length N N N Ω ( N ) \Omega(\sqrt{N}) Ω ( N )
(ii) K K K Ω ( K ) \Omega(\sqrt{K}) Ω ( K )
The best known prior classical and quantum bounds on these problems are presented in Table 1 . A detailed discussion of techniques and prior works on these applications is presented in § 5 .
Technical overview
We first give an overview of the proof of Theorem 1.1 , then move to Theorem 1.2 . Our proofs combine the polynomial method with a continuous hybrid argument. We express acceptance probabilities as polynomials and use the hybrid argument to compare their expectations under the hard input distributions.
Polynomial and discrete hybrid arguments have previously been combined, for instance in Zhandry’s construction of quantum-secure pseudorandom functions [Zha21], but not so often applied since. Here, continuous interpolation preserves the i.i.d. structure of our multiple samples, while moment matching cancels the low-degree contributions at each stage.
First step: input distributions
We start with two random variables X 0 , X 1 X_0, X_1 X 0 , X 1 [ A ] = { 1 , … , A } [A] = \{1, \ldots, A\} [ A ] = { 1 , … , A } positive frequency statistics and have proportional moments up to order r − 1 r - 1 r − 1 μ b = E [ X b ] \mu_b = \mathbb{E}[X_b] μ b = E [ X b ] b ∈ { 0 , 1 } b \in\{0, 1\} b ∈ { 0 , 1 } X b X_b X b Z b Z_b Z b X b X_b X b 1 / μ b 1/\mu_b 1/ μ b Z b Z_b Z b S = { 0 } ∪ [ A ] S = \{0\} \cup[A] S = { 0 } ∪ [ A ]
E [ Z b ] = 1 , E [ Z b j ] = E [ X b j ] μ b , E [ Z 0 j ] = E [ Z 1 j ] ( 1 ≤ j < r ) . \mathbb{E}[Z_b] = 1,\qquad\mathbb{E}[Z_b^j] = \frac{\mathbb{E}[X_b^j]}{\mu_b},\qquad\mathbb{E}[Z_0^j] = \mathbb{E}[Z_1^j]\quad(1 \le j < r). E [ Z b ] = 1 , E [ Z b j ] = μ b E [ X b j ] , E [ Z 0 j ] = E [ Z 1 j ] ( 1 ≤ j < r ) . The additional zero value is crucial, it lets us obtain mean one while converting proportional moments into matching moments.
For b ∈ { 0 , 1 } b \in\{0,1\} b ∈ { 0 , 1 } X b X_b X b Z b Z_b Z b π b \pi_b π b Z b Z_b Z b f f f f f f π b \pi_b π b f : [ N ] → [ N ] f : [N] \to[N] f : [ N ] → [ N ] N N N π b \pi_b π b
To overcome this issue, we will use a randomized variant of the frequency construction of [RRSS09] to define Π b , N \Pi_{b,N} Π b , N m = ⌊ N / 2 ⌋ m = \lfloor N/2 \rfloor m = ⌊ N /2 ⌋ π b \pi_b π b
We sample m = ⌊ N / 2 ⌋ m = \lfloor N/2 \rfloor m = ⌊ N /2 ⌋ z = ( z 1 , … , z m ) \mathbf{z} = (z_1, \ldots, z_m) z = ( z 1 , … , z m ) π b \pi_b π b Z b Z_b Z b z = ∑ i z i z = \sum_i z_i z = ∑ i z i
If z ≤ N z \le N z ≤ N N − z N - z N − z singletons ) yielding multiplicity vector c \mathbf{c} c
If z > N z > N z > N c \mathbf{c} c
This gives a function on exactly N N N f ∼ D c f \sim\mathcal{D}_{\mathbf{c}} f ∼ D c D c \mathcal{D}_{\mathbf{c}} D c c \mathbf{c} c Π b , N \Pi_{b,N} Π b , N f ∼ Π b , N f \sim\Pi_{b,N} f ∼ Π b , N A \mathcal{A} A Pr f ∼ Π b , N [ A f = 1 ] \Pr_{f\sim\Pi_{b,N}}[\mathcal{A}^f = 1] Pr f ∼ Π b , N [ A f = 1 ]
It is important to note that our construction differs slightly from the original one of [RRSS09]. Indeed, [RRSS09] obtains independence of the frequency statistics of the observed values, rather than of the input multiplicities. For this, they use a Poissonization argument: instead of taking T T T T T T Poisson ( T ) \operatorname{Poisson}(T) Poisson ( T )
Second step: forming the acceptance probability polynomial
Our main goal is to show that any quantum algorithm that performs few queries has almost the same acceptance probability under the two input distributions whose moments match up to r − 1 r-1 r − 1 polynomial method , i.e., the fact that the acceptance probability of a T T T 2 T 2T 2 T [8 ] .
Averaging over the random assignments of positions and labels gives a symmetric polynomial P P P 2 T 2T 2 T Lemma 3.1 gives
P ( c ) = Pr f ∼ D c [ A f = 1 ] ∈ [ 0 , 1 ] (2) P(\mathbf{c})=\Pr_{f\sim\mathcal{D}_{\mathbf{c}}}\left[\mathcal{A}^{f}=1\right]\in[0,1] \tag*{(2)} P ( c ) = f ∼ D c Pr [ A f = 1 ] ∈ [ 0 , 1 ] (2) for every feasible frequency vector c \mathbf{c} c c ( z ) \mathbf{c}(\mathbf{z}) c ( z ) z \mathbf{z} z
Pr f ∼ Π b , N [ A f = 1 ] = E z ∼ π b ⊗ m [ P ( c ( z ) ) ] . \Pr_{f\sim\Pi_{b,N}}\left[\mathcal{A}^{f}=1\right]=\mathbb{E}_{\mathbf{z}\sim\pi_b^{\otimes m}}\left[P(\mathbf{c}(\mathbf{z}))\right]. f ∼ Π b , N Pr [ A f = 1 ] = E z ∼ π b ⊗ m [ P ( c ( z )) ] . Symmetry means that permuting the entries of c \mathbf{c} c P ( c ) P(\mathbf{c}) P ( c ) P P P p j ( c ) = ∑ a = 1 N c a j p_j(\mathbf{c})=\sum_{a=1}^{N}c_a^j p j ( c ) = ∑ a = 1 N c a j z \mathbf{z} z
However, we assume that Z 0 Z_0 Z 0 Z 1 Z_1 Z 1 r − 1 r-1 r − 1 P P P 2 T 2T 2 T T T T r r r
The main idea is therefore to use a hybrid argument, changing the distribution of one sampled multiplicity at a time, and approximate the acceptance probability, as a function of that multiplicity with the others fixed, by a polynomial of degree below r r r π 0 \pi_0 π 0 π 1 \pi_1 π 1
Third step: using the hybrid argument
We now describe the hybrid argument to analyze the success probability of any given algorithm against two different input distributions. Recall that c ( z ) \mathbf{c}(\mathbf{z}) c ( z ) z \mathbf{z} z ∑ i z i > N \sum_i z_i>N ∑ i z i > N S = { 0 } ∪ [ A ] S=\{0\}\cup[A] S = { 0 } ∪ [ A ] h : S m → [ 0 , 1 ] h:S^m\to[0,1] h : S m → [ 0 , 1 ]
h ( z ) = P ( c ( z ) ) = Pr f ∼ D c ( z ) [ A f = 1 ] . h(\mathbf{z})=P(\mathbf{c}(\mathbf{z}))=\Pr_{f\sim\mathcal{D}_{\mathbf{c}(\mathbf{z})}}\left[\mathcal{A}^{f}=1\right]. h ( z ) = P ( c ( z )) = f ∼ D c ( z ) Pr [ A f = 1 ] . Thus h ( z ) h(\mathbf{z}) h ( z ) z \mathbf{z} z z \mathbf{z} z c ( z ) \mathbf{c}(\mathbf{z}) c ( z ) P P P h h h
Pr f ∼ Π b , N [ A f = 1 ] = E z ∼ π b ⊗ m [ h ( z ) ] . \Pr_{f\sim\Pi_{b,N}}\left[\mathcal{A}^{f}=1\right]=\mathbb{E}_{\mathbf{z}\sim\pi_b^{\otimes m}}\left[h(\mathbf{z})\right]. f ∼ Π b , N Pr [ A f = 1 ] = E z ∼ π b ⊗ m [ h ( z ) ] . For two probability distributions π 0 \pi_0 π 0 π 1 \pi_1 π 1 S S S
H i = E z ∼ π 1 ⊗ i ⊗ π 0 ⊗ ( m − i ) [ h ( z ) ] ( 0 ≤ i ≤ m ) . H_i = \mathbb{E}_{z\sim\pi_1^{\otimes i}\otimes\pi_0^{\otimes(m-i)}}[h(z)] \quad(0\le i\le m). H i = E z ∼ π 1 ⊗ i ⊗ π 0 ⊗ ( m − i ) [ h ( z )] ( 0 ≤ i ≤ m ) . Define q w ( s ) = h ( w , s ) q_{\mathbf{w}}(s)=h(\mathbf{w},s) q w ( s ) = h ( w , s ) w ∈ S m − 1 \mathbf{w}\in S^{m-1} w ∈ S m − 1 s ∈ S s\in S s ∈ S H m − H 0 H_m-H_0 H m − H 0 π 0 \pi_0 π 0 π 1 \pi_1 π 1
The usual hybrid changes one coordinate at each step and telescopes H m − H 0 = ∑ i = 0 m − 1 ( H i + 1 − H i ) H_m-H_0=\sum_{i=0}^{m-1}(H_{i+1}-H_i) H m − H 0 = ∑ i = 0 m − 1 ( H i + 1 − H i )
H i + 1 − H i = E w ∼ π 1 ⊗ i ⊗ π 0 ⊗ ( m − 1 − i ) [ ∑ s ∈ S ( π 1 ( s ) − π 0 ( s ) ) q w ( s ) ] . H_{i+1}-H_i=\mathbb{E}_{\mathbf{w}\sim\pi_1^{\otimes i}\otimes\pi_0^{\otimes(m-1-i)}}\left[\sum_{s\in S}(\pi_1(s)-\pi_0(s))q_{\mathbf{w}}(s)\right]. H i + 1 − H i = E w ∼ π 1 ⊗ i ⊗ π 0 ⊗ ( m − 1 − i ) [ s ∈ S ∑ ( π 1 ( s ) − π 0 ( s )) q w ( s ) ] . For the formal proof we use a continuous version of this argument in Lemma 3.7 , where ( π u ) 0 ≤ u ≤ 1 (\pi_u)_{0\le u\le1} ( π u ) 0 ≤ u ≤ 1 π 0 \pi_0 π 0 π 1 \pi_1 π 1 F ( u ) = E z ∼ π u ⊗ m [ h ( z ) ] F(u)=\mathbb{E}_{z\sim\pi_u^{\otimes m}}[h(z)] F ( u ) = E z ∼ π u ⊗ m [ h ( z )] π ˙ u ( s ) = d d u π u ( s ) \dot{\pi}_u(s)=\frac{d}{du}\pi_u(s) π ˙ u ( s ) = d u d π u ( s )
∣ H m − H 0 ∣ = ∣ F ( 1 ) − F ( 0 ) ∣ ≤ ∫ 0 1 ∣ F ′ ( u ) ∣ d u = m ∫ 0 1 E w ∼ π u ⊗ ( m − 1 ) [ ∣ ∑ s ∈ S π ˙ u ( s ) q w ( s ) ∣ ] d u . (3) \lvert H_m-H_0\rvert=\lvert F(1)-F(0)\rvert\le\int_0^1\lvert F'(u)\rvert\,du=m\int_0^1\mathbb{E}_{\mathbf{w}\sim\pi_u^{\otimes(m-1)}}\left[\left\lvert\sum_{s\in S}\dot{\pi}_u(s)q_{\mathbf{w}}(s)\right\rvert\right]\,du. \tag*{(3)} ∣ H m − H 0 ∣ = ∣ F ( 1 ) − F ( 0 )∣ ≤ ∫ 0 1 ∣ F ′ ( u )∣ d u = m ∫ 0 1 E w ∼ π u ⊗ ( m − 1 ) [ s ∈ S ∑ π ˙ u ( s ) q w ( s ) ] d u . (3) Then the RHS is upper bounded by ∑ i = 0 m − 1 ∣ H i + 1 − H i ∣ \sum_{i=0}^{m-1}\lvert H_{i+1}-H_i\rvert ∑ i = 0 m − 1 ∣ H i + 1 − H i ∣ π u = ( 1 − u ) π 0 + u π 1 \pi_u=(1-u)\pi_0+u\pi_1 π u = ( 1 − u ) π 0 + u π 1
The advantage of the continuous formulation is that the remaining multiplicities w \mathbf{w} w π u \pi_u π u s ∈ S s\in S s ∈ S w \mathbf{w} w s s s Bin ( m − 1 , π u ( s ) ) \operatorname{Bin}(m-1,\pi_u(s)) Bin ( m − 1 , π u ( s )) H i + 1 − H i H_{i+1}-H_i H i + 1 − H i π 1 \pi_1 π 1 π 0 \pi_0 π 0 q w q_{\mathbf{w}} q w
Fourth step: using the matching moments
Bringing back the degree bound In the rest of this overview, we only consider samples w ∈ S m − 1 \mathbf{w}\in S^{m-1} w ∈ S m − 1 w = ∑ i = 1 m − 1 w i ≤ 3 N 4 w=\sum_{i=1}^{m-1}w_i\le\frac{3N}{4} w = ∑ i = 1 m − 1 w i ≤ 4 3 N
For every integer 0 ≤ s ≤ H = ⌊ N / 4 ⌋ 0\le s\le H=\lfloor N/4\rfloor 0 ≤ s ≤ H = ⌊ N /4 ⌋ w + s ≤ N w+s\le N w + s ≤ N § 1.3.1 does not overflow and the resulting frequency vector c ( w , s ) \mathbf{c}(\mathbf{w},s) c ( w , s ) s s s ( N − w − s ) (N-w-s) ( N − w − s ) w \mathbf{w} w j j j
p j ( c ( w , s ) ) = p j ( w ) + ( N − w − s ) + s j . p_j(\mathbf{c}(\mathbf{w},s))=p_j(\mathbf{w})+(N-w-s)+s^j. p j ( c ( w , s )) = p j ( w ) + ( N − w − s ) + s j . Since we start with a polynomial P P P c \mathbf{c} c (2) , the function q w ( s ) q_{\mathbf{w}}(s) q w ( s ) s s s P P P [ 0 , 1 ] [0,1] [ 0 , 1 ] 0 ≤ s ≤ H 0\le s\le H 0 ≤ s ≤ H
Matching moments Since q w ( s ) q_{\mathbf{w}}(s) q w ( s ) 2 T 2T 2 T s s s Q w ( s ) Q_{\mathbf{w}}(s) Q w ( s ) r − 1 r-1 r − 1 Q w Q_{\mathbf{w}} Q w (3) . Indeed, since π 0 \pi_0 π 0 π 1 \pi_1 π 1 r r r π u \pi_u π u π v \pi_v π v u , v ∈ [ 0 , 1 ] u,v\in[0,1] u , v ∈ [ 0 , 1 ] ∑ s ∈ S π u ( s ) Q w ( s ) \sum_{s\in S}\pi_u(s)Q_{\mathbf{w}}(s) ∑ s ∈ S π u ( s ) Q w ( s ) u u u Lemma 3.4 ). Therefore ∑ s ∈ S π ˙ u ( s ) Q w ( s ) = 0 \sum_{s\in S}\dot{\pi}_u(s)Q_{\mathbf{w}}(s)=0 ∑ s ∈ S π ˙ u ( s ) Q w ( s ) = 0
∑ s ∈ S π ˙ u ( s ) q w ( s ) = ∑ s ∈ S π ˙ u ( s ) ( q w ( s ) − Q w ( s ) ) . \sum_{s\in S}\dot{\pi}_u(s)q_{\mathbf{w}}(s)=\sum_{s\in S}\dot{\pi}_u(s)\bigl(q_{\mathbf{w}}(s)-Q_{\mathbf{w}}(s)\bigr). s ∈ S ∑ π ˙ u ( s ) q w ( s ) = s ∈ S ∑ π ˙ u ( s ) ( q w ( s ) − Q w ( s ) ) . As a consequence we get this special case of Lemma 3.8 :
∣ F ( 1 ) − F ( 0 ) ∣ ≤ m ∫ 0 1 E w ∼ π u ⊗ ( m − 1 ) [ ∣ ∑ s ∈ S π ˙ u ( s ) ( q w ( s ) − Q w ( s ) ) ∣ ] d u . |F(1)-F(0)| \le m \int_{0}^{1} \mathbb{E}_{\mathbf{w}\sim\pi_u^{\otimes(m-1)}}\left[\left|\sum_{s\in S}\dot{\pi}_u(s)(q_{\mathbf{w}}(s)-Q_{\mathbf{w}}(s))\right|\right]\,du. ∣ F ( 1 ) − F ( 0 ) ∣ ≤ m ∫ 0 1 E w ∼ π u ⊗ ( m − 1 ) [ s ∈ S ∑ π ˙ u ( s ) ( q w ( s ) − Q w ( s )) ] d u . Combining small degree and matching moments In the regime N ≥ max { 8 , 4 A } N \ge\max\{8,4A\} N ≥ max { 8 , 4 A } T 2 ≤ N / 64 T^2 \le N/64 T 2 ≤ N /64 ∣ q w ( s ) − Q w ( s ) ∣ |q_{\mathbf{w}}(s)-Q_{\mathbf{w}}(s)| ∣ q w ( s ) − Q w ( s ) ∣ q w ( s ) ∈ [ 0 , 1 ] q_{\mathbf{w}}(s)\in[0,1] q w ( s ) ∈ [ 0 , 1 ] 0 ≤ s ≤ H 0\le s\le H 0 ≤ s ≤ H π b \pi_b π b
E Z b ∼ π b [ ∣ q w ( Z b ) − Q w ( Z b ) ∣ ] ≤ 2 A r − 1 ( 2 r ) ! ( 128 T 2 N ) r . \mathbb{E}_{Z_b\sim\pi_b}\left[|q_{\mathbf{w}}(Z_b)-Q_{\mathbf{w}}(Z_b)|\right]\le\frac{2A^{r-1}}{(2r)!}\left(\frac{128T^2}{N}\right)^r. E Z b ∼ π b [ ∣ q w ( Z b ) − Q w ( Z b ) ∣ ] ≤ ( 2 r )! 2 A r − 1 ( N 128 T 2 ) r . Therefore
∣ ∑ s ∈ S π ˙ u ( s ) ( q w ( s ) − Q w ( s ) ) ∣ ≤ ∑ s ∈ S ( π 0 ( s ) + π 1 ( s ) ) ∣ q w ( s ) − Q w ( s ) ∣ = ∑ b = 0 1 ∑ s ∈ S Pr [ Z b = s ] ∣ q w ( s ) − Q w ( s ) ∣ = ∑ b = 0 1 E [ ∣ q w ( Z b ) − Q w ( Z b ) ∣ ] ≤ 4 A r − 1 ( 2 r ) ! ( 128 T 2 N ) r . \begin{aligned}
\left|\sum_{s\in S}\dot{\pi}_u(s)(q_{\mathbf{w}}(s)-Q_{\mathbf{w}}(s))\right|
\le\sum_{s\in S}(\pi_0(s)+\pi_1(s))|q_{\mathbf{w}}(s)-Q_{\mathbf{w}}(s)| \\
&= \sum_{b=0}^{1}\sum_{s\in S}\Pr[Z_b=s]|q_{\mathbf{w}}(s)-Q_{\mathbf{w}}(s)| \\
&= \sum_{b=0}^{1}\mathbb{E}[|q_{\mathbf{w}}(Z_b)-Q_{\mathbf{w}}(Z_b)|] \\
&\le\frac{4A^{r-1}}{(2r)!}\left(\frac{128T^2}{N}\right)^r.
\end{aligned} s ∈ S ∑ π ˙ u ( s ) ( q w ( s ) − Q w ( s )) ≤ s ∈ S ∑ ( π 0 ( s ) + π 1 ( s )) ∣ q w ( s ) − Q w ( s ) ∣ = b = 0 ∑ 1 s ∈ S ∑ Pr [ Z b = s ] ∣ q w ( s ) − Q w ( s ) ∣ = b = 0 ∑ 1 E [ ∣ q w ( Z b ) − Q w ( Z b ) ∣ ] ≤ ( 2 r )! 4 A r − 1 ( N 128 T 2 ) r . So finally
∣ Pr f ∼ Π 1 , N [ A f = 1 ] − Pr f ∼ Π 0 , N [ A f = 1 ] ∣ = ∣ F ( 1 ) − F ( 0 ) ∣ ≤ N 2 [ 4 A r − 1 ( 2 r ) ! ( 128 T 2 N ) r ] , \left|\Pr_{f\sim\Pi_{1,N}}[\mathcal{A}^f=1]-\Pr_{f\sim\Pi_{0,N}}[\mathcal{A}^f=1]\right|=|F(1)-F(0)|\le\frac{N}{2}\left[\frac{4A^{r-1}}{(2r)!}\left(\frac{128T^2}{N}\right)^r\right], f ∼ Π 1 , N Pr [ A f = 1 ] − f ∼ Π 0 , N Pr [ A f = 1 ] = ∣ F ( 1 ) − F ( 0 ) ∣ ≤ 2 N [ ( 2 r )! 4 A r − 1 ( N 128 T 2 ) r ] , up to an additional exponential small term (bounded by 2 e − N / ( 4 A 2 ) 2e^{-N/(4A^2)} 2 e − N / ( 4 A 2 ) w ≤ 3 N / 4 w\le3N/4 w ≤ 3 N /4 A = O ( r 2 ) A=O(r^2) A = O ( r 2 ) A = o ( N / log N ) A=o(\sqrt{N/\log N}) A = o ( N / log N ) T = Ω ( N 1 / 2 − 1 / ( 2 r ) ) T=\Omega(N^{1/2-1/(2r)}) T = Ω ( N 1/2 − 1/ ( 2 r ) )
A better bound for some regimes
For proving the second theorem, we use two main lemmas: Lemma 4.2 and Lemma 4.1 . First we discuss how to prove the theorem using these lemmas and then continue with the lemmas.
As before, let π b \pi_b π b Z b Z_b Z b b ∈ { 0 , 1 } b\in\{0,1\} b ∈ { 0 , 1 } [ A ] ∪ { 0 } [A]\cup\{0\} [ A ] ∪ { 0 } ∥ π 1 − π 0 ∥ 1 = δ \|\pi_1-\pi_0\|_1=\delta ∥ π 1 − π 0 ∥ 1 = δ Lemma 4.2 provides a distribution ω \omega ω r − 1 r-1 r − 1 π 0 \pi_0 π 0 π 1 \pi_1 π 1 δ \delta δ π 0 \pi_0 π 0 π 1 \pi_1 π 1 ω ( s ) ≥ 32 − A δ \omega(s)\ge32^{-A}\delta ω ( s ) ≥ 3 2 − A δ s ∈ [ A ] ∪ { 0 } s\in[A]\cup\{0\} s ∈ [ A ] ∪ { 0 } ω \omega ω π b , u = ( 1 − u ) π b + u ω \pi_{b,u}=(1-u)\pi_b+u\omega π b , u = ( 1 − u ) π b + u ω b ∈ { 0 , 1 } b\in\{0,1\} b ∈ { 0 , 1 } r − 1 r-1 r − 1 π b \pi_b π b ω \omega ω
Denoting F b ( u ) = E z ∼ π b , u ⊗ m [ h ( z ) ] F_b(u)=\mathbb{E}_{z\sim\pi_{b,u}^{\otimes m}}[h(z)] F b ( u ) = E z ∼ π b , u ⊗ m [ h ( z )] ∣ F 1 ( 0 ) − F 0 ( 0 ) ∣ ≤ ∣ F 0 ( 1 ) − F 0 ( 0 ) ∣ + ∣ F 1 ( 1 ) − F 1 ( 0 ) ∣ |F_1(0)-F_0(0)|\le|F_0(1)-F_0(0)|+|F_1(1)-F_1(0)| ∣ F 1 ( 0 ) − F 0 ( 0 ) ∣ ≤ ∣ F 0 ( 1 ) − F 0 ( 0 ) ∣ + ∣ F 1 ( 1 ) − F 1 ( 0 ) ∣ Lemma 3.8 to bound each term ∣ F b ( 1 ) − F b ( 0 ) ∣ |F_b(1)-F_b(0)| ∣ F b ( 1 ) − F b ( 0 ) ∣ b ∈ { 0 , 1 } b\in\{0,1\} b ∈ { 0 , 1 } w > 3 N / 4 w>3N/4 w > 3 N /4
∣ ∑ s ∈ S π ˉ b , u ( s ) ( q w ( s ) − P w ( s ) ) ∣ ≤ δ ∑ ℓ = r A ( A ℓ ) ∣ d ℓ ( w ) ∣ . \left|\sum_{s\in S}\bar{\pi}_{b,u}(s)\left(q_w(s)-P_w(s)\right)\right|\leq\delta\sum_{\ell=r}^{A}\binom{A}{\ell}\left|d_{\ell}(w)\right|. s ∈ S ∑ π ˉ b , u ( s ) ( q w ( s ) − P w ( s ) ) ≤ δ ℓ = r ∑ A ( ℓ A ) ∣ d ℓ ( w ) ∣ . Now we use the other main lemma of this proof: Lemma 4.1 provides an upper bound of c ℓ T 1 + α ℓ N ( m a ) − α ℓ \frac{c^{\ell}T^{1+\alpha_{\ell}}}{N}(ma)^{-\alpha_{\ell}} N c ℓ T 1 + α ℓ ( ma ) − α ℓ ∣ d ℓ ( w ) ∣ \left|d_{\ell}(w)\right| ∣ d ℓ ( w ) ∣ α j = 1 − 2 1 − j \alpha_j=1-2^{1-j} α j = 1 − 2 1 − j a a a π b , u \pi_{b,u} π b , u ω \omega ω § 4 ), one can obtain the required upper bound
∣ Pr f ∼ Π 0 , N [ A f = 1 ] − Pr f ∼ Π 1 , N [ A f = 1 ] ∣ ≤ C A 2 T 2 − 2 1 − r N 1 − 2 1 − r . \left|\underset{f\sim\Pi_{0,N}}{\Pr}\left[\mathcal{A}^{f}=1\right]-\underset{f\sim\Pi_{1,N}}{\Pr}\left[\mathcal{A}^{f}=1\right]\right|\leq C A^{2}\frac{T^{2-2^{1-r}}}{N^{1-2^{1-r}}}. f ∼ Π 0 , N Pr [ A f = 1 ] − f ∼ Π 1 , N Pr [ A f = 1 ] ≤ C A 2 N 1 − 2 1 − r T 2 − 2 1 − r . up to a small additive term bounded by N exp ( − c N A 2 ) N\exp\left(-\frac{cN}{A^{2}}\right) N exp ( − A 2 c N ) w ≤ 3 N / 4 w\leq3N/4 w ≤ 3 N /4 A A A r r r T = Ω ( N 1 / 2 − 1 / ( 2 ( 2 r − 1 ) ) ) T=\Omega\left(N^{1/2-1/(2(2r-1))}\right) T = Ω ( N 1/2 − 1/ ( 2 ( 2 r − 1 )) )
Obtaining the distribution ω \omega ω The proof of Lemma 4.2 first starts from ( π 0 + π 1 ) / 2 (\pi_0+\pi_1)/2 ( π 0 + π 1 ) /2 r − 1 r-1 r − 1 r r r π 0 \pi_0 π 0 π 1 \pi_1 π 1
Newton coefficients of q w q_w q w Now we turn to proving Lemma 4.1 , and introduce some notation. First, we write the input function f : [ N ] → [ N ] f:[N]\to[N] f : [ N ] → [ N ] f ∈ [ N ] N f\in[N]^N f ∈ [ N ] N f = ( f ( 1 ) , … , f ( N ) ) f=(f(1),\ldots,f(N)) f = ( f ( 1 ) , … , f ( N )) [ N ] [N] [ N ] f f f ℓ ≥ r \ell\geq r ℓ ≥ r f f f ℓ \ell ℓ ρ \rho ρ ℓ \ell ℓ n j n_j n j j j j j < ℓ j<\ell j < ℓ n ∗ = min 1 ≤ j < ℓ n j n_*=\min_{1\leq j<\ell}n_j n ∗ = min 1 ≤ j < ℓ n j p ( f ) = Pr [ A f = 1 ] p(f)=\Pr\left[\mathcal{A}^{f}=1\right] p ( f ) = Pr [ A f = 1 ] f f f
We define the following distribution ν j \nu_j ν j j ≤ ℓ j\leq\ell j ≤ ℓ [ N ] [N] [ N ] c \mathbf{c} c ℓ \ell ℓ j j j B B B ℓ − j \ell-j ℓ − j f ( i ) f(i) f ( i ) i i i a = ( a i ) i ∈ B \mathbf{a}=(a_i)_{i\in B} a = ( a i ) i ∈ B j j j [ N ] ∖ f ( [ N ] ) [N]\setminus f([N]) [ N ] ∖ f ([ N ]) ν j \nu_j ν j ( f , B , a ) (f,B,\mathbf{a}) ( f , B , a ) f f f ν j \nu_j ν j D c ( w , j ) \mathcal{D}_{\mathbf{c}}(\mathbf{w},j) D c ( w , j ) E ν j [ p ( f ) ] = q w ( j ) \mathbb{E}_{\nu_j}[p(f)]=q_w(j) E ν j [ p ( f )] = q w ( j )
For a subset U ⊆ B U\subseteq B U ⊆ B f U , a f^{U,\mathbf{a}} f U , a f f f f ( i ) f(i) f ( i ) a i a_i a i i ∈ U i\in U i ∈ U
D B G a ( f ) = ∑ U ⊆ B ( − 1 ) ∣ U ∣ g ( f U , a ) , D_{B\mathcal{G}}^{\mathbf{a}}(f)=\sum_{U\subseteq B}(-1)^{|U|}g\left(f^{U,\mathbf{a}}\right), D B G a ( f ) = U ⊆ B ∑ ( − 1 ) ∣ U ∣ g ( f U , a ) , where g g g [ N ] N [N]^N [ N ] N a a a j = ℓ j=\ell j = ℓ g = p g=p g = p U ⊆ B U\subseteq B U ⊆ B ( ℓ − ∣ U ∣ ) (\ell-|U|) ( ℓ − ∣ U ∣ ) ∣ U ∣ |U| ∣ U ∣ q w ( ℓ − ∣ U ∣ ) q_{\mathbf{w}}(\ell-|U|) q w ( ℓ − ∣ U ∣ ) d ℓ ( w ) = ∑ s = 0 ℓ ( − 1 ) ℓ − s ( ℓ s ) q w ( s ) d_{\ell}(\mathbf{w})=\sum_{s=0}^{\ell}(-1)^{\ell-s}\binom{\ell}{s}q_{\mathbf{w}}(s) d ℓ ( w ) = ∑ s = 0 ℓ ( − 1 ) ℓ − s ( s ℓ ) q w ( s ) 0 ≤ ℓ ≤ A 0\leq\ell\leq A 0 ≤ ℓ ≤ A Proposition 4.3 )
E ν ℓ [ ( D B p ) ( f ) ] = ∑ s = 0 ℓ ( − 1 ) ℓ − s ( ℓ s ) q w ( s ) = d ℓ ( w ) . \mathbb{E}_{\nu_\ell}[(D_Bp)(f)]=\sum_{s=0}^{\ell}(-1)^{\ell-s}\binom{\ell}{s}q_{\mathbf{w}}(s)=d_\ell(\mathbf{w}). E ν ℓ [( D B p ) ( f )] = s = 0 ∑ ℓ ( − 1 ) ℓ − s ( s ℓ ) q w ( s ) = d ℓ ( w ) . Bounding expected block differences As we mentioned, Lemma 4.1 gives an upper bound of C ℓ T 1 + α ℓ N ( m a ) − α ℓ \frac{C^\ell T^{1+\alpha_\ell}}{N}(ma)^{-\alpha_\ell} N C ℓ T 1 + α ℓ ( ma ) − α ℓ ∣ d ℓ ( w ) ∣ |d_\ell(\mathbf{w})| ∣ d ℓ ( w ) ∣ ∣ d ℓ ( w ) ∣ |d_\ell(\mathbf{w})| ∣ d ℓ ( w ) ∣ w \mathbf{w} w ∣ d ℓ ( w ) ∣ |d_\ell(\mathbf{w})| ∣ d ℓ ( w ) ∣ w ∈ { 0 , 1 } m − 1 \mathbf{w}\in\{0,1\}^{m-1} w ∈ { 0 , 1 } m − 1 Lemma 4.8 simply by using the Newton bound (Lemma 3.3). The other cases are treated in Lemma 4.9 by combining the last equation of the previous paragraph and the bound on the expected block differences ∣ E ν ℓ [ ( D B p ) ( f ) ] ∣ ≤ C ℓ T 1 + α ℓ ρ n 1 n ∗ α ℓ − 1 / 2 |\mathbb{E}_{\nu_\ell}[(D_Bp)(f)]|\leq\frac{C^\ell T^{1+\alpha_\ell}}{\sqrt{\rho}n_1n_*^{\alpha_\ell-1/2}} ∣ E ν ℓ [( D B p ) ( f )] ∣ ≤ ρ n 1 n ∗ α ℓ − 1/2 C ℓ T 1 + α ℓ α j = 1 − 2 1 − j \alpha_j=1-2^{1-j} α j = 1 − 2 1 − j Lemma 4.6 . Finally, the bounds on the inverse binomial moments of Lemma 3.6 turn the dependence on ρ \rho ρ n ∗ n_* n ∗ ( m a ) − α ℓ (ma)^{-\alpha_\ell} ( ma ) − α ℓ
Query-gain argument Now we turn to proving Lemma 4.6 , which is the core of the proof of Theorem 2.6 . Our argument is similar to the query-gain argument in [9 ] , for which we only present here a high-level intuition. Recall that the goal is to prove an upper bound on ∣ E ν ℓ [ ( D B p ) ( f ) ] ∣ |\mathbb{E}_{\nu_\ell}[(D_Bp)(f)]| ∣ E ν ℓ [( D B p ) ( f )] ∣ T T T f f f ∣ ψ t ⟩ |\psi_t\rangle ∣ ψ t ⟩ t t t ∣ ψ t ′ ⟩ |\psi'_t\rangle ∣ ψ t ′ ⟩ t + 1 t+1 t + 1 D B D_B D B f ↦ ∣ ψ t ( f ) ⟩ f\mapsto|\psi_t(f)\rangle f ↦ ∣ ψ t ( f )⟩ ∣ ψ 0 ⟩ |\psi_0\rangle ∣ ψ 0 ⟩ ∣ ψ T ⟩ |\psi_T\rangle ∣ ψ T ⟩ p ( f ) p(f) p ( f ) ∣ 0 ⟩ |0\rangle ∣0 ⟩ ⟨ 0 ∣ ψ T ( f ) ⟩ = 1 − 2 p ( f ) \langle0|\psi_T(f)\rangle=1-2p(f) ⟨ 0∣ ψ T ( f )⟩ = 1 − 2 p ( f ) § 4 .
Let us define difference vector ∣ e B , t ⟩ = D B ∣ ψ t + 1 ⟩ − O f D B ∣ ψ t ′ ⟩ |e_{B,t}\rangle=D_B|\psi_{t+1}\rangle-O_fD_B|\psi'_t\rangle ∣ e B , t ⟩ = D B ∣ ψ t + 1 ⟩ − O f D B ∣ ψ t ′ ⟩ D B ∣ ψ T ⟩ D_B|\psi_T\rangle D B ∣ ψ T ⟩ D B p D_Bp D B p ∣ e B , t ⟩ |e_{B,t}\rangle ∣ e B , t ⟩ Lemma 4.5 combined with Claim 4.7 provides bound ∥ ∣ e B , t ⟩ ∥ ν j 2 ≤ 4 j n 1 4 2 j T 2 α j n 1 n ∗ 2 α j \lVert|e_{B,t}\rangle\rVert_{\nu_j}^2\leq\frac{4j}{n_1}\frac{4^{2j}T^{2\alpha_j}}{n_1n_*^{2\alpha_j}} ∥ ∣ e B , t ⟩ ∥ ν j 2 ≤ n 1 4 j n 1 n ∗ 2 α j 4 2 j T 2 α j ∣ E ν ℓ [ ( D B p ) ( f ) ] ∣ |\mathbb{E}_{\nu_\ell}[(D_Bp)(f)]| ∣ E ν ℓ [( D B p ) ( f )] ∣ ∑ t = 0 T − 1 ∥ ∣ e B , t ⟩ ∥ ν ℓ ρ ≤ C ℓ T 1 + α ℓ ρ n 1 n ∗ α ℓ − 1 / 2 \sum_{t=0}^{T-1}\lVert|e_{B,t}\rangle\rVert_{\nu_\ell}\sqrt{\rho}\leq\frac{C^\ell T^{1+\alpha_\ell}}{\sqrt{\rho}n_1n_*^{\alpha_\ell-1/2}} ∑ t = 0 T − 1 ∥ ∣ e B , t ⟩ ∥ ν ℓ ρ ≤ ρ n 1 n ∗ α ℓ − 1/2 C ℓ T 1 + α ℓ
Problem setting and main results
Construction of the input distributions
For an integer N ≥ 1 N\geq1 N ≥ 1 [ N ] = { 1 , … , N } [N]=\{1,\ldots,N\} [ N ] = { 1 , … , N } x = ( x 1 , … , x m ) \mathbf{x}=(x_1,\ldots,x_m) x = ( x 1 , … , x m )
Frequency vector The frequency vector of any given function f : [ N ] → [ N ] f:[N]\to[N] f : [ N ] → [ N ] c ( f ) = ( ∣ f − 1 ( 1 ) ∣ , … , ∣ f − 1 ( N ) ∣ ) \mathbf{c}(f)=(|f^{-1}(1)|,\ldots,|f^{-1}(N)|) c ( f ) = ( ∣ f − 1 ( 1 ) ∣ , … , ∣ f − 1 ( N ) ∣ ) c = ( c 1 , c 2 , … , c N ) ∈ Z ≥ 0 N \mathbf{c}=(c_1,c_2,\ldots,c_N)\in\mathbb{Z}_{\geq0}^N c = ( c 1 , c 2 , … , c N ) ∈ Z ≥ 0 N feasible if ∑ j ∈ [ N ] c j = N \sum_{j\in[N]}c_j=N ∑ j ∈ [ N ] c j = N c = c ( f ) \mathbf{c}=\mathbf{c}(f) c = c ( f ) f : [ N ] → [ N ] f:[N]\to[N] f : [ N ] → [ N ] feasible frequency vector , or simply a feasible c \mathbf{c} c
For a feasible (frequency vector) c \mathbf{c} c D c \mathcal{D}_{\mathbf{c}} D c c \mathbf{c} c D c \mathcal{D}_{\mathbf{c}} D c c \mathbf{c} c c ′ \mathbf{c}' c ′ ( f ( 1 ) , … , f ( N ) ) (f(1),\ldots,f(N)) ( f ( 1 ) , … , f ( N )) j j j c j ′ c'_j c j ′
The following random variable describes the frequency of a uniformly chosen output label. For a function f f f D c \mathcal{D}_{\mathbf{c}} D c positive frequency statistics X = ∣ f − 1 ( Y ) ∣ X=\lvert f^{-1}(Y)\rvert X = ∣ f − 1 ( Y )∣ Y Y Y f ( [ N ] ) f([N]) f ([ N ])
Pr [ X = a ] = ∣ { j : c j = a } ∣ ∣ { j : c j ≠ 0 } ∣ ( a ≥ 1 ) . \Pr[X=a]=\frac{\lvert\{j:c_j=a\}\rvert}{\lvert\{j:c_j\ne0\}\rvert}\qquad(a\ge1). Pr [ X = a ] = ∣{ j : c j = 0 }∣ ∣{ j : c j = a }∣ ( a ≥ 1 ) . Choosing instead Y ′ Y' Y ′ [ N ] [N] [ N ] mean-one frequency statistics Z = ∣ f − 1 ( Y ′ ) ∣ Z=\lvert f^{-1}(Y')\rvert Z = ∣ f − 1 ( Y ′ )∣ E [ X ] = N / ∣ f ( [ N ] ) ∣ \mathbb{E}[X]=N/\lvert f([N])\rvert E [ X ] = N / ∣ f ([ N ])∣
Pr [ Z = a ] = Pr [ X = a ] E [ X ] ( a ≥ 1 ) , Pr [ Z = 0 ] = 1 − 1 E [ X ] . (4) \Pr[Z=a]=\frac{\Pr[X=a]}{\mathbb{E}[X]}\quad(a\ge1),\qquad\Pr[Z=0]=1-\frac{1}{\mathbb{E}[X]}. \tag*{(4)} Pr [ Z = a ] = E [ X ] Pr [ X = a ] ( a ≥ 1 ) , Pr [ Z = 0 ] = 1 − E [ X ] 1 . (4) So the normalization simply corresponds to including unused output labels. When it is clear from the context, we will refer to any of these statistics simply as frequency statistics.
From frequency statistics to functions We now construct a random function from prescribed positive frequency statistics X X X Z Z Z (4) . We use a randomized variant of the frequency construction of [RRSS09, Definition 5.4]. We sample m m m z = ( z 1 , … , z m ) \mathbf{z}=(z_1,\ldots,z_m) z = ( z 1 , … , z m ) Z Z Z z ≤ N z\le N z ≤ N N − z N-z N − z
Definition 2.1 (Induced input distribution). Fix an integer A ≥ 1 A\ge1 A ≥ 1 and positive frequency statistics X X X supported on [ A ] [A] [ A ] Denote μ = E [ X ] \mu=\mathbb{E}[X] μ = E [ X ] and define its associated mean-one frequency statistics Z Z Z by (4) . For N ≥ 1 N\ge1 N ≥ 1 let Π N \Pi_N Π N be the distribution of f : [ N ] → [ N ] f:[N]\to[N] f : [ N ] → [ N ] obtained as follows:
Draw m = ⌊ N / 2 ⌋ m=\lfloor N/2\rfloor m = ⌊ N /2 ⌋ z = ( z 1 , … , z m ) \mathbf{z}=(z_1,\ldots,z_m) z = ( z 1 , … , z m ) Z Z Z z = ∑ i z i z=\sum_i z_i z = ∑ i z i
If z ≤ N z\le N z ≤ N c = c ( z ) \mathbf{c}=\mathbf{c}(\mathbf{z}) c = c ( z ) z \mathbf{z} z N − z N-z N − z 1 1 1 N N N z > N z>N z > N c = ( 1 , … , 1 ) \mathbf{c}=(1,\ldots,1) c = ( 1 , … , 1 )
Draw f ∼ D c f\sim\mathcal{D}_{\mathbf{c}} f ∼ D c
Observe that the vector c \mathbf{c} c N N N
Remark 2.2. Let S = { 0 } ∪ [ A ] S=\{0\}\cup[A] S = { 0 } ∪ [ A ] m = ⌊ N / 2 ⌋ m=\lfloor N/2\rfloor m = ⌊ N /2 ⌋ π \pi π Z Z Z π ( s ) = Pr [ Z = s ] \pi(s)=\Pr[Z=s] π ( s ) = Pr [ Z = s ] s ∈ S s\in S s ∈ S Π N \Pi_N Π N π ⊗ m \pi^{\otimes m} π ⊗ m z ∈ S m \mathbf{z}\in S^m z ∈ S m c ( z ) \mathbf{c}(\mathbf{z}) c ( z ) Definition 2.1 . Then generating f f f Π N \Pi_N Π N z \mathbf{z} z π ⊗ m \pi^{\otimes m} π ⊗ m f f f D c ( z ) \mathcal{D}_{\mathbf{c}(\mathbf{z})} D c ( z )
In particular, for every algorithm A \mathcal{A} A f f f
Pr f ∼ Π N [ A f = 1 ] = E z ∼ π ⊗ m [ h ( z ) ] , with h ( z ) = Pr f ∼ D c ( z ) [ A f = 1 ] . (5) \Pr_{f\sim\Pi_N}[\mathcal{A}^f=1]=\mathbb{E}_{\mathbf{z}\sim\pi^{\otimes m}}[h(\mathbf{z})],\qquad\text{with }h(\mathbf{z})=\Pr_{f\sim\mathcal{D}_{\mathbf{c}(\mathbf{z})}}[\mathcal{A}^f=1]. \tag*{(5)} f ∼ Π N Pr [ A f = 1 ] = E z ∼ π ⊗ m [ h ( z )] , with h ( z ) = f ∼ D c ( z ) Pr [ A f = 1 ] . (5) Example 2.3. Consider A = 3 A=3 A = 3 N = 8 N=8 N = 8 X X X 1 1 1 3 3 3 1 / 2 1/2 1/2 μ = 2 \mu=2 μ = 2
Pr [ Z = 0 ] = 1 2 , Pr [ Z = 1 ] = Pr [ Z = 3 ] = 1 4 . \Pr[Z=0]=\frac{1}{2},\qquad\Pr[Z=1]=\Pr[Z=3]=\frac{1}{4}. Pr [ Z = 0 ] = 2 1 , Pr [ Z = 1 ] = Pr [ Z = 3 ] = 4 1 . To sample f ∼ Π 8 f\sim\Pi_8 f ∼ Π 8 ( 3 , 1 , 0 , 0 ) (3,1,0,0) ( 3 , 1 , 0 , 0 ) s = 4 s=4 s = 4
c = ( 3 , 1 , 1 , 1 , 1 , 1 , 0 , 0 ) . \mathbf{c}=(3,1,1,1,1,1,0,0). c = ( 3 , 1 , 1 , 1 , 1 , 1 , 0 , 0 ) . Thus there is one output value of multiplicity three and five of multiplicity one. One possible outcome after assigning labels and positions is
( f ( 1 ) , … , f ( 8 ) ) = ( 7 , 2 , 7 , 5 , 8 , 3 , 6 , 7 ) . (f(1),\ldots,f(8))=(7,2,7,5,8,3,6,7). ( f ( 1 ) , … , f ( 8 )) = ( 7 , 2 , 7 , 5 , 8 , 3 , 6 , 7 ) . For comparison, the draw ( 3 , 3 , 3 , 0 ) (3,3,3,0) ( 3 , 3 , 3 , 0 ) s = 9 > N s=9>N s = 9 > N c = ( 1 , … , 1 ) \mathbf{c}=(1,\ldots,1) c = ( 1 , … , 1 )
The number K K K 3 3 3 Bin ( 4 , 1 / 4 ) \operatorname{Bin}(4,1/4) Bin ( 4 , 1/4 ) K = 0 K=0 K = 0 K ≥ 3 K\geq3 K ≥ 3 K = 1 , 2 K=1,2 K = 1 , 2
Π 8 = 47 128 D ( 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 ) + 27 64 D ( 3 , 1 , 1 , 1 , 1 , 1 , 0 , 0 ) + 27 128 D ( 3 , 3 , 1 , 1 , 0 , 0 , 0 , 0 ) . \Pi_8=\frac{47}{128}\mathcal{D}_{(1,1,1,1,1,1,1,1)}+\frac{27}{64}\mathcal{D}_{(3,1,1,1,1,1,0,0)}+\frac{27}{128}\mathcal{D}_{(3,3,1,1,0,0,0,0)}. Π 8 = 128 47 D ( 1 , 1 , 1 , 1 , 1 , 1 , 1 , 1 ) + 64 27 D ( 3 , 1 , 1 , 1 , 1 , 1 , 0 , 0 ) + 128 27 D ( 3 , 3 , 1 , 1 , 0 , 0 , 0 , 0 ) . Main theorems
Fix an integer A ≥ 1 A\geq1 A ≥ 1 X 0 , X 1 X_0,X_1 X 0 , X 1 [ A ] [A] [ A ] Π 0 , N \Pi_{0,N} Π 0 , N Π 1 , N \Pi_{1,N} Π 1 , N Definition 2.1 , and consider the following distinguishability problem.
A single function f ∼ Π b , N f\sim\Pi_{b,N} f ∼ Π b , N f f f b b b Π 0 , N \Pi_{0,N} Π 0 , N Π 1 , N \Pi_{1,N} Π 1 , N
The following proposition expresses exact moment matching of the mean-one frequency statistics as proportional moments of the positive frequency statistics.
Recall that, for b ∈ { 0 , 1 } b\in\{0,1\} b ∈ { 0 , 1 } μ b = E [ X b ] \mu_b=\mathbb{E}[X_b] μ b = E [ X b ] Z b ∈ { 0 } ∪ [ A ] Z_b\in\{0\}\cup[A] Z b ∈ { 0 } ∪ [ A ]
Pr [ Z b = a ] = Pr [ X b = a ] μ b (for a ∈ [ A ] ) , Pr [ Z b = 0 ] = 1 − 1 μ b . \Pr[Z_b=a]=\frac{\Pr[X_b=a]}{\mu_b}\quad\text{(for }a\in[A]\text{)},\qquad\Pr[Z_b=0]=1-\frac{1}{\mu_b}. Pr [ Z b = a ] = μ b Pr [ X b = a ] (for a ∈ [ A ] ) , Pr [ Z b = 0 ] = 1 − μ b 1 . Since μ b ≥ 1 \mu_b\geq1 μ b ≥ 1 X b X_b X b 1 / μ b 1/\mu_b 1/ μ b
Proposition 2.4 (Normalization of moments). For b ∈ { 0 , 1 } b\in\{0,1\} b ∈ { 0 , 1 }
E [ Z b j ] = E [ X b j ] μ b , E [ Z b ] = 1. (6) \mathbb{E}[Z_b^j]=\frac{\mathbb{E}[X_b^j]}{\mu_b},\qquad\mathbb{E}[Z_b]=1. \tag*{(6)} E [ Z b j ] = μ b E [ X b j ] , E [ Z b ] = 1. (6) Consequently, for every integer $j\geq 1,
E [ Z 0 j ] = E [ Z 1 j ] ⟺ E [ X 1 j ] E [ X 0 j ] = μ 1 μ 0 . \mathbb{E}[Z_0^j]=\mathbb{E}[Z_1^j]\quad\Longleftrightarrow\quad\frac{\mathbb{E}[X_1^j]}{\mathbb{E}[X_0^j]}=\frac{\mu_1}{\mu_0}. E [ Z 0 j ] = E [ Z 1 j ] ⟺ E [ X 0 j ] E [ X 1 j ] = μ 0 μ 1 . Proof. The proof is direct using, for j ≥ 1 j \ge1 j ≥ 1
E [ Z b j ] = ∑ a = 1 A a j Pr [ X b = a ] μ b = E [ X b j ] μ b . \mathbb{E}[Z_b^j] = \sum_{a=1}^{A} a^j \frac{\Pr[X_b=a]}{\mu_b} = \frac{\mathbb{E}[X_b^j]}{\mu_b}. E [ Z b j ] = a = 1 ∑ A a j μ b Pr [ X b = a ] = μ b E [ X b j ] . In particular, all denominators are non-zero since X b ≥ 1 X_b \ge1 X b ≥ 1 j = 1 j=1 j = 1 E [ Z b ] = 1 \mathbb{E}[Z_b]=1 E [ Z b ] = 1
We now introduce our two main theorems, which share the same moment hypothesis. Theorem 2.5 remains useful when the support bound A A A ( r − 1 ) (r-1) ( r − 1 ) N N N A , r A,r A , r Theorem 2.6 gives a stronger quantum query lower bound for constant distinguishing bias, at the cost of an exponential factor C A C^A C A
Theorem 2.5 is proved in § 3 and Theorem 2.6 in § 4 . The constants c , C c,C c , C
Theorem 2.5. Fix an integer A ≥ 1 A \ge1 A ≥ 1 X 0 , X 1 X_0,X_1 X 0 , X 1 [ A ] [A] [ A ] Π 0 , N , Π 1 , N \Pi_{0,N},\Pi_{1,N} Π 0 , N , Π 1 , N Definition 2.1 applied to X 0 X_0 X 0 X 1 X_1 X 1 r ≥ 2 r \ge2 r ≥ 2
E [ X 1 ] E [ X 0 ] = E [ X 1 2 ] E [ X 0 2 ] = ⋯ = E [ X 1 r − 1 ] E [ X 0 r − 1 ] . (7) \frac{\mathbb{E}[X_1]}{\mathbb{E}[X_0]}=\frac{\mathbb{E}[X_1^2]}{\mathbb{E}[X_0^2]}=\cdots=\frac{\mathbb{E}[X_1^{r-1}]}{\mathbb{E}[X_0^{r-1}]}. \tag*{(7)} E [ X 0 ] E [ X 1 ] = E [ X 0 2 ] E [ X 1 2 ] = ⋯ = E [ X 0 r − 1 ] E [ X 1 r − 1 ] . (7) There are absolute constants c , C > 0 c,C>0 c , C > 0 N ≥ C A N \ge CA N ≥ C A 0 ≤ T ≤ c N 0 \le T \le c\sqrt{N} 0 ≤ T ≤ c N T T T A \mathcal{A} A
∣ Pr f ∼ Π 0 , N [ A f = 1 ] − Pr f ∼ Π 1 , N [ A f = 1 ] ∣ ≤ N A ( C A T 2 r 2 N ) r + N exp ( − c N A 2 ) . (8) \left|\Pr_{f\sim\Pi_{0,N}}[\mathcal{A}^f=1]-\Pr_{f\sim\Pi_{1,N}}[\mathcal{A}^f=1]\right|
\le\frac{N}{A}\left(\frac{CAT^2}{r^2N}\right)^r+N\exp\left(-\frac{cN}{A^2}\right). \tag*{(8)} f ∼ Π 0 , N Pr [ A f = 1 ] − f ∼ Π 1 , N Pr [ A f = 1 ] ≤ A N ( r 2 N C A T 2 ) r + N exp ( − A 2 c N ) . (8) In particular, if A = O ( r 2 ) A=O(r^2) A = O ( r 2 ) A = o ( N / log N ) A=o(\sqrt{N}/\log N) A = o ( N / log N ) o ( 1 ) o(1) o ( 1 ) T = o ( N 1 / 2 − 1 / ( 2 r ) ) T=o(N^{1/2-1/(2r)}) T = o ( N 1/2 − 1/ ( 2 r ) ) N → ∞ N\to\infty N → ∞ f f f
Theorem 2.6. Fix an integer A ≥ 1 A \ge1 A ≥ 1 X 0 , X 1 X_0,X_1 X 0 , X 1 [ A ] [A] [ A ] Π 0 , N , Π 1 , N \Pi_{0,N},\Pi_{1,N} Π 0 , N , Π 1 , N Definition 2.1 applied to X 0 X_0 X 0 X 1 X_1 X 1 r ≥ 2 r \ge2 r ≥ 2
E [ X 1 ] E [ X 0 ] = E [ X 1 2 ] E [ X 0 2 ] = ⋯ = E [ X 1 r − 1 ] E [ X 0 r − 1 ] . \frac{\mathbb{E}[X_1]}{\mathbb{E}[X_0]}=\frac{\mathbb{E}[X_1^2]}{\mathbb{E}[X_0^2]}=\cdots=\frac{\mathbb{E}[X_1^{r-1}]}{\mathbb{E}[X_0^{r-1}]}. E [ X 0 ] E [ X 1 ] = E [ X 0 2 ] E [ X 1 2 ] = ⋯ = E [ X 0 r − 1 ] E [ X 1 r − 1 ] . There are absolute constants c , C > 0 c,C>0 c , C > 0 N ≥ C A N \ge CA N ≥ C A 0 ≤ T ≤ c N 0 \le T \le c\sqrt{N} 0 ≤ T ≤ c N T T T A \mathcal{A} A
∣ Pr f ∼ Π 0 , N [ A f = 1 ] − Pr f ∼ Π 1 , N [ A f = 1 ] ∣ ≤ C A r T 2 − 2 1 − r N 1 − 2 1 − r + N exp ( − c N A 2 ) . (9) \left|\Pr_{f\sim\Pi_{0,N}}[\mathcal{A}^f=1]-\Pr_{f\sim\Pi_{1,N}}[\mathcal{A}^f=1]\right|
\le CA^r\frac{T^{2-2^{1-r}}}{N^{1-2^{1-r}}}+N\exp\left(-\frac{cN}{A^2}\right). \tag*{(9)} f ∼ Π 0 , N Pr [ A f = 1 ] − f ∼ Π 1 , N Pr [ A f = 1 ] ≤ C A r N 1 − 2 1 − r T 2 − 2 1 − r + N exp ( − A 2 c N ) . (9) In particular, for fixed A , r A,r A , r o ( 1 ) o(1) o ( 1 ) T = o ( N 1 / 2 − 1 / ( 2 ( 2 r − 1 ) ) ) T=o(N^{1/2-1/(2(2^r-1))}) T = o ( N 1/2 − 1/ ( 2 ( 2 r − 1 )) ) N → ∞ N\to\infty N → ∞ f f f
Remark on the case r = 2 r = 2 r = 2 This base case also appears in [RRSS09, Definition 5.4, Theorem 5.6 and Corollary 5.7]. When r = 2 r = 2 r = 2 A = 2 A = 2 A = 2 X 0 ≡ 1 X_0 \equiv1 X 0 ≡ 1 X 1 ≡ 2 X_1 \equiv2 X 1 ≡ 2 Π 0 , N \Pi_{0,N} Π 0 , N Π 1 , N \Pi_{1,N} Π 1 , N K ∼ Bin ( ⌊ N / 2 ⌋ , 1 / 2 ) K \sim\operatorname{Bin}(\lfloor N/2 \rfloor, 1/2) K ∼ Bin (⌊ N /2 ⌋ , 1/2 ) 2 2 2 1 − e − Ω ( N ) 1 - e^{-\Omega(N)} 1 − e − Ω ( N ) N / 8 N/8 N /8 1 / 8 1/8 1/8 Theorem 2.5 gives an Ω ( N 1 / 4 ) \Omega(N^{1/4}) Ω ( N 1/4 ) Theorem 2.6 recovers the known Ω ( N 1 / 3 ) \Omega(N^{1/3}) Ω ( N 1/3 ) [5 ] by noticing that a two-to-one function is a special case of a far from injective function.
Moment matching: framework and first bound
We begin by introducing the general tools that will be used in the proofs of our two main theorems, and then prove the first one, namely Theorem 2.5 .
Polynomial and probabilistic tools
Symmetrization
We use the frequency-vector notation of Subsection 2.1. The following lemma establishes the connection between quantum query complexity and the moment-matching technique used in our proof. It shows that, after averaging over random permutations of the domain and range, the acceptance probability of any quantum algorithm making at most T T T 2 T 2T 2 T
Moreover, its representation in terms of power sums, together with the weighted-degree restriction, allows us to obtain a low-degree univariate polynomial when varying a single multiplicity while keeping others fixed. This polynomial structure is crucial for applying moment matching to cancel the lower-order terms and using polynomial inequalities to bound the remaining contribution.
Lemma 3.1 (Symmetrization). For every quantum algorithm A A A T T T P ∈ R [ x 1 , … , x N ] P \in\mathbb{R}[x_1, \ldots, x_N] P ∈ R [ x 1 , … , x N ] d = 2 T d = 2T d = 2 T c \mathbf{c} c
P ( c ) = Pr f ∼ D c [ A f = 1 ] ∈ [ 0 , 1 ] . P(\mathbf{c}) = \Pr_{f \sim\mathcal{D}_{\mathbf{c}}}\left[A^f = 1\right] \in[0,1]. P ( c ) = f ∼ D c Pr [ A f = 1 ] ∈ [ 0 , 1 ] . If d ≥ 1 d \ge1 d ≥ 1 P ( x ) = F ( p 1 ( x ) , … , p d ( x ) ) P(\mathbf{x}) = F(p_1(\mathbf{x}), \ldots, p_d(\mathbf{x})) P ( x ) = F ( p 1 ( x ) , … , p d ( x )) p j ( x ) = ∑ i = 1 N x i j p_j(\mathbf{x}) = \sum_{i=1}^{N} x_i^j p j ( x ) = ∑ i = 1 N x i j j j j F ∈ R [ y 1 , … , y d ] F \in\mathbb{R}[y_1, \ldots, y_d] F ∈ R [ y 1 , … , y d ] y 1 α 1 ⋯ y d α d y_1^{\alpha_1} \cdots y_d^{\alpha_d} y 1 α 1 ⋯ y d α d F F F ∑ j = 1 d j α j ≤ d \sum_{j=1}^{d} j\alpha_j \le d ∑ j = 1 d j α j ≤ d
Proof. First, following [8 ] , the acceptance probability Pr [ A f = 1 ] \Pr\left[A^f = 1\right] Pr [ A f = 1 ] d d d δ i , a ( f ) = 1 [ f ( i ) = a ] \delta_{i,a}(f) = \mathbf{1}[f(i) = a] δ i , a ( f ) = 1 [ f ( i ) = a ]
For an input with frequency vector c \mathbf{c} c D c \mathcal{D}_{\mathbf{c}} D c f f f q ≤ d q \le d q ≤ d ℓ \ell ℓ a 1 , … , a ℓ a_1,\ldots,a_\ell a 1 , … , a ℓ q 1 , … , q ℓ q_1,\ldots,q_\ell q 1 , … , q ℓ
1 ( N ) q ( N ) ℓ ∑ a 1 , … , a ℓ ∈ [ N ] d i s t i n c t ∏ s = 1 ℓ ( c a s ) q s , where ( x ) k = x ( x − 1 ) ⋯ ( x − k + 1 ) , and ( x ) 0 = 1. \frac{1}{(N)_q(N)_\ell}\sum_{\substack{a_1,\ldots,a_\ell\in[N]\\ \mathrm{distinct}}}\prod_{s=1}^{\ell}(c_{a_s})_{q_s},
\qquad\text{where }(x)_k=x(x-1)\cdots(x-k+1),\text{ and }(x)_0=1. ( N ) q ( N ) ℓ 1 a 1 , … , a ℓ ∈ [ N ] distinct ∑ s = 1 ∏ ℓ ( c a s ) q s , where ( x ) k = x ( x − 1 ) ⋯ ( x − k + 1 ) , and ( x ) 0 = 1. This is a symmetric polynomial of degree at most ∑ s q s = q ≤ d \sum_s q_s=q\le d ∑ s q s = q ≤ d P P P P P P [30 ] , giving F F F
Approximation and moment bounds
We begin by stating some polynomial tools that will be used in the proofs of Theorems 2.5 and 2.6 . The first provides a bound on the Taylor remainder of a low-degree polynomial whose values are bounded on an integer interval, while the second gives a Newton expansion and a corresponding remainder estimate. These results will allow us to control the higher-order terms that remain after moment matching. For completeness, we provide their proofs in Appendix § 8 .
Lemma 3.2 (Taylor bound). Let H ≥ 1 H\ge1 H ≥ 1 d ≥ 0 d\ge0 d ≥ 0 d 2 ≤ H / 2 d^2\le H/2 d 2 ≤ H /2 q ( z ) = ∑ ℓ = 0 d a ℓ z ℓ q(z)=\sum_{\ell=0}^{d}a_\ell z^\ell q ( z ) = ∑ ℓ = 0 d a ℓ z ℓ d d d ∣ q ( z ) ∣ ≤ 1 |q(z)|\le1 ∣ q ( z ) ∣ ≤ 1 z ∈ { 0 } ∪ [ H ] = { 0 , 1 , … , H } z\in\{0\}\cup[H]=\{0,1,\ldots,H\} z ∈ { 0 } ∪ [ H ] = { 0 , 1 , … , H } r ≥ 1 r\ge1 r ≥ 1 Q r = ∑ ℓ = 0 min ( r − 1 , r ) a ℓ z ℓ Q_r=\sum_{\ell=0}^{\min(r-1,r)}a_\ell z^\ell Q r = ∑ ℓ = 0 m i n ( r − 1 , r ) a ℓ z ℓ z ∈ [ 0 , H ] z\in[0,H] z ∈ [ 0 , H ]
∣ q ( z ) − Q r ( z ) ∣ ≤ 2 ( 2 r ) ! ( 4 d 2 H ) r z r . (10) |q(z)-Q_r(z)|\le\frac{2}{(2r)!}\left(\frac{4d^2}{H}\right)^r z^r. \tag*{(10)} ∣ q ( z ) − Q r ( z ) ∣ ≤ ( 2 r )! 2 ( H 4 d 2 ) r z r . (10) Lemma 3.3 (Newton bound). Let H ≥ 1 H\ge1 H ≥ 1 d ≥ 0 d\ge0 d ≥ 0 q ( z ) q(z) q ( z ) d d d ∣ q ( z ) ∣ ≤ 1 |q(z)|\le1 ∣ q ( z ) ∣ ≤ 1 z ∈ { 0 } ∪ [ H ] z\in\{0\}\cup[H] z ∈ { 0 } ∪ [ H ]
d ℓ = ∑ s = 0 ℓ ( − 1 ) ℓ − s ( ℓ s ) q ( s ) ( 0 ≤ ℓ ≤ H ) . d_\ell=\sum_{s=0}^{\ell}(-1)^{\ell-s}\binom{\ell}{s}q(s)\qquad(0\le\ell\le H). d ℓ = s = 0 ∑ ℓ ( − 1 ) ℓ − s ( s ℓ ) q ( s ) ( 0 ≤ ℓ ≤ H ) . For an integer 1 ≤ r ≤ H + 1 1\le r\le H+1 1 ≤ r ≤ H + 1 Q r ( z ) = ∑ ℓ = 0 r − 1 d ℓ ( z ℓ ) Q_r(z)=\sum_{\ell=0}^{r-1}d_\ell\binom{z}{\ell} Q r ( z ) = ∑ ℓ = 0 r − 1 d ℓ ( ℓ z ) z ∈ { 0 } ∪ [ H ] z\in\{0\}\cup[H] z ∈ { 0 } ∪ [ H ]
q ( z ) − Q r ( z ) = ∑ ℓ = r H d ℓ ( z ℓ ) = ∑ ℓ = r z d ℓ ( z ℓ ) , q(z)-Q_r(z)=\sum_{\ell=r}^{H}d_\ell\binom{z}{\ell}=\sum_{\ell=r}^{z}d_\ell\binom{z}{\ell}, q ( z ) − Q r ( z ) = ℓ = r ∑ H d ℓ ( ℓ z ) = ℓ = r ∑ z d ℓ ( ℓ z ) , where empty sums are understood to be zero. Assume moreover that d 2 ≤ H / 2 d^2\le H/2 d 2 ≤ H /2 1 ≤ r ≤ H + 1 1\le r\le H+1 1 ≤ r ≤ H + 1 z ∈ { 0 } ∪ [ H ] z\in\{0\}\cup[H] z ∈ { 0 } ∪ [ H ]
∣ q ( z ) − Q r ( z ) ∣ ≤ 2 ( 2 r ) ! ( 4 d 2 H ) r z r . (11) |q(z)-Q_r(z)|\le\frac{2}{(2r)!}\left(\frac{4d^2}{H}\right)^r z^r. \tag*{(11)} ∣ q ( z ) − Q r ( z ) ∣ ≤ ( 2 r )! 2 ( H 4 d 2 ) r z r . (11) We first establish a basic consequence of moment matching. The following lemma shows that when two probability distributions have matching moments up to a given order, the corresponding lower-order terms vanish in the difference of expectations of a polynomial. This cancellation holds in both the monomial and Newton bases and will be used to control the differences in acceptance probabilities.
Lemma 3.4 (Moment cancellation). Let A , r ≥ 1 A,r\ge1 A , r ≥ 1 π , ν \pi,\nu π , ν { 0 } ∪ [ A ] \{0\}\cup[A] { 0 } ∪ [ A ] r − 1 r-1 r − 1
∑ s = 0 A ν ( s ) s k = ∑ s = 0 A π ( s ) s k ( k = 1 , … , r − 1 ) . \sum_{s=0}^{A}\nu(s)s^k=\sum_{s=0}^{A}\pi(s)s^k\qquad(k=1,\ldots,r-1). s = 0 ∑ A ν ( s ) s k = s = 0 ∑ A π ( s ) s k ( k = 1 , … , r − 1 ) . Choose one of the two bases ϕ ℓ ( z ) = z ℓ \phi_\ell(z)=z^\ell ϕ ℓ ( z ) = z ℓ ϕ ℓ ( z ) = ( z ℓ ) \phi_\ell(z)=\binom{z}{\ell} ϕ ℓ ( z ) = ( ℓ z ) ℓ ≥ 0 \ell\ge0 ℓ ≥ 0 q ( s ) = ∑ ℓ = 0 D a ℓ ϕ ℓ ( s ) q(s)=\sum_{\ell=0}^{D}a_\ell\phi_\ell(s) q ( s ) = ∑ ℓ = 0 D a ℓ ϕ ℓ ( s ) { 0 } ∪ [ A ] \{0\}\cup[A] { 0 } ∪ [ A ] D ≥ 0 D\ge0 D ≥ 0
∑ s = 0 A ( ν ( s ) − π ( s ) ) q ( s ) = ∑ ℓ = r D η ℓ a ℓ , (12) \sum_{s=0}^{A}(\nu(s)-\pi(s))q(s)=\sum_{\ell=r}^{D}\eta_\ell a_\ell, \tag*{(12)} s = 0 ∑ A ( ν ( s ) − π ( s )) q ( s ) = ℓ = r ∑ D η ℓ a ℓ , (12) where
η ℓ = ∑ s = 0 A ( ν ( s ) − π ( s ) ) ϕ ℓ ( s ) , and ∣ η ℓ ∣ ≤ ∥ ν − π ∥ 1 ϕ ℓ ( A ) . \eta_\ell=\sum_{s=0}^{A}(\nu(s)-\pi(s))\phi_\ell(s),\qquad\text{and}\qquad|\eta_\ell|\le\|\nu-\pi\|_1\phi_\ell(A). η ℓ = s = 0 ∑ A ( ν ( s ) − π ( s )) ϕ ℓ ( s ) , and ∣ η ℓ ∣ ≤ ∥ ν − π ∥ 1 ϕ ℓ ( A ) . Proof. The moment identities also hold for k = 0 k=0 k = 0 ϕ ℓ \phi_\ell ϕ ℓ ℓ \ell ℓ ℓ < r \ell<r ℓ < r ϕ ℓ ( s ) = ∑ k = 0 ℓ b k s k \phi_\ell(s)=\sum_{k=0}^{\ell}b_ks^k ϕ ℓ ( s ) = ∑ k = 0 ℓ b k s k
η ℓ = ∑ k = 0 ℓ b k ∑ s = 0 A ( ν ( s ) − π ( s ) ) s k = 0. \eta_\ell=\sum_{k=0}^{\ell}b_k\sum_{s=0}^{A}(\nu(s)-\pi(s))s^k=0. η ℓ = k = 0 ∑ ℓ b k s = 0 ∑ A ( ν ( s ) − π ( s )) s k = 0. Expanding q q q
∑ s = 0 A ( ν ( s ) − π ( s ) ) q ( s ) = ∑ ℓ = 0 D a ℓ η ℓ = ∑ ℓ = r D a ℓ η ℓ . \sum_{s=0}^{A}(\nu(s)-\pi(s))q(s)=\sum_{\ell=0}^{D}a_\ell\eta_\ell=\sum_{\ell=r}^{D}a_\ell\eta_\ell. s = 0 ∑ A ( ν ( s ) − π ( s )) q ( s ) = ℓ = 0 ∑ D a ℓ η ℓ = ℓ = r ∑ D a ℓ η ℓ . Finally, for either basis, 0 ≤ ϕ ℓ ( s ) ≤ ϕ ℓ ( A ) 0\le\phi_\ell(s)\le\phi_\ell(A) 0 ≤ ϕ ℓ ( s ) ≤ ϕ ℓ ( A ) { 0 } ∪ [ A ] \{0\}\cup[A] { 0 } ∪ [ A ]
∣ η ℓ ∣ ≤ ∑ s = 0 A ∣ ν ( s ) − π ( s ) ∣ ϕ ℓ ( s ) ≤ ∥ ν − π ∥ 1 ϕ ℓ ( A ) . |\eta_\ell|\le\sum_{s=0}^{A}|\nu(s)-\pi(s)|\phi_\ell(s)\le\|\nu-\pi\|_1\phi_\ell(A). ∣ η ℓ ∣ ≤ s = 0 ∑ A ∣ ν ( s ) − π ( s ) ∣ ϕ ℓ ( s ) ≤ ∥ ν − π ∥ 1 ϕ ℓ ( A ) . We next recall the Lagrange polynomial interpolation result on integer intervals. For completeness, we provide a proof in Appendix § 8 .
Lemma 3.5 (Lagrange interpolation). Let A ≥ 2 A\ge2 A ≥ 2 0 ≤ d ≤ A 0\le d\le A 0 ≤ d ≤ A s 0 < ⋯ < s d s_0<\cdots<s_d s 0 < ⋯ < s d { 0 } ∪ [ A ] \{0\}\cup[A] { 0 } ∪ [ A ]
L i ( x ) = ∏ 0 ≤ h ≤ d h ≠ i x − s h s i − s h ( 0 ≤ i ≤ d ) . L_i(x)=\prod_{\substack{0\le h\le d\\h\ne i}}\frac{x-s_h}{s_i-s_h}\qquad(0\le i\le d). L i ( x ) = 0 ≤ h ≤ d h = i ∏ s i − s h x − s h ( 0 ≤ i ≤ d ) . Every polynomial P P P d d d P ( x ) = ∑ i = 0 d P ( s i ) L i ( x ) P(x)=\sum_{i=0}^{d}P(s_i)L_i(x) P ( x ) = ∑ i = 0 d P ( s i ) L i ( x ) t ∈ { 0 } ∪ [ A ] t\in\{0\}\cup[A] t ∈ { 0 } ∪ [ A ] ∑ i = 0 d ∣ L i ( t ) ∣ ≤ 4 A − 1 \sum_{i=0}^{d}|L_i(t)|\le4^{A-1} ∑ i = 0 d ∣ L i ( t ) ∣ ≤ 4 A − 1
The following lemma provides bounds on inverse moments of binomial random variables. These estimates will be used to control the inverse block-count factors that arise when averaging the bounds on the Newton coefficients, required later in the proof of Theorem 2.6 . Importantly, this result does not require independence between the random variables.
Lemma 3.6 (Inverse binomial moments). Let m ≥ 1 m\ge1 m ≥ 1 a , b ∈ ( 0 , 1 ] a,b\in(0,1] a , b ∈ ( 0 , 1 ] Y , Z Y,Z Y , Z Bin ( m − 1 , a ) \operatorname{Bin}(m-1,a) Bin ( m − 1 , a ) Bin ( m − 1 , b ) \operatorname{Bin}(m-1,b) Bin ( m − 1 , b )
E [ ( 1 + Y ) − 1 ] = 1 − ( 1 − a ) m m a ≤ 1 m a . \mathbb{E}[(1+Y)^{-1}]=\frac{1-(1-a)^m}{ma}\le\frac{1}{ma}. E [( 1 + Y ) − 1 ] = ma 1 − ( 1 − a ) m ≤ ma 1 . For β , γ ≥ 0 \beta,\gamma\ge0 β , γ ≥ 0 β + γ ≤ 1 \beta+\gamma\le1 β + γ ≤ 1
E [ ( 1 + Y ) − β ( 1 + Z ) − γ ] ≤ ( m a ) − β ( m b ) − γ . \mathbb{E}\left[(1+Y)^{-\beta}(1+Z)^{-\gamma}\right]\le(ma)^{-\beta}(mb)^{-\gamma}. E [ ( 1 + Y ) − β ( 1 + Z ) − γ ] ≤ ( ma ) − β ( mb ) − γ . Proof. Since Y ∼ Bin ( m − 1 , a ) Y \sim\operatorname{Bin}(m-1,a) Y ∼ Bin ( m − 1 , a )
E [ ( 1 + Y ) − 1 ] = ∫ 0 1 E [ t Y ] d t = ∫ 0 1 ( 1 − a + a t ) m − 1 d t = 1 − ( 1 − a ) m m a ≤ 1 m a . \mathbb{E}[(1+Y)^{-1}] = \int_0^1 \mathbb{E}[t^Y]\,\mathrm{d}t = \int_0^1 (1-a+at)^{m-1}\,\mathrm{d}t = \frac{1-(1-a)^m}{ma} \le\frac{1}{ma}. E [( 1 + Y ) − 1 ] = ∫ 0 1 E [ t Y ] d t = ∫ 0 1 ( 1 − a + a t ) m − 1 d t = ma 1 − ( 1 − a ) m ≤ ma 1 . The same bound holds for Z Z Z b b b a a a β , γ , 1 − β − γ \beta,\gamma,1-\beta-\gamma β , γ , 1 − β − γ 1 1 1
E [ ( 1 + Y ) − β ( 1 + Z ) − γ ] ≤ E [ ( 1 + Y ) − 1 ] β E [ ( 1 + Z ) − 1 ] γ ≤ ( m a ) − β ( m b ) − γ . \mathbb{E}[(1+Y)^{-\beta}(1+Z)^{-\gamma}] \le\mathbb{E}[(1+Y)^{-1}]^\beta\mathbb{E}[(1+Z)^{-1}]^\gamma\le(ma)^{-\beta}(mb)^{-\gamma}. E [( 1 + Y ) − β ( 1 + Z ) − γ ] ≤ E [( 1 + Y ) − 1 ] β E [( 1 + Z ) − 1 ] γ ≤ ( ma ) − β ( mb ) − γ . Hybrid arguments and moment matching
As discussed in the overview, interpolation between multiplicity distributions turns the global comparison into a one-coordinate calculation. This is a reminiscence of the quantum hybrid argument in [7 ] . The two lemmas of this section make this reduction explicit.
We start by defining a new notion of continuous hybrid argument. Then we explain why it is generalizing the usual one. Finally, we state a lemma that will be use to exploit the moment-matching condition.
In this full subsection, fix integers A , m ≥ 1 A,m \ge1 A , m ≥ 1 S = { 0 } ∪ [ A ] S=\{0\}\cup[A] S = { 0 } ∪ [ A ] A A A m m m S S S
Continuous hybrid argument
Let h : S m → [ 0 , 1 ] h:S^m\to[0,1] h : S m → [ 0 , 1 ] z = ( w , s ) ∈ S m z=(w,s)\in S^m z = ( w , s ) ∈ S m w ∈ S m − 1 w\in S^{m-1} w ∈ S m − 1 s ∈ S s\in S s ∈ S q w ( s ) = h ( w , s ) = h ( z ) q_w(s)=h(w,s)=h(z) q w ( s ) = h ( w , s ) = h ( z )
The following derivative identity in Lemma 3.7 provides a continuous version of the usual hybrid bound. We will elaborate on this after presenting its proof. Its final inequality additionally takes the absolute value inside the expectation over w w w
Lemma 3.7 (Continuous hybrid argument). Let h : S m → [ 0 , 1 ] h:S^m\to[0,1] h : S m → [ 0 , 1 ] q w ( s ) = h ( w , s ) q_w(s)=h(w,s) q w ( s ) = h ( w , s ) w ∈ S m − 1 w\in S^{m-1} w ∈ S m − 1 ( π u ) 0 ≤ u ≤ 1 (\pi_u)_{0\le u\le1} ( π u ) 0 ≤ u ≤ 1 C 1 C^1 C 1 S S S F ( u ) = E π u ⊗ m [ h ] F(u)=\mathbb{E}_{\pi_u^{\otimes m}}[h] F ( u ) = E π u ⊗ m [ h ] π ˙ u ( s ) = d d u π u ( s ) \dot{\pi}_u(s)=\frac{\mathrm{d}}{\mathrm{d}u}\pi_u(s) π ˙ u ( s ) = d u d π u ( s )
F ′ ( u ) = m E w ∼ π u ⊗ ( m − 1 ) [ ∑ s ∈ S π ˙ u ( s ) q w ( s ) ] . (13) F'(u)=m\,\mathbb{E}_{w\sim\pi_u^{\otimes(m-1)}}\left[\sum_{s\in S}\dot{\pi}_u(s)q_w(s)\right]. \tag*{(13)} F ′ ( u ) = m E w ∼ π u ⊗ ( m − 1 ) [ s ∈ S ∑ π ˙ u ( s ) q w ( s ) ] . (13) Consequently,
∣ F ( 1 ) − F ( 0 ) ∣ ≤ m ∫ 0 1 E w ∼ π u ⊗ ( m − 1 ) [ ∣ ∑ s ∈ S π ˙ u ( s ) q w ( s ) ∣ ] d u . (14) |F(1)-F(0)|\le m\int_0^1\mathbb{E}_{w\sim\pi_u^{\otimes(m-1)}}\left[\left|\sum_{s\in S}\dot{\pi}_u(s)q_w(s)\right|\right]\,\mathrm{d}u. \tag*{(14)} ∣ F ( 1 ) − F ( 0 ) ∣ ≤ m ∫ 0 1 E w ∼ π u ⊗ ( m − 1 ) [ s ∈ S ∑ π ˙ u ( s ) q w ( s ) ] d u . (14) Proof. Writing the expectation as a finite sum and differentiating each product term gives us
F ′ ( u ) = d d u ( ∑ z ∈ S m h ( z ) ∏ j = 1 m π u ( z j ) ) = ∑ i = 1 m ∑ z ∈ S m h ( z ) π ˙ u ( z i ) ∏ 1 ≤ j ≤ m j ≠ i π u ( z j ) . F'(u)=\frac{d}{du}\left(\sum_{\mathbf{z}\in S^m}h(\mathbf{z})\prod_{j=1}^{m}\pi_u(z_j)\right)
=\sum_{i=1}^{m}\sum_{\mathbf{z}\in S^m}h(\mathbf{z})\dot{\pi}_u(z_i)\prod_{\substack{1\leq j\leq m\\j\ne i}}\pi_u(z_j). F ′ ( u ) = d u d ( z ∈ S m ∑ h ( z ) j = 1 ∏ m π u ( z j ) ) = i = 1 ∑ m z ∈ S m ∑ h ( z ) π ˙ u ( z i ) 1 ≤ j ≤ m j = i ∏ π u ( z j ) . For each fixed i i i s = z i s=z_i s = z i w = ( z 1 , … , z i − 1 , z i + 1 , … , z m ) \mathbf{w}=(z_1,\ldots,z_{i-1},z_{i+1},\ldots,z_m) w = ( z 1 , … , z i − 1 , z i + 1 , … , z m ) h ( z ) = h ( w , s ) = q w ( s ) h(\mathbf{z})=h(\mathbf{w},s)=q_{\mathbf{w}}(s) h ( z ) = h ( w , s ) = q w ( s )
∑ w ∈ S m − 1 ( ∏ j = 1 m − 1 π u ( w j ) ) ∑ s ∈ S π ˙ u ( s ) q w ( s ) = E w ∼ π u ⊗ ( m − 1 ) [ ∑ s ∈ S π ˙ u ( s ) q w ( s ) ] . \sum_{\mathbf{w}\in S^{m-1}}\left(\prod_{j=1}^{m-1}\pi_u(w_j)\right)\sum_{s\in S}\dot{\pi}_u(s)q_{\mathbf{w}}(s)
=\mathbb{E}_{\mathbf{w}\sim\pi_u^{\otimes(m-1)}}\left[\sum_{s\in S}\dot{\pi}_u(s)q_{\mathbf{w}}(s)\right]. w ∈ S m − 1 ∑ ( j = 1 ∏ m − 1 π u ( w j ) ) s ∈ S ∑ π ˙ u ( s ) q w ( s ) = E w ∼ π u ⊗ ( m − 1 ) [ s ∈ S ∑ π ˙ u ( s ) q w ( s ) ] . This expression is independent of i i i i i i (13) . Finally, F F F C 1 C^1 C 1 ∣ F ( 1 ) − F ( 0 ) ∣ ≤ ∫ 0 1 ∣ F ′ ( u ) ∣ d u |F(1)-F(0)|\leq\int_0^1|F'(u)|\,du ∣ F ( 1 ) − F ( 0 ) ∣ ≤ ∫ 0 1 ∣ F ′ ( u ) ∣ d u ∣ E [ X ] ∣ ≤ E [ ∣ X ∣ ] |\mathbb{E}[X]|\leq\mathbb{E}[|X|] ∣ E [ X ] ∣ ≤ E [ ∣ X ∣ ]
Connection to standard hybrid arguments
In our applications, these coordinates are multiplicity draws: s s s w \mathbf{w} w m − 1 m-1 m − 1 h ( z ) h(\mathbf{z}) h ( z ) z \mathbf{z} z D c ( z ) \mathcal{D}_{c(\mathbf{z})} D c ( z ) h h h (5) of Remark 2.2, if each coordinate of z \mathbf{z} z π \pi π S S S
Pr f ∼ Π N [ A f = 1 ] = E z ∼ π ⊗ m [ h ( z ) ] . \Pr_{f\sim\Pi_N}[A^f=1]=\mathbb{E}_{\mathbf{z}\sim\pi^{\otimes m}}[h(\mathbf{z})]. f ∼ Π N Pr [ A f = 1 ] = E z ∼ π ⊗ m [ h ( z )] . Standard hybrid argument We now describe the usual hybrid argument to analyze the success probability of any given algorithm against two different input distributions. For two probability distributions π 0 , π 1 \pi_0,\pi_1 π 0 , π 1 S S S
H i = E z ∼ π 1 ⊗ i ⊗ π 0 ⊗ ( m − i ) [ h ( z ) ] ( 0 ≤ i ≤ m ) . H_i=\mathbb{E}_{\mathbf{z}\sim\pi_1^{\otimes i}\otimes\pi_0^{\otimes(m-i)}}[h(\mathbf{z})]\qquad(0\leq i\leq m). H i = E z ∼ π 1 ⊗ i ⊗ π 0 ⊗ ( m − i ) [ h ( z )] ( 0 ≤ i ≤ m ) . We are interested in the quantity H m − H 0 H_m-H_0 H m − H 0 π 0 \pi_0 π 0 π 1 \pi_1 π 1 H m − H 0 = ∑ i = 0 m − 1 ( H i + 1 − H i ) H_m-H_0=\sum_{i=0}^{m-1}(H_{i+1}-H_i) H m − H 0 = ∑ i = 0 m − 1 ( H i + 1 − H i )
H i + 1 − H i = E w ∼ π 1 ⊗ i ⊗ π 0 ⊗ ( m − 1 − i ) [ ∑ s ∈ S ( π 1 ( s ) − π 0 ( s ) ) q w ( s ) ] . H_{i+1}-H_i=\mathbb{E}_{\mathbf{w}\sim\pi_1^{\otimes i}\otimes\pi_0^{\otimes(m-1-i)}}\left[\sum_{s\in S}(\pi_1(s)-\pi_0(s))q_{\mathbf{w}}(s)\right]. H i + 1 − H i = E w ∼ π 1 ⊗ i ⊗ π 0 ⊗ ( m − 1 − i ) [ s ∈ S ∑ ( π 1 ( s ) − π 0 ( s )) q w ( s ) ] . Continuous hybrid argument We now give a continuous version of this argument in Lemma 3.7 . Let ( π u ) 0 ≤ u ≤ 1 (\pi_u)_{0\leq u\leq1} ( π u ) 0 ≤ u ≤ 1 C 1 C^1 C 1 S S S π 0 \pi_0 π 0 π 1 \pi_1 π 1
F ( u ) = E z ∼ π u ⊗ m [ h ( z ) ] , π ˙ u ( s ) = d d u π u ( s ) , ∥ π ˙ u ∥ 1 = ∑ s ∈ S ∣ π ˙ u ( s ) ∣ . F(u)=\mathbb{E}_{\mathbf{z}\sim\pi_u^{\otimes m}}[h(\mathbf{z})],\qquad\dot{\pi}_u(s)=\frac{d}{du}\pi_u(s),\qquad\|\dot{\pi}_u\|_1=\sum_{s\in S}|\dot{\pi}_u(s)|. F ( u ) = E z ∼ π u ⊗ m [ h ( z )] , π ˙ u ( s ) = d u d π u ( s ) , ∥ π ˙ u ∥ 1 = s ∈ S ∑ ∣ π ˙ u ( s ) ∣. Here F ( 0 ) = H 0 F(0)=H_0 F ( 0 ) = H 0 F ( 1 ) = H m F(1)=H_m F ( 1 ) = H m π u = ( 1 − u ) π 0 + u π 1 \pi_u=(1-u)\pi_0+u\pi_1 π u = ( 1 − u ) π 0 + u π 1
F ( u ) = ∑ i = 0 m ( m i ) u i ( 1 − u ) m − i H i . F(u)=\sum_{i=0}^{m}\binom{m}{i}u^i(1-u)^{m-i}H_i. F ( u ) = i = 0 ∑ m ( i m ) u i ( 1 − u ) m − i H i . Differentiating with respect to u u u
F ′ ( u ) = ∑ i = 1 m i ( m i ) u i − 1 ( 1 − u ) m − i H i − ∑ i = 0 m − 1 ( m − i ) ( m i ) u i ( 1 − u ) m − 1 − i H i = m ∑ i = 0 m − 1 ( m − 1 i ) u i ( 1 − u ) m − 1 − i ( H i + 1 − H i ) . \begin{aligned}
F'(u)&=\sum_{i=1}^{m}i\binom{m}{i}u^{i-1}(1-u)^{m-i}H_i-\sum_{i=0}^{m-1}(m-i)\binom{m}{i}u^i(1-u)^{m-1-i}H_i\\
&=m\sum_{i=0}^{m-1}\binom{m-1}{i}u^i(1-u)^{m-1-i}(H_{i+1}-H_i).
\end{aligned} F ′ ( u ) = i = 1 ∑ m i ( i m ) u i − 1 ( 1 − u ) m − i H i − i = 0 ∑ m − 1 ( m − i ) ( i m ) u i ( 1 − u ) m − 1 − i H i = m i = 0 ∑ m − 1 ( i m − 1 ) u i ( 1 − u ) m − 1 − i ( H i + 1 − H i ) . The weights are nonnegative and each integrates to 1, so
∣ F ( 1 ) − F ( 0 ) ∣ = ∣ H m − H 0 ∣ ≤ ∫ 0 1 ∣ F ′ ( u ) ∣ d u ≤ ∑ i = 0 m − 1 ∣ H i + 1 − H i ∣ . \lvert F(1)-F(0)\rvert=\lvert H_m-H_0\rvert\le\int_0^1\lvert F'(u)\rvert\,du\le\sum_{i=0}^{m-1}\lvert H_{i+1}-H_i\rvert. ∣ F ( 1 ) − F ( 0 )∣ = ∣ H m − H 0 ∣ ≤ ∫ 0 1 ∣ F ′ ( u )∣ d u ≤ i = 0 ∑ m − 1 ∣ H i + 1 − H i ∣ . Thus the derivative identity in Lemma 3.7 recovers the standard hybrid bound.
Final remark The continuous formulation in Lemma 3.7 is useful in § 4 because the remaining draws are independent and have the same distribution: the count Y s = ∣ { j : w j = s } ∣ Y_s=\lvert\{j:w_j=s\}\rvert Y s = ∣{ j : w j = s }∣ Bin ( m − 1 , π u ( s ) ) \operatorname{Bin}(m-1,\pi_u(s)) Bin ( m − 1 , π u ( s )) Lemma 4.1 . A fixed discrete hybrid generally has two different coordinate distributions and would require corresponding count estimates. For the polynomial proof in § 3 , the standard discrete hybrid would give the same bound.
Moment matching
Moment matching allows us to replace q w q_w q w q w − P w q_w-P_w q w − P w Lemma 3.7 . We state this below in a lemma that will provide us a common comparison bound for Theorems 2.5 and 2.6 . It also bounds the contribution of exceptional choices of w w w
Lemma 3.8. Let h : S m → [ 0 , 1 ] h:S^m\to[0,1] h : S m → [ 0 , 1 ] q w ( s ) = h ( w , s ) q_w(s)=h(w,s) q w ( s ) = h ( w , s ) w ∈ S m − 1 w\in S^{m-1} w ∈ S m − 1 ( π u ) 0 ≤ u ≤ 1 (\pi_u)_{0\le u\le1} ( π u ) 0 ≤ u ≤ 1 C 1 C^1 C 1 S S S r − 1 r-1 r − 1 u u u r ≥ 1 r\ge1 r ≥ 1 F ( u ) = E π u ⊗ m [ h ] F(u)=\mathbb{E}_{\pi_u^{\otimes m}}[h] F ( u ) = E π u ⊗ m [ h ] w ∈ S m − 1 w\in S^{m-1} w ∈ S m − 1 P w P_w P w r r r G ⊆ S m − 1 G\subseteq S^{m-1} G ⊆ S m − 1
∣ F ( 1 ) − F ( 0 ) ∣ ≤ m ∫ 0 1 E w ∼ π u ⊗ ( m − 1 ) [ 1 G ∣ ∑ s ∈ S π ˙ u ( s ) ( q w ( s ) − P w ( s ) ) ∣ ] d u + m ∫ 0 1 ∥ π ˙ u ∥ 1 Pr w ∼ π u ⊗ ( m − 1 ) [ w ∉ G ] d u . (15) \begin{aligned}
\lvert F(1)-F(0)\rvert\le{}&m\int_0^1\mathbb{E}_{w\sim\pi_u^{\otimes(m-1)}}\left[\mathbf{1}_{G}\left\lvert\sum_{s\in S}\dot{\pi}_u(s)(q_w(s)-P_w(s))\right\rvert\right]\,du\\
&+m\int_0^1\lVert\dot{\pi}_u\rVert_1\Pr_{w\sim\pi_u^{\otimes(m-1)}}[w\notin G]\,du. \tag*{(15)}
\end{aligned} ∣ F ( 1 ) − F ( 0 )∣ ≤ m ∫ 0 1 E w ∼ π u ⊗ ( m − 1 ) [ 1 G s ∈ S ∑ π ˙ u ( s ) ( q w ( s ) − P w ( s )) ] d u + m ∫ 0 1 ∥ π ˙ u ∥ 1 w ∼ π u ⊗ ( m − 1 ) Pr [ w ∈ / G ] d u . (15) Proof. Fix w \mathbf{w} w u , v ∈ [ 0 , 1 ] u,v \in[0,1] u , v ∈ [ 0 , 1 ] π u , π v \pi_u,\pi_v π u , π v r − 1 r-1 r − 1 deg P w < r \deg P_{\mathbf{w}} < r deg P w < r Lemma 3.4 gives ∑ s ∈ S ( π u ( s ) − π v ( s ) ) P w ( s ) = 0 \sum_{s\in S}(\pi_u(s)-\pi_v(s))P_{\mathbf{w}}(s)=0 ∑ s ∈ S ( π u ( s ) − π v ( s )) P w ( s ) = 0 ∑ s ∈ S π u ( s ) P w ( s ) \sum_{s\in S}\pi_u(s)P_{\mathbf{w}}(s) ∑ s ∈ S π u ( s ) P w ( s ) u u u
Therefore, at every point where it is differentiable,
0 = d d u ( ∑ s ∈ S π u ( s ) P w ( s ) ) = ∑ s ∈ S π ˙ u ( s ) P w ( s ) . 0=\frac{d}{du}\left(\sum_{s\in S}\pi_u(s)P_{\mathbf{w}}(s)\right)=\sum_{s\in S}\dot{\pi}_u(s)P_{\mathbf{w}}(s). 0 = d u d ( s ∈ S ∑ π u ( s ) P w ( s ) ) = s ∈ S ∑ π ˙ u ( s ) P w ( s ) . Consequently,
∑ s ∈ S π ˙ u ( s ) q w ( s ) = ∑ s ∈ S π ˙ u ( s ) ( q w ( s ) − P w ( s ) ) . (16) \sum_{s\in S}\dot{\pi}_u(s)q_{\mathbf{w}}(s)=\sum_{s\in S}\dot{\pi}_u(s)\left(q_{\mathbf{w}}(s)-P_{\mathbf{w}}(s)\right). \tag*{(16)} s ∈ S ∑ π ˙ u ( s ) q w ( s ) = s ∈ S ∑ π ˙ u ( s ) ( q w ( s ) − P w ( s ) ) . (16) Equation (14) of Lemma 3.7 , split over G \mathcal{G} G
∣ F ( 1 ) − F ( 0 ) ∣ ≤ m ∫ 0 1 E w ∼ π u ⊗ ( m − 1 ) [ 1 G ∣ ∑ s ∈ S π ˙ u ( s ) q w ( s ) ∣ ] d u + m ∫ 0 1 E w ∼ π u ⊗ ( m − 1 ) [ 1 G c ∣ ∑ s ∈ S π ˙ u ( s ) q w ( s ) ∣ ] d u . \lvert F(1)-F(0)\rvert\leq m\int_0^1 \mathbb{E}_{\mathbf{w}\sim\pi_u^{\otimes(m-1)}}\left[\mathbf{1}_{\mathcal{G}}\left\lvert\sum_{s\in S}\dot{\pi}_u(s)q_{\mathbf{w}}(s)\right\rvert\right]\,du
+m\int_0^1 \mathbb{E}_{\mathbf{w}\sim\pi_u^{\otimes(m-1)}}\left[\mathbf{1}_{\mathcal{G}^{c}}\left\lvert\sum_{s\in S}\dot{\pi}_u(s)q_{\mathbf{w}}(s)\right\rvert\right]\,du. ∣ F ( 1 ) − F ( 0 )∣ ≤ m ∫ 0 1 E w ∼ π u ⊗ ( m − 1 ) [ 1 G s ∈ S ∑ π ˙ u ( s ) q w ( s ) ] d u + m ∫ 0 1 E w ∼ π u ⊗ ( m − 1 ) [ 1 G c s ∈ S ∑ π ˙ u ( s ) q w ( s ) ] d u . We apply (16) in the first term. For the second term, 0 ≤ q w ≤ 1 0\leq q_{\mathbf{w}}\leq1 0 ≤ q w ≤ 1
∣ ∑ s ∈ S π ˙ u ( s ) q w ( s ) ∣ ≤ ∑ s ∈ S ∣ π ˙ u ( s ) ∣ q w ( s ) ≤ ∥ π ˙ u ∥ 1 . \left\lvert\sum_{s\in S}\dot{\pi}_u(s)q_{\mathbf{w}}(s)\right\rvert\leq\sum_{s\in S}\lvert\dot{\pi}_u(s)\rvert q_{\mathbf{w}}(s)\leq\lVert\dot{\pi}_u\rVert_1. s ∈ S ∑ π ˙ u ( s ) q w ( s ) ≤ s ∈ S ∑ ∣ π ˙ u ( s )∣ q w ( s ) ≤ ∥ π ˙ u ∥ 1 . These bounds prove (15) , completing the proof.
Proof of Theorem 2.5
We are now almost ready to prove our first main theorem. This full subsection is devoted to this. Let us fix the parameters of Theorem 2.5 and let A \mathcal{A} A T T T f : [ N ] → [ N ] f:[N]\to[N] f : [ N ] → [ N ] T = 0 T=0 T = 0
Assume N ≥ max { 8 , 4 A } N\geq\max\{8,4A\} N ≥ max { 8 , 4 A } T ≥ 1 T\geq1 T ≥ 1 T 2 ≤ N / 64 T^2\leq N/64 T 2 ≤ N /64 S = { 0 } ∪ [ A ] S=\{0\}\cup[A] S = { 0 } ∪ [ A ] m = ⌊ N / 2 ⌋ m=\lfloor N/2\rfloor m = ⌊ N /2 ⌋ H = ⌊ N / 4 ⌋ H=\lfloor N/4\rfloor H = ⌊ N /4 ⌋ π b \pi_b π b Z b Z_b Z b b ∈ { 0 , 1 } b\in\{0,1\} b ∈ { 0 , 1 } z ∈ S m \mathbf{z}\in S^m z ∈ S m c ( z ) c(\mathbf{z}) c ( z ) Definition 2.1 , and define
h ( z ) = Pr f ∼ D c ( z ) [ A f = 1 ] . h(\mathbf{z})=\Pr_{f\sim D_{c(\mathbf{z})}}[\mathcal{A}^f=1]. h ( z ) = f ∼ D c ( z ) Pr [ A f = 1 ] . Note that with this symmetrization, h h h z \mathbf{z} z
For w ∈ S m − 1 \mathbf{w}\in S^{m-1} w ∈ S m − 1 w = ∑ i w i w=\sum_i w_i w = ∑ i w i q w ( s ) = h ( w , s ) q_{\mathbf{w}}(s)=h(\mathbf{w},s) q w ( s ) = h ( w , s )
Lemma 3.9 (Taylor approximation). For every w ∈ S m − 1 \mathbf{w}\in S^{m-1} w ∈ S m − 1 w ≤ 3 N / 4 w\leq3N/4 w ≤ 3 N /4 q w q_{\mathbf{w}} q w 2 T 2T 2 T q w q_{\mathbf{w}} q w
q w ( s ) = ∑ j = 0 2 T a w , j s j ( s ∈ S ) , q_{\mathbf{w}}(s)=\sum_{j=0}^{2T}a_{\mathbf{w},j}s^j \qquad(s\in S), q w ( s ) = j = 0 ∑ 2 T a w , j s j ( s ∈ S ) , with real coefficients and satisfying ∣ q w ( z ) ∣ ≤ 1 |q_{\mathbf{w}}(z)| \le1 ∣ q w ( z ) ∣ ≤ 1 z ∈ { 0 } ∪ [ H ] z \in\{0\} \cup[H] z ∈ { 0 } ∪ [ H ] Z Z Z S S S
E Z [ ∣ q w ( Z ) − Q w ( Z ) ∣ ] ≤ 2 A r − 1 ( 2 r ) ! ( 128 T 2 N ) r (17) \mathbb{E}_{Z}[|q_{\mathbf{w}}(Z)-Q_{\mathbf{w}}(Z)|] \le\frac{2A^{r-1}}{(2r)!}\left(\frac{128T^2}{N}\right)^r \tag*{(17)} E Z [ ∣ q w ( Z ) − Q w ( Z ) ∣ ] ≤ ( 2 r )! 2 A r − 1 ( N 128 T 2 ) r (17) where
Q w ( z ) = ∑ j = 0 min { r − 1 , 2 T } a w , j z j . Q_{\mathbf{w}}(z)=\sum_{j=0}^{\min\{r-1,2T\}}a_{\mathbf{w},j}z^j. Q w ( z ) = j = 0 ∑ m i n { r − 1 , 2 T } a w , j z j . Proof. Let us fix w \mathbf{w} w w ≤ 3 N / 4 w \le3N/4 w ≤ 3 N /4 d = 2 T d=2T d = 2 T H ≥ N / 8 H \ge N/8 H ≥ N /8 A ≤ H A \le H A ≤ H d 2 ≤ H / 2 d^2 \le H/2 d 2 ≤ H /2
As in step 2 of Definition 2.1 , for each integer 0 ≤ z ≤ H 0 \le z \le H 0 ≤ z ≤ H c ( z ) \mathbf{c}(z) c ( z ) ( w , z ) (\mathbf{w},z) ( w , z ) N − w − z N-w-z N − w − z N N N w + z ≤ N w+z \le N w + z ≤ N q w q_{\mathbf{w}} q w
q w ( z ) = Pr f ∼ D c ( z ) [ A f = 1 ] ∈ [ 0 , 1 ] . q_{\mathbf{w}}(z)=\Pr_{f\sim D_{\mathbf{c}(z)}}[\mathcal{A}^f=1]\in[0,1]. q w ( z ) = f ∼ D c ( z ) Pr [ A f = 1 ] ∈ [ 0 , 1 ] . For z ∈ S z \in S z ∈ S w + z ≤ N w+z \le N w + z ≤ N h ( w , z ) h(w,z) h ( w , z ) Lemma 3.1 , we know that there is a symmetric polynomial P P P d d d
P ( c ) = Pr f ∼ D c [ A f = 1 ] P(\mathbf{c})=\Pr_{f\sim D_{\mathbf{c}}}[\mathcal{A}^f=1] P ( c ) = f ∼ D c Pr [ A f = 1 ] for every feasible c \mathbf{c} c
Let us write P ( x ) = G ( p 1 ( x ) , … , p d ( x ) ) P(\mathbf{x})=G(p_1(\mathbf{x}),\ldots,p_d(\mathbf{x})) P ( x ) = G ( p 1 ( x ) , … , p d ( x )) G G G d d d 1 ≤ j ≤ d 1\le j\le d 1 ≤ j ≤ d p j ( c ( z ) ) = p j ( w ) + N − w − z + z j p_j(\mathbf{c}(z))=p_j(\mathbf{w})+N-w-z+z^j p j ( c ( z )) = p j ( w ) + N − w − z + z j z z z q w ( z ) q_{\mathbf{w}}(z) q w ( z ) 2 T 2T 2 T z \mathbf{z} z
q w ( z ) = G ( ( p j ( w ) + ( N − w − z ) + z j ) j = 1 d ) = ∑ j = 0 2 T a w , j z j q_{\mathbf{w}}(z)=G\left(\left(p_j(\mathbf{w})+(N-w-z)+z^j\right)_{j=1}^{d}\right)=\sum_{j=0}^{2T}a_{\mathbf{w},j}z^j q w ( z ) = G ( ( p j ( w ) + ( N − w − z ) + z j ) j = 1 d ) = j = 0 ∑ 2 T a w , j z j extends the integer values and has degree at most d d d
Since Q w Q_{\mathbf{w}} Q w r r r
E [ ∣ q w ( Z ) − Q w ( Z ) ∣ ] ≤ 2 ( 2 r ) ! ( 4 d 2 H ) r E [ Z r ] ≤ 2 A r − 1 ( 2 r ) ! ( 128 T 2 N ) r , \mathbb{E}[|q_{\mathbf{w}}(Z)-Q_{\mathbf{w}}(Z)|]\le\frac{2}{(2r)!}\left(\frac{4d^2}{H}\right)^r\mathbb{E}[Z^r]\le\frac{2A^{r-1}}{(2r)!}\left(\frac{128T^2}{N}\right)^r, E [ ∣ q w ( Z ) − Q w ( Z ) ∣ ] ≤ ( 2 r )! 2 ( H 4 d 2 ) r E [ Z r ] ≤ ( 2 r )! 2 A r − 1 ( N 128 T 2 ) r , using the fact that E [ Z r ] ≤ A r − 1 E [ Z ] = A r − 1 \mathbb{E}[Z^r]\le A^{r-1}\mathbb{E}[Z]=A^{r-1} E [ Z r ] ≤ A r − 1 E [ Z ] = A r − 1 H ≥ N / 8 H\ge N/8 H ≥ N /8 d = 2 T d=2T d = 2 T
Finally, we are ready to prove our first main theorem.
End of proof of Theorem 2.5 . By Proposition 2.4 and the moment matching condition (7) , the distributions π 0 , π 1 \pi_0,\pi_1 π 0 , π 1 Z 0 , Z 1 Z_0,Z_1 Z 0 , Z 1 r − 1 r-1 r − 1 S S S π u = ( 1 − u ) π 0 + u π 1 \pi_u=(1-u)\pi_0+u\pi_1 π u = ( 1 − u ) π 0 + u π 1 0 ≤ u ≤ 1 0\le u\le1 0 ≤ u ≤ 1 r − 1 r-1 r − 1
E s ∼ π u [ s j ] = ( 1 − u ) E [ Z 0 j ] + u E [ Z 1 j ] = E [ Z 0 j ] ( 1 ≤ j ≤ r − 1 ) . \mathbb{E}_{s\sim\pi_u}[s^j]=(1-u)\mathbb{E}[Z_0^j]+u\mathbb{E}[Z_1^j]=\mathbb{E}[Z_0^j]\qquad(1\le j\le r-1). E s ∼ π u [ s j ] = ( 1 − u ) E [ Z 0 j ] + u E [ Z 1 j ] = E [ Z 0 j ] ( 1 ≤ j ≤ r − 1 ) . Let F ( u ) = E w ∼ π ~ u ⊗ m [ h ( z ) ] F(u)=\mathbb{E}_{\mathbf{w}\sim\tilde{\pi}_u^{\otimes m}}[h(\mathbf{z})] F ( u ) = E w ∼ π ~ u ⊗ m [ h ( z )] F ( b ) = Pr f ∼ Π b , N [ A f = 1 ] F(b)=\Pr_{f\sim\Pi_{b,N}}[\mathcal{A}^f=1] F ( b ) = Pr f ∼ Π b , N [ A f = 1 ] b = 0 , 1 b=0,1 b = 0 , 1 Lemma 3.8 with
G = { w ∈ S m − 1 : w ≤ 3 N / 4 } , P w = { Q w , w ∈ G , 0 , w ∉ G . \mathcal{G}=\{\mathbf{w}\in S^{m-1}:\mathbf{w}\leq3N/4\},\qquad
P_{\mathbf{w}}=
\begin{cases}
Q_{\mathbf{w}}, & \mathbf{w}\in\mathcal{G},\\
0, & \mathbf{w}\notin\mathcal{G}.
\end{cases} G = { w ∈ S m − 1 : w ≤ 3 N /4 } , P w = { Q w , 0 , w ∈ G , w ∈ / G . where Q w Q_{\mathbf{w}} Q w Lemma 3.9 for the given w \mathbf{w} w r r r
∣ F ( 1 ) − F ( 0 ) ∣ ≤ m ∫ 0 1 E w ∼ π ~ u ⊗ ( m − 1 ) [ ∣ 1 G ∑ s ∈ S π ~ u ( s ) ( q w ( s ) − P w ( s ) ) ∣ ] d u |F(1)-F(0)|\leq m\int_0^1\mathbb{E}_{\mathbf{w}\sim\tilde{\pi}_u^{\otimes(m-1)}}\left[\left|\mathbf{1}_{\mathcal{G}}\sum_{s\in S}\tilde{\pi}_u(s)(q_{\mathbf{w}}(s)-P_{\mathbf{w}}(s))\right|\right]\,du ∣ F ( 1 ) − F ( 0 ) ∣ ≤ m ∫ 0 1 E w ∼ π ~ u ⊗ ( m − 1 ) [ 1 G s ∈ S ∑ π ~ u ( s ) ( q w ( s ) − P w ( s )) ] d u + m ∫ 0 1 ∥ π ~ u ∥ 1 Pr w ∼ π ~ u ⊗ ( m − 1 ) [ w ∉ G ] d u . {}+m\int_0^1\|\tilde{\pi}_u\|_1\Pr_{\mathbf{w}\sim\tilde{\pi}_u^{\otimes(m-1)}}[\mathbf{w}\notin\mathcal{G}]\,du. + m ∫ 0 1 ∥ π ~ u ∥ 1 w ∼ π ~ u ⊗ ( m − 1 ) Pr [ w ∈ / G ] d u . On G \mathcal{G} G Lemma 3.9 bounds the residual inside the expectation above by
∣ ∑ s ∈ S π ~ u ( s ) ( q w ( s ) − P w ( s ) ) ∣ ≤ ∑ s ∈ S ( π 0 ( s ) + π 1 ( s ) ) ∣ q w ( s ) − Q w ( s ) ∣ = ∑ b = 0 1 ∑ s ∈ S Pr [ Z b = s ] ∣ q w ( s ) − Q w ( s ) ∣ = ∑ b = 0 1 E [ ∣ q w ( Z b ) − Q w ( Z b ) ∣ ] ≤ 4 A r − 1 ( 2 r ) ! ( 128 T 2 N ) r . \begin{aligned}
\left|\sum_{s\in S}\tilde{\pi}_u(s)(q_{\mathbf{w}}(s)-P_{\mathbf{w}}(s))\right|
\leq\sum_{s\in S}(\pi_0(s)+\pi_1(s))|q_{\mathbf{w}}(s)-Q_{\mathbf{w}}(s)| \\
&=\sum_{b=0}^{1}\sum_{s\in S}\Pr[Z_b=s]|q_{\mathbf{w}}(s)-Q_{\mathbf{w}}(s)| \\
&=\sum_{b=0}^{1}\mathbb{E}[|q_{\mathbf{w}}(Z_b)-Q_{\mathbf{w}}(Z_b)|] \\
&\leq\frac{4A^{r-1}}{(2r)!}\left(\frac{128T^2}{N}\right)^r.
\end{aligned} s ∈ S ∑ π ~ u ( s ) ( q w ( s ) − P w ( s )) ≤ s ∈ S ∑ ( π 0 ( s ) + π 1 ( s )) ∣ q w ( s ) − Q w ( s ) ∣ = b = 0 ∑ 1 s ∈ S ∑ Pr [ Z b = s ] ∣ q w ( s ) − Q w ( s ) ∣ = b = 0 ∑ 1 E [ ∣ q w ( Z b ) − Q w ( Z b ) ∣ ] ≤ ( 2 r )! 4 A r − 1 ( N 128 T 2 ) r . where the first inequality uses the fact that π ~ u = π 1 − π 0 \tilde{\pi}_u=\pi_1-\pi_0 π ~ u = π 1 − π 0
Under π ~ u ⊗ ( m − 1 ) \tilde{\pi}_u^{\otimes(m-1)} π ~ u ⊗ ( m − 1 ) A A A E [ w ] = m − 1 ≤ N / 2 \mathbb{E}[\mathbf{w}]=m-1\leq N/2 E [ w ] = m − 1 ≤ N /2 [27 ] gives, for every u u u
Pr w ∼ π ~ u ⊗ ( m − 1 ) [ w ∉ G ] ≤ exp ( − N 4 A 2 ) . (18) \Pr_{\mathbf{w}\sim\tilde{\pi}_u^{\otimes(m-1)}}[\mathbf{w}\notin\mathcal{G}]
\leq\exp\left(-\frac{N}{4A^2}\right). \tag*{(18)} w ∼ π ~ u ⊗ ( m − 1 ) Pr [ w ∈ / G ] ≤ exp ( − 4 A 2 N ) . (18) Also, ∥ π ~ u ∥ 1 ≤ ∥ π 1 ∥ 1 + ∥ π 0 ∥ 1 = 2 \|\tilde{\pi}_u\|_1\leq\|\pi_1\|_1+\|\pi_0\|_1=2 ∥ π ~ u ∥ 1 ≤ ∥ π 1 ∥ 1 + ∥ π 0 ∥ 1 = 2 m ≤ N / 2 m\leq N/2 m ≤ N /2
∣ Pr f ∼ Π 0 , N [ A f = 1 ] − Pr f ∼ Π 1 , N [ A f = 1 ] ∣ = ∣ F ( 0 ) − F ( 1 ) ∣ ≤ m ∫ 0 1 ( 4 A r − 1 ( 2 r ) ! ( 128 T 2 N ) r + 2 exp ( − N 4 A 2 ) ) d u ≤ 2 × 128 r A r − 1 T 2 r ( 2 r ) ! N r − 1 + N exp ( − N 4 A 2 ) . (19) \begin{aligned}
\left|\Pr_{f\sim\Pi_{0,N}}[\mathcal{A}^f=1]-\Pr_{f\sim\Pi_{1,N}}[\mathcal{A}^f=1]\right|=|F(0)-F(1)| \\
&\leq m\int_0^1\left(\frac{4A^{r-1}}{(2r)!}\left(\frac{128T^2}{N}\right)^r+2\exp\left(-\frac{N}{4A^2}\right)\right)\,du \\
&\leq\frac{2\times128^r A^{r-1}T^{2r}}{(2r)!N^{r-1}}+N\exp\left(-\frac{N}{4A^2}\right). \tag*{(19)}
\end{aligned} f ∼ Π 0 , N Pr [ A f = 1 ] − f ∼ Π 1 , N Pr [ A f = 1 ] = ∣ F ( 0 ) − F ( 1 ) ∣ ≤ m ∫ 0 1 ( ( 2 r )! 4 A r − 1 ( N 128 T 2 ) r + 2 exp ( − 4 A 2 N ) ) d u ≤ ( 2 r )! N r − 1 2 × 12 8 r A r − 1 T 2 r + N exp ( − 4 A 2 N ) . (19) Using ( 2 r ) ! ≥ ( 2 r / e ) 2 r (2r)!\geq(2r/e)^{2r} ( 2 r )! ≥ ( 2 r / e ) 2 r 2 ≤ 2 r 2\leq2^r 2 ≤ 2 r
N A ( 64 e 2 A T 2 r 2 N ) r . \frac{N}{A}\left(\frac{64e^2AT^2}{r^2N}\right)^r. A N ( r 2 N 64 e 2 A T 2 ) r . This proves (8) with C = 64 e 2 C=64e^2 C = 64 e 2 c = 1 / 8 c=1/8 c = 1/8
Stronger bound for fixed support
We prove Theorem 2.6 by the same comparison lemma as the polynomial estimate (Lemma 3.8 ). However, instead of using the Taylor bound, we now apply a truncated Newton expansion. We first give the main proof using the coefficient bound of Lemma 4.1 and the interpolation paths of Lemma 4.2 , which are proved in Subsections 4.2 and 4.3, respectively.
Proof of Theorem 2.6
Let us fix a T T T A \mathcal{A} A f : [ N ] → [ N ] f:[N]\to[N] f : [ N ] → [ N ] p ( f ) = Pr [ A f = 1 ] p(f)=\Pr[\mathcal{A}^{f}=1] p ( f ) = Pr [ A f = 1 ] S = { 0 } ∪ [ A ] S=\{0\}\cup[A] S = { 0 } ∪ [ A ] m = ⌊ N / 2 ⌋ m=\lfloor N/2\rfloor m = ⌊ N /2 ⌋ π b \pi_b π b Z b Z_b Z b b ∈ { 0 , 1 } b\in\{0,1\} b ∈ { 0 , 1 } z ∈ S m z\in S^m z ∈ S m c ( z ) \mathbf{c}(z) c ( z ) Definition 2.1 , and define h ( z ) = E f ∼ D c ( z ) [ p ( f ) ] h(z)=\mathbb{E}_{f\sim D_{\mathbf{c}(z)}}[p(f)] h ( z ) = E f ∼ D c ( z ) [ p ( f )] w ∈ S m − 1 \mathbf{w}\in S^{m-1} w ∈ S m − 1 w = ∑ i w i w=\sum_i w_i w = ∑ i w i q w ( s ) = h ( w , s ) q_{\mathbf{w}}(s)=h(\mathbf{w},s) q w ( s ) = h ( w , s ) s ∈ S s\in S s ∈ S
Let us write the Newton coefficients of q w q_{\mathbf{w}} q w
d ℓ ( w ) = ∑ s = 0 ℓ ( − 1 ) ℓ − s ( ℓ s ) q w ( s ) ( 0 ≤ ℓ ≤ A ) . (20) d_\ell(\mathbf{w})=\sum_{s=0}^{\ell}(-1)^{\ell-s}\binom{\ell}{s}q_{\mathbf{w}}(s)\qquad(0\leq\ell\leq A). \tag*{(20)} d ℓ ( w ) = s = 0 ∑ ℓ ( − 1 ) ℓ − s ( s ℓ ) q w ( s ) ( 0 ≤ ℓ ≤ A ) . (20) Let α j = 1 − 2 1 − j \alpha_j=1-2^{1-j} α j = 1 − 2 1 − j j ≥ 1 j\geq1 j ≥ 1 G = { w ∈ S m − 1 : ∑ i w i ≤ 3 N / 4 } \mathcal{G}=\{\mathbf{w}\in S^{m-1}:\sum_i w_i\leq3N/4\} G = { w ∈ S m − 1 : ∑ i w i ≤ 3 N /4 }
Lemma 4.1. Assume N ≥ 8 A N\geq8A N ≥ 8 A T ≥ 1 T\geq1 T ≥ 1 T 2 ≤ N / 8 T^2\leq N/8 T 2 ≤ N /8 2 ≤ ℓ ≤ A 2\leq\ell\leq A 2 ≤ ℓ ≤ A T ≤ N α ℓ / ( 1 + α ℓ ) T\leq N^{\alpha_\ell/(1+\alpha_\ell)} T ≤ N α ℓ / ( 1 + α ℓ ) π \pi π S S S π ( s ) ≥ a > 0 \pi(s)\geq a>0 π ( s ) ≥ a > 0 s ∈ S s\in S s ∈ S C C C
E w ∼ π ⊗ ( m − 1 ) [ 1 G ( w ) × ∣ d ℓ ( w ) ∣ ] ≤ C ℓ T 1 + α ℓ N ( m a ) − α ℓ , Pr [ G c ] ≤ e − N / ( 4 A 2 ) . \mathbb{E}_{\mathbf{w}\sim\pi^{\otimes(m-1)}}\left[\mathbf{1}_{\mathcal{G}}(\mathbf{w})\times\lvert d_\ell(\mathbf{w})\rvert\right]\leq\frac{C^\ell T^{1+\alpha_\ell}}{N}(ma)^{-\alpha_\ell},\qquad\Pr[\mathcal{G}^{c}]\leq e^{-N/(4A^2)}. E w ∼ π ⊗ ( m − 1 ) [ 1 G ( w ) × ∣ d ℓ ( w )∣ ] ≤ N C ℓ T 1 + α ℓ ( ma ) − α ℓ , Pr [ G c ] ≤ e − N / ( 4 A 2 ) . Lemma 4.2. Let 2 ≤ r ≤ A 2\leq r\leq A 2 ≤ r ≤ A π 0 , π 1 \pi_0,\pi_1 π 0 , π 1 { 0 } ∪ [ A ] \{0\}\cup[A] { 0 } ∪ [ A ] r − 1 r-1 r − 1 δ = ∥ π 1 − π 0 ∥ 1 \delta=\lVert\pi_1-\pi_0\rVert_1 δ = ∥ π 1 − π 0 ∥ 1 ω \omega ω
ω ( s ) ≥ 32 − A δ ( s ∈ { 0 } ∪ [ A ] ) , ∥ ω − π b ∥ 1 ≤ δ ( b = 0 , 1 ) . \omega(s)\geq32^{-A}\delta\quad(s\in\{0\}\cup[A]),\qquad\lVert\omega-\pi_b\rVert_1\leq\delta\quad(b=0,1). ω ( s ) ≥ 3 2 − A δ ( s ∈ { 0 } ∪ [ A ]) , ∥ ω − π b ∥ 1 ≤ δ ( b = 0 , 1 ) . Using these lemmas, we now prove Theorem 2.6 .
Proof of Theorem 2.6. By Proposition 2.4 , the distributions π b \pi_b π b Z b Z_b Z b r − 1 r-1 r − 1 δ = ∥ π 1 − π 0 ∥ 1 ≤ 2 \delta=\lVert\pi_1-\pi_0\rVert_1\leq2 δ = ∥ π 1 − π 0 ∥ 1 ≤ 2 π 0 = π 1 \pi_0=\pi_1 π 0 = π 1 T = 0 T=0 T = 0 δ > 0 \delta>0 δ > 0 T ≥ 1 T\geq1 T ≥ 1 r > A r>A r > A π 0 = π 1 \pi_0=\pi_1 π 0 = π 1 A + 1 A+1 A + 1 A A A 2 ≤ r ≤ A 2\leq r\leq A 2 ≤ r ≤ A N ≥ 8 A N\geq8A N ≥ 8 A T 2 ≤ N / 8 T^2\leq N/8 T 2 ≤ N /8 T 1 + α r > N α r T^{1+\alpha_r}>N^{\alpha_r} T 1 + α r > N α r
T ≤ N α r / ( 1 + α r ) ≤ N α ℓ / ( 1 + α ℓ ) ( ℓ ≥ r ) , T\leq N^{\alpha_r/(1+\alpha_r)}\leq N^{\alpha_\ell/(1+\alpha_\ell)}\qquad(\ell\geq r), T ≤ N α r / ( 1 + α r ) ≤ N α ℓ / ( 1 + α ℓ ) ( ℓ ≥ r ) , so Lemma 4.1 applies to every remaining coefficient. Let ω \omega ω 4.2 4.2 4.2 r − 1 r-1 r − 1 π 0 \pi_0 π 0 π 1 \pi_1 π 1 κ = 32 − A \kappa=32^{-A} κ = 3 2 − A b ∈ { 0 , 1 } b\in\{0,1\} b ∈ { 0 , 1 } S \mathcal{S} S
π b , u = ( 1 − u ) π b + u ω , F b ( u ) = E z ∼ π b , u ⊗ m [ h ( z ) ] ( 0 ≤ u ≤ 1 ) . \pi_{b,u}=(1-u)\pi_b+u\omega,\qquad F_b(u)=\mathbb{E}_{\mathbf{z}\sim\pi_{b,u}^{\otimes m}}[h(\mathbf{z})]\qquad(0\leq u\leq1). π b , u = ( 1 − u ) π b + u ω , F b ( u ) = E z ∼ π b , u ⊗ m [ h ( z )] ( 0 ≤ u ≤ 1 ) . Using the fact that the first ( r − 1 ) (r-1) ( r − 1 ) π b \pi_b π b ω \omega ω π b , u \pi_{b,u} π b , u u u u
π b , u ( s ) ≥ u ω ( s ) ≥ u κ δ ( s ∈ S ) , ∥ π ˙ b , u ∥ 1 = ∥ − π b + ω ∥ 1 ≤ δ . \pi_{b,u}(s)\geq u\omega(s)\geq u\kappa\delta\quad(s\in\mathcal{S}),\qquad\|\dot{\pi}_{b,u}\|_1=\|-\pi_b+\omega\|_1\leq\delta. π b , u ( s ) ≥ u ω ( s ) ≥ u κ δ ( s ∈ S ) , ∥ π ˙ b , u ∥ 1 = ∥ − π b + ω ∥ 1 ≤ δ . Here F b ( 0 ) = Pr f ∼ Π b , N [ A f = 1 ] F_b(0)=\Pr_{f\sim\Pi_{b,N}}[\mathcal{A}^f=1] F b ( 0 ) = Pr f ∼ Π b , N [ A f = 1 ] F b ( 1 ) = E z ∼ ω ⊗ m [ h ( z ) ] F_b(1)=\mathbb{E}_{\mathbf{z}\sim\omega^{\otimes m}}[h(\mathbf{z})] F b ( 1 ) = E z ∼ ω ⊗ m [ h ( z )] ∣ F b ( 1 ) − F b ( 0 ) ∣ |F_b(1)-F_b(0)| ∣ F b ( 1 ) − F b ( 0 ) ∣ b ∈ { 0 , 1 } b\in\{0,1\} b ∈ { 0 , 1 } 3.8 3.8 3.8 G = { w ∈ S m : ∑ i w i ≤ 3 N / 4 } \mathcal{G}=\{\mathbf{w}\in\mathcal{S}^m:\sum_i w_i\leq3N/4\} G = { w ∈ S m : ∑ i w i ≤ 3 N /4 } P w ( s ) = ∑ ℓ = 0 r − 1 d ℓ ( w ) ( s ℓ ) P_{\mathbf{w}}(s)=\sum_{\ell=0}^{r-1}d_\ell(\mathbf{w})\binom{s}{\ell} P w ( s ) = ∑ ℓ = 0 r − 1 d ℓ ( w ) ( ℓ s ) r − 1 r-1 r − 1 d ℓ ( w ) d_\ell(\mathbf{w}) d ℓ ( w ) ( 20 ) (20) ( 20 ) ∣ F b ( 1 ) − F b ( 0 ) ∣ |F_b(1)-F_b(0)| ∣ F b ( 1 ) − F b ( 0 ) ∣
m ∫ 0 1 E w ∼ π b , u ⊗ ( m − 1 ) [ ∣ 1 G ∑ s ∈ S π ˙ b , u ( s ) ( q w ( s ) − P w ( s ) ) ∣ ] d u + m ∫ 0 1 ∥ π ˙ b , u ∥ 1 Pr w ∼ π b , u ⊗ ( m − 1 ) [ w ∉ G ] d u . (21) m\int_0^1\mathbb{E}_{\mathbf{w}\sim\pi_{b,u}^{\otimes(m-1)}}\left[\left|\mathbf{1}_{\mathcal{G}}\sum_{s\in\mathcal{S}}\dot{\pi}_{b,u}(s)(q_{\mathbf{w}}(s)-P_{\mathbf{w}}(s))\right|\right]\,du+m\int_0^1\|\dot{\pi}_{b,u}\|_1\Pr_{\mathbf{w}\sim\pi_{b,u}^{\otimes(m-1)}}[\mathbf{w}\notin\mathcal{G}]\,du. \tag*{(21)} m ∫ 0 1 E w ∼ π b , u ⊗ ( m − 1 ) [ 1 G s ∈ S ∑ π ˙ b , u ( s ) ( q w ( s ) − P w ( s )) ] d u + m ∫ 0 1 ∥ π ˙ b , u ∥ 1 w ∼ π b , u ⊗ ( m − 1 ) Pr [ w ∈ / G ] d u . (21) We now restrict our attention to bounding the two terms in the above equation.
We apply the Newton expansion in Lemma 3.3 3.3 3.3
∣ ∑ s ∈ S π ˙ b , u ( s ) ( q w ( s ) − P w ( s ) ) ∣ ≤ δ ∑ ℓ = r A ( A ℓ ) ∣ d ℓ ( w ) ∣ . \left|\sum_{s\in\mathcal{S}}\dot{\pi}_{b,u}(s)(q_{\mathbf{w}}(s)-P_{\mathbf{w}}(s))\right|\leq\delta\sum_{\ell=r}^{A}\binom{A}{\ell}|d_\ell(\mathbf{w})|. s ∈ S ∑ π ˙ b , u ( s ) ( q w ( s ) − P w ( s )) ≤ δ ℓ = r ∑ A ( ℓ A ) ∣ d ℓ ( w ) ∣. For u > 0 u>0 u > 0 4.1 4.1 4.1 π b , u \pi_{b,u} π b , u a = u κ δ a=u\kappa\delta a = u κ δ E [ 1 G ∣ d ℓ ( w ) ∣ ] ≤ C ℓ T 1 + α ℓ N ( m u κ δ ) − α ℓ \mathbb{E}[\mathbf{1}_{\mathcal{G}}|d_\ell(\mathbf{w})|]\leq\frac{C^\ell T^{1+\alpha_\ell}}{N}(mu\kappa\delta)^{-\alpha_\ell} E [ 1 G ∣ d ℓ ( w ) ∣ ] ≤ N C ℓ T 1 + α ℓ ( m u κ δ ) − α ℓ
E w ∼ π b , u ⊗ ( m − 1 ) [ ∣ 1 G ∑ s ∈ S π ˙ b , u ( s ) ( q w ( s ) − P w ( s ) ) ∣ ] ≤ δ ∑ ℓ = r A ( A ℓ ) C ℓ T 1 + α ℓ N ( m u κ δ ) − α ℓ . \mathbb{E}_{\mathbf{w}\sim\pi_{b,u}^{\otimes(m-1)}}\left[\left|\mathbf{1}_{\mathcal{G}}\sum_{s\in\mathcal{S}}\dot{\pi}_{b,u}(s)(q_{\mathbf{w}}(s)-P_{\mathbf{w}}(s))\right|\right]\leq\delta\sum_{\ell=r}^{A}\binom{A}{\ell}\frac{C^\ell T^{1+\alpha_\ell}}{N}(mu\kappa\delta)^{-\alpha_\ell}. E w ∼ π b , u ⊗ ( m − 1 ) [ 1 G s ∈ S ∑ π ˙ b , u ( s ) ( q w ( s ) − P w ( s )) ] ≤ δ ℓ = r ∑ A ( ℓ A ) N C ℓ T 1 + α ℓ ( m u κ δ ) − α ℓ . We absorb ( A ℓ ) κ − α ℓ \binom{A}{\ell}\kappa^{-\alpha_\ell} ( ℓ A ) κ − α ℓ C A C^A C A ( 21 ) (21) ( 21 )
C A N ∑ ℓ = r A T 1 + α ℓ δ 1 − α ℓ m α ℓ u − α ℓ . \frac{C^A}{N}\sum_{\ell=r}^{A}\frac{T^{1+\alpha_\ell}\delta^{1-\alpha_\ell}}{m^{\alpha_\ell}}u^{-\alpha_\ell}. N C A ℓ = r ∑ A m α ℓ T 1 + α ℓ δ 1 − α ℓ u − α ℓ . The exceptional-event probability (i.e. the probability of w ∉ G \mathbf{w}\notin\mathcal{G} w ∈ / G e − N / ( 4 A 2 ) e^{-N/(4A^2)} e − N / ( 4 A 2 ) α ℓ < 1 \alpha_\ell<1 α ℓ < 1 ( 21 ) (21) ( 21 )
∣ Pr f ∼ Π 1 , N [ A f = 1 ] − Pr f ∼ Π 0 , N [ A f = 1 ] ∣ ≤ ∑ b = 0 1 ∣ F b ( 1 ) − F b ( 0 ) ∣ ≤ C A m N ∑ ℓ = r A T 1 + α ℓ δ 1 − α ℓ m α ℓ ( 1 − α ℓ ) + 2 m δ e − N / ( 4 A 2 ) . \left|\Pr_{f\sim\Pi_{1,N}}[\mathcal{A}^f=1]-\Pr_{f\sim\Pi_{0,N}}[\mathcal{A}^f=1]\right|\leq\sum_{b=0}^{1}|F_b(1)-F_b(0)|\leq\frac{C^A m}{N}\sum_{\ell=r}^{A}\frac{T^{1+\alpha_\ell}\delta^{1-\alpha_\ell}}{m^{\alpha_\ell}(1-\alpha_\ell)}+2m\delta e^{-N/(4A^2)}. f ∼ Π 1 , N Pr [ A f = 1 ] − f ∼ Π 0 , N Pr [ A f = 1 ] ≤ b = 0 ∑ 1 ∣ F b ( 1 ) − F b ( 0 ) ∣ ≤ N C A m ℓ = r ∑ A m α ℓ ( 1 − α ℓ ) T 1 + α ℓ δ 1 − α ℓ + 2 m δ e − N / ( 4 A 2 ) . Consider δ ≤ 2 \delta\leq2 δ ≤ 2 N / 3 ≤ m ≤ N / 2 N/3\leq m\leq N/2 N /3 ≤ m ≤ N /2 ( 1 − α ℓ ) − 1 = 2 ℓ − 1 (1-\alpha_\ell)^{-1}=2^{\ell-1} ( 1 − α ℓ ) − 1 = 2 ℓ − 1 T ≤ N T\leq N T ≤ N α ℓ ≥ α r \alpha_\ell\geq\alpha_r α ℓ ≥ α r ℓ ≥ r \ell\geq r ℓ ≥ r T 1 + α ℓ N α ℓ ≤ T 1 + α r N α r \frac{T^{1+\alpha_\ell}}{N^{\alpha_\ell}}\leq\frac{T^{1+\alpha_r}}{N^{\alpha_r}} N α ℓ T 1 + α ℓ ≤ N α r T 1 + α r C A C^A C A
∣ Pr f ∼ Π 1 , N [ A f = 1 ] − Pr f ∼ Π 0 , N [ A f = 1 ] ∣ ≤ C A T 1 + α r N α r + 2 N e − N / ( 4 A 2 ) . \left|\Pr_{f\sim\Pi_{1,N}}[\mathcal{A}^f=1]-\Pr_{f\sim\Pi_{0,N}}[\mathcal{A}^f=1]\right|\leq C^A\frac{T^{1+\alpha_r}}{N^{\alpha_r}}+2Ne^{-N/(4A^2)}. f ∼ Π 1 , N Pr [ A f = 1 ] − f ∼ Π 0 , N Pr [ A f = 1 ] ≤ C A N α r T 1 + α r + 2 N e − N / ( 4 A 2 ) . The left-hand side is at most one, so we may replace 2 N e − N / ( 4 A 2 ) 2Ne^{-N/(4A^2)} 2 N e − N / ( 4 A 2 ) N e − N / ( 8 A 2 ) Ne^{-N/(8A^2)} N e − N / ( 8 A 2 ) N ≥ 2 N\geq2 N ≥ 2 □ \square □
Proof of Lemma 4.1
Recall that we have fixed a T T T A \mathcal{A} A f : [ N ] → [ N ] f : [N] \to[N] f : [ N ] → [ N ] p ( f ) = Pr [ A f = 1 ] p(f) = \Pr[\mathcal{A}^{f} = 1] p ( f ) = Pr [ A f = 1 ]
We prove the upper bound on the expectation of the Newton coefficients in Lemma 4.1 by first bounding each Newton coefficient d ℓ ( w ) d_{\ell}(\mathbf{w}) d ℓ ( w ) w \mathbf{w} w w ∈ { 0 , 1 } m − 1 \mathbf{w} \in\{0,1\}^{m-1} w ∈ { 0 , 1 } m − 1 singleton case . We treat the singleton case separately in Lemma 4.8 . For the other cases, we first introduce some new notation.
Newton coefficients as block differences
Assume N ≥ 8 A N \ge8A N ≥ 8 A 2 ≤ ℓ ≤ A 2 \le\ell\le A 2 ≤ ℓ ≤ A w ∈ S m − 1 \mathbf{w} \in S^{m-1} w ∈ S m − 1 ∑ i w i ≤ 3 N / 4 \sum_i w_i \le3N/4 ∑ i w i ≤ 3 N /4 w i ≥ 2 w_i \ge2 w i ≥ 2 c = c ( w , ℓ ) \mathbf{c} = \mathbf{c}(\mathbf{w},\ell) c = c ( w , ℓ ) f f f ( f ( 1 ) , … , f ( N ) ) ∈ [ N ] N (f(1),\ldots,f(N)) \in[N]^N ( f ( 1 ) , … , f ( N )) ∈ [ N ] N f f f [ N ] [N] [ N ] blocks , their sizes correspond to the non-zero frequency entries.
For 0 ≤ s ≤ ℓ 0 \le s \le\ell 0 ≤ s ≤ ℓ f f f q w ( s ) q_{\mathbf{w}}(s) q w ( s ) q w ( ℓ ) q_{\mathbf{w}}(\ell) q w ( ℓ ) ℓ \ell ℓ s s s ℓ − s \ell-s ℓ − s s = 0 s=0 s = 0
Let ρ = ∣ { a ∈ [ N ] : c a = ℓ } ∣ \rho= |\{a \in[N] : c_a = \ell\}| ρ = ∣ { a ∈ [ N ] : c a = ℓ } ∣ ℓ \ell ℓ d = ∣ { a ∈ [ N ] : c a > 0 } ∣ d = |\{a \in[N] : c_a > 0\}| d = ∣ { a ∈ [ N ] : c a > 0 } ∣ ∑ i w i + ℓ ≤ 7 N / 8 \sum_i w_i+\ell\le7N/8 ∑ i w i + ℓ ≤ 7 N /8 ρ ≥ 1 \rho\ge1 ρ ≥ 1 d + ℓ ≤ N d+\ell\le N d + ℓ ≤ N
For 1 ≤ j ≤ ℓ 1 \le j \le\ell 1 ≤ j ≤ ℓ c \mathbf{c} c ν j \nu_j ν j f f f j j j B B B a \mathbf{a} a ν j \nu_j ν j [ N ] [N] [ N ] c \mathbf{c} c ℓ \ell ℓ j j j B B B ℓ − j \ell-j ℓ − j [ N ] [N] [ N ] f : [ N ] → [ N ] f : [N] \to[N] f : [ N ] → [ N ] d + ℓ − j ≤ N − j d+\ell-j \le N-j d + ℓ − j ≤ N − j j j j j j j a = ( a i ) i ∈ B \mathbf{a} = (a_i)_{i\in B} a = ( a i ) i ∈ B E ν j \mathbb{E}_{\nu_j} E ν j
For U ⊆ B U \subseteq B U ⊆ B f U , a f^{U,\mathbf{a}} f U , a
f U , a ( i ) = { a i , i ∈ U , f ( i ) , i ∉ U . f^{U,\mathbf{a}}(i) =
\begin{cases}
a_i, & i \in U,\\
f(i), & i \notin U.
\end{cases} f U , a ( i ) = { a i , f ( i ) , i ∈ U , i ∈ / U . The same tuple a \mathbf{a} a U ⊆ B U \subseteq B U ⊆ B f U , a f^{U,\mathbf{a}} f U , a j ≥ 2 j \ge2 j ≥ 2 ( f , B , a ) ∼ ν j (f,B,\mathbf{a}) \sim\nu_j ( f , B , a ) ∼ ν j i i i B B B ( f { i } , a , B ∖ { i } , ( a k ) k ∈ B ∖ { i } ) ∼ ν j − 1 (f^{\{i\},\mathbf{a}}, B \setminus\{i\}, (a_k)_{k\in B\setminus\{i\}}) \sim\nu_{j-1} ( f { i } , a , B ∖ { i } , ( a k ) k ∈ B ∖ { i } ) ∼ ν j − 1 Proposition 4.4 . Together with the original triple ( f , B , a ) (f,B,\mathbf{a}) ( f , B , a ) ν j \nu_j ν j ν j − 1 \nu_{j-1} ν j − 1
The marginal distribution of f f f ν j \nu_j ν j D c ( w , j ) \mathcal{D}_{\mathbf{c}(\mathbf{w},j)} D c ( w , j ) D c \mathcal{D}_{\mathbf{c}} D c j = ℓ j=\ell j = ℓ
E ν j [ p ( f ) ] = q w ( j ) . \mathbb{E}_{\nu_j}[p(f)] = q_{\mathbf{w}}(j). E ν j [ p ( f )] = q w ( j ) . For any scalar- or vector-valued function g g g f : [ N ] → [ N ] f : [N] \to[N] f : [ N ] → [ N ] block difference operator by
D B a g ( f ) = ∑ U ⊆ B ( − 1 ) ∣ U ∣ g ( f U , a ) . D_{B}^{\mathbf{a}}g(f) = \sum_{U \subseteq B} (-1)^{|U|} g(f^{U,\mathbf{a}}). D B a g ( f ) = U ⊆ B ∑ ( − 1 ) ∣ U ∣ g ( f U , a ) . We henceforth suppress a \mathbf{a} a
The next lemma identifies d ℓ ( w ) d_{\ell}(\mathbf{w}) d ℓ ( w ) q w q_{\mathbf{w}} q w E ν ℓ [ ( D B p ) ( f ) ] \mathbb{E}_{\nu_{\ell} }[(D_{B}p)(f)] E ν ℓ [( D B p ) ( f )]
Proposition 4.3. For every ℓ \ell ℓ w \mathbf{w} w
E ν ℓ [ ( D B p ) ( f ) ] = d ℓ ( w ) . (22) \mathbb{E}_{\nu_\ell}[(D_{B p})(f)] = d_\ell(\mathbf{w}). \tag*{(22)} E ν ℓ [( D B p ) ( f )] = d ℓ ( w ) . (22) Proof. In the definition of D B D_B D B f U f^U f U U ⊆ B U \subseteq B U ⊆ B ( ℓ − ∣ U ∣ ) (\ell-|U|) ( ℓ − ∣ U ∣ ) ∣ U ∣ |U| ∣ U ∣ B B B U = B U=B U = B ℓ \ell ℓ ν ℓ \nu_\ell ν ℓ U ⊆ B U \subseteq B U ⊆ B ( ℓ ∣ U ∣ ) \binom{\ell}{|U|} ( ∣ U ∣ ℓ ) ∣ U ∣ |U| ∣ U ∣ Proposition 4.4 . So the resulting mean acceptance is q w ( ℓ − ∣ U ∣ ) q_{\mathbf{w}}(\ell-|U|) q w ( ℓ − ∣ U ∣ ) s = ℓ − ∣ U ∣ s=\ell-|U| s = ℓ − ∣ U ∣
E ν ℓ [ ( D B p ) ( f ) ] = ∑ s = 0 ℓ ( − 1 ) ℓ − s ( ℓ s ) q w ( s ) = d ℓ ( w ) . \mathbb{E}_{\nu_\ell}[(D_{B p})(f)] = \sum_{s=0}^{\ell}(-1)^{\ell-s}\binom{\ell}{s}q_{\mathbf{w}}(s)=d_\ell(\mathbf{w}). E ν ℓ [( D B p ) ( f )] = s = 0 ∑ ℓ ( − 1 ) ℓ − s ( s ℓ ) q w ( s ) = d ℓ ( w ) . Thus, for proving Lemma 4.1 , it suffices to bound the average block difference of the acceptance probability.
Bounding the block differences
Consider a feasible frequency vector c \mathbf{c} c ρ ≥ 1 \rho\ge1 ρ ≥ 1 d + ℓ ≤ N d+\ell\le N d + ℓ ≤ N b j = ∣ { a ∈ [ N ] : c a = j } ∣ b_j=|\{a\in[N]:c_a=j\}| b j = ∣ { a ∈ [ N ] : c a = j } ∣ j j j 1 ≤ j < ℓ 1\le j<\ell 1 ≤ j < ℓ n j = 1 + b j n_j=1+b_j n j = 1 + b j 1 ≤ j < ℓ 1\le j<\ell 1 ≤ j < ℓ n ∗ = min 1 ≤ j < ℓ n j n_*=\min_{1\le j<\ell}n_j n ∗ = min 1 ≤ j < ℓ n j
The following identity of the block difference operator is going to be useful in our proofs. For J ⊆ B J\subseteq B J ⊆ B D J D_J D J a i a_i a i i ∈ J i\in J i ∈ J f { i } f^{\{i\}} f { i } i ∈ B ∖ J i\in B\setminus J i ∈ B ∖ J
Proposition 4.4. Let 1 ≤ j ≤ ℓ 1\le j\le\ell 1 ≤ j ≤ ℓ ( f , B , a ) ∼ ν j (f,B,\mathbf{a})\sim\nu_j ( f , B , a ) ∼ ν j U ⊆ B U\subseteq B U ⊆ B f U f^U f U U U U g g g i ∈ B i\in B i ∈ B ( f , B , a ) (f,B,\mathbf{a}) ( f , B , a ) a \mathbf{a} a
D B g ( f ) = D B ∖ { i } g ( f ) − D B ∖ { i } g ( f { i } ) . (23) D_Bg(f)=D_{B\setminus\{i\}}g(f)-D_{B\setminus\{i\}}g(f^{\{i\}}). \tag*{(23)} D B g ( f ) = D B ∖ { i } g ( f ) − D B ∖ { i } g ( f { i } ) . (23) Proof. Conditional on the partition and B B B U ⊆ B U\subseteq B U ⊆ B f U f^U f U
For the identity, let us fix a sampled triple ( f , B , a ) (f,B,\mathbf{a}) ( f , B , a ) i ∈ B i\in B i ∈ B i i i
D B g ( f ) = ∑ U ⊆ B ∖ { i } ( − 1 ) ∣ U ∣ ( g ( f U ) − g ( f U ∪ { i } ) ) D_Bg(f)=\sum_{U\subseteq B\setminus\{i\}}(-1)^{|U|}\left(g(f^U)-g(f^{U\cup\{i\}})\right) D B g ( f ) = U ⊆ B ∖ { i } ∑ ( − 1 ) ∣ U ∣ ( g ( f U ) − g ( f U ∪ { i } ) ) = D B ∖ { i } g ( f ) − D B ∖ { i } g ( f { i } ) . =D_{B\setminus\{i\}}g(f)-D_{B\setminus\{i\}}g(f^{\{i\}}). = D B ∖ { i } g ( f ) − D B ∖ { i } g ( f { i } ) . The last equality uses ( f { i } ) U = f U ∪ { i } (f^{\{i\}})^U=f^{U\cup\{i\}} ( f { i } ) U = f U ∪ { i } a \mathbf{a} a
In the proof of the next lemma, the main fact used is that, conditional on f f f B B B j j j j j j j − 1 j-1 j − 1 j j j j − 1 j-1 j − 1 ∣ G ( f ) ⟩ |G(f)\rangle ∣ G ( f )⟩ f f f f f f
Lemma 4.5. Let ∣ G ( f ) ⟩ = ∑ i ∣ i ⟩ ⊗ ∣ G i ( f ) ⟩ |G(f)\rangle= \sum_i |i\rangle\otimes|G_i(f)\rangle ∣ G ( f )⟩ = ∑ i ∣ i ⟩ ⊗ ∣ G i ( f )⟩
E ν j [ ∑ i ∈ B ∥ D B ∖ { i } ∣ G i ( f { i } ) ⟩ ∥ 2 2 ] ≤ j n 1 E ν j − 1 [ ∥ D B ∣ G ( f ) ⟩ ∥ 2 2 ] ( 2 ≤ j ≤ ℓ ) . (24) \mathbb{E}_{\nu_j}\left[\sum_{i\in B}\left\|D_{B\setminus\{i\}}|G_i(f^{\{i\}})\rangle\right\|_2^2\right]\leq\frac{j}{n_1}\mathbb{E}_{\nu_{j-1}}\left[\left\|D_B|G(f)\rangle\right\|_2^2\right]
\qquad(2\leq j\leq\ell). \tag*{(24)} E ν j [ i ∈ B ∑ D B ∖ { i } ∣ G i ( f { i } )⟩ 2 2 ] ≤ n 1 j E ν j − 1 [ ∥ D B ∣ G ( f )⟩ ∥ 2 2 ] ( 2 ≤ j ≤ ℓ ) . (24) Moreover, if ∥ ∣ G ( f ) ⟩ ∥ 2 = 1 \left\||G(f)\rangle\right\|_2=1 ∥ ∣ G ( f )⟩ ∥ 2 = 1 f f f
E ν j [ ∑ i ∈ B ∥ D B ∖ { i } ∣ G i ( f ) ⟩ ∥ 2 2 ] ≤ 4 j n ∗ ( 2 ≤ j < ℓ ) . (25) \mathbb{E}_{\nu_j}\left[\sum_{i\in B}\left\|D_{B\setminus\{i\}}|G_i(f)\rangle\right\|_2^2\right]\leq\frac{4^j}{n_*}
\qquad(2\leq j<\ell). \tag*{(25)} E ν j [ i ∈ B ∑ D B ∖ { i } ∣ G i ( f )⟩ 2 2 ] ≤ n ∗ 4 j ( 2 ≤ j < ℓ ) . (25) Proof. We provide the proofs of the two statements separately.
Proof of the first statement. Choose i i i B B B f ( i ) f(i) f ( i ) a i a_i a i f { i } f^{\{i\}} f { i } B ∖ { i } B\setminus\{i\} B ∖ { i } a \mathbf{a} a ( j − 1 ) (j-1) ( j − 1 ) i i i s j = b 1 + ℓ − j + 1 ≥ n 1 s_j=b_1+\ell-j+1\geq n_1 s j = b 1 + ℓ − j + 1 ≥ n 1 a i a_i a i S \mathcal{S} S
E ν j [ ∑ i ∈ B ∥ D B ∖ { i } ∣ G i ( f { i } ) ⟩ ∥ 2 2 ] = j s j E ν j − 1 [ ∑ i ∈ S ∥ D B ∣ G i ( f ) ⟩ ∥ 2 2 ] ≤ j n 1 E ν j − 1 [ ∥ D B ∣ G ( f ) ⟩ ∥ 2 2 ] . \mathbb{E}_{\nu_j}\left[\sum_{i\in B}\left\|D_{B\setminus\{i\}}|G_i(f^{\{i\}})\rangle\right\|_2^2\right]
=\frac{j}{s_j}\mathbb{E}_{\nu_{j-1}}\left[\sum_{i\in\mathcal{S}}\left\|D_B|G_i(f)\rangle\right\|_2^2\right]
\leq\frac{j}{n_1}\mathbb{E}_{\nu_{j-1}}\left[\left\|D_B|G(f)\rangle\right\|_2^2\right]. E ν j [ i ∈ B ∑ D B ∖ { i } ∣ G i ( f { i } )⟩ 2 2 ] = s j j E ν j − 1 [ i ∈ S ∑ ∥ D B ∣ G i ( f )⟩ ∥ 2 2 ] ≤ n 1 j E ν j − 1 [ ∥ D B ∣ G ( f )⟩ ∥ 2 2 ] . Proof of the second statement. Note that D B ∖ { i } ∣ G i ( f ) ⟩ D_{B\setminus\{i\}}|G_i(f)\rangle D B ∖ { i } ∣ G i ( f )⟩ 2 j − 1 2^{j-1} 2 j − 1 ∣ G i ( f V ) ⟩ |G_i(f^V)\rangle ∣ G i ( f V )⟩ V ⊆ B ∖ { i } V\subseteq B\setminus\{i\} V ⊆ B ∖ { i } i ∈ B i\in B i ∈ B
∑ i ∈ B ∥ D B ∖ { i } ∣ G i ( f ) ⟩ ∥ 2 2 ≤ 2 j − 1 ∑ U ⊆ B ∑ i ∈ B ∖ U ∥ G i ( f U ) ∥ 2 2 . \sum_{i\in B}\left\|D_{B\setminus\{i\}}|G_i(f)\rangle\right\|_2^2
\leq2^{j-1}\sum_{U\subseteq B}\sum_{i\in B\setminus U}\left\|G_i(f^U)\right\|_2^2. i ∈ B ∑ D B ∖ { i } ∣ G i ( f )⟩ 2 2 ≤ 2 j − 1 U ⊆ B ∑ i ∈ B ∖ U ∑ G i ( f U ) 2 2 . Now let us group the terms by s = ∣ B ∖ U ∣ s=|B\setminus U| s = ∣ B ∖ U ∣ f U f^U f U B ∖ U B\setminus U B ∖ U s s s 1 / n ∗ 1/n_* 1/ n ∗ n s ≥ n ∗ n_s\geq n_* n s ≥ n ∗ s s s 2 j − 1 ∑ s ∈ [ j ] ( j s ) / n ∗ = 2 j − 1 ( 2 j − 1 ) / n ∗ ≤ 4 j / n ∗ 2^{j-1}\sum_{s\in[j]}\binom{j}{s}/n_*=2^{j-1}(2^j-1)/n_*\leq4^j/n_* 2 j − 1 ∑ s ∈ [ j ] ( s j ) / n ∗ = 2 j − 1 ( 2 j − 1 ) / n ∗ ≤ 4 j / n ∗ (25) . □
Now we turn to the main lemma of this part, that upper bounds the expected block difference of the acceptance probability. Our argument is an elementary form of the more involved query-gain argument in [9 ] .
Lemma 4.6. Under the preceding assumptions, the acceptance probability p ( f ) p(f) p ( f ) T T T f : [ N ] → [ N ] f : [N] \to[N] f : [ N ] → [ N ]
∣ E ν ℓ [ ( D B p ) ( f ) ] ∣ ≤ C ℓ T 1 + α ℓ ρ n 1 n ∗ α ℓ − 1 / 2 , (26) \left|\mathbb{E}_{\nu_\ell}[(D_Bp)(f)]\right| \leq\frac{C^\ell T^{1+\alpha_\ell}}{\sqrt{\rho}\,n_1 n_*^{\alpha_\ell-1/2}}, \tag*{(26)} ∣ E ν ℓ [( D B p ) ( f )] ∣ ≤ ρ n 1 n ∗ α ℓ − 1/2 C ℓ T 1 + α ℓ , (26) where C C C
Proof. By deferring measurements and uncomputing, we are going to make the accepting amplitude linear in the final state, which costs a factor 2 in queries. Let A f A_f A f f f f ∣ 0 ⟩ |0\rangle ∣0 ⟩ P a c c P_{\mathrm{acc}} P acc V f = A f † ( I − 2 P a c c ) A f V_f = A_f^\dagger(I-2P_{\mathrm{acc}})A_f V f = A f † ( I − 2 P acc ) A f P a c c P_{\mathrm{acc}} P acc V f V_f V f
g ( f ) : = ⟨ 0 ∣ V f ∣ 0 ⟩ = 1 − 2 p ( f ) . g(f) := \langle0|V_f|0\rangle= 1-2p(f). g ( f ) := ⟨ 0∣ V f ∣0 ⟩ = 1 − 2 p ( f ) . Since V f V_f V f A f A_f A f A f † A_f^\dagger A f † 2 T 2T 2 T f f f T T T O f : ∣ i , y ⟩ ↦ ∣ i , y + f ( i ) m o d N ⟩ O_f : |i,y\rangle\mapsto|i,y+f(i)\bmod N\rangle O f : ∣ i , y ⟩ ↦ ∣ i , y + f ( i ) mod N ⟩ Neg ∣ y ⟩ = ∣ − y m o d N ⟩ \operatorname{Neg}|y\rangle=|-y\bmod N\rangle Neg ∣ y ⟩ = ∣ − y mod N ⟩ Neg O f Neg ∣ i , y ⟩ = ∣ i , y − f ( i ) m o d N ⟩ = O f † ∣ i , y ⟩ \operatorname{Neg}O_f\operatorname{Neg}|i,y\rangle=|i,y-f(i)\bmod N\rangle=O_f^\dagger|i,y\rangle Neg O f Neg ∣ i , y ⟩ = ∣ i , y − f ( i ) mod N ⟩ = O f † ∣ i , y ⟩
So we consider T ′ = 2 T T'=2T T ′ = 2 T V f V_f V f D B 1 = 0 D_B1=0 D B 1 = 0 D B p = − 1 2 D B g D_Bp=-\frac{1}{2}D_Bg D B p = − 2 1 D B g ∣ E ν ℓ [ D B g ( f ) ] ∣ \left|\mathbb{E}_{\nu_\ell}[D_Bg(f)]\right| ∣ E ν ℓ [ D B g ( f )] ∣ T ′ T' T ′ V f = W T ′ O f W T ′ − 1 ⋯ W 1 O f W 0 V_f=W_{T'}O_fW_{T'-1}\cdots W_1O_fW_0 V f = W T ′ O f W T ′ − 1 ⋯ W 1 O f W 0 W T ′ W_{T'} W T ′ ⟨ u ∣ = ⟨ 0 ∣ W T ′ \langle u|=\langle0|W_{T'} ⟨ u ∣ = ⟨ 0∣ W T ′
∥ ∣ G ⟩ ∥ ν j = ( E ν j [ ∥ ∣ G ⟩ ∥ 2 2 ] ) 1 / 2 . \lVert|G\rangle\rVert_{\nu_j}=\left(\mathbb{E}_{\nu_j}\left[\lVert|G\rangle\lVert_2^2\right]\right)^{1/2}. ∥ ∣ G ⟩ ∥ ν j = ( E ν j [ ∥ ∣ G ⟩ ∥ 2 2 ] ) 1/2 . When there is no ambiguity, we suppress the input f f f D B D_B D B B B B a \mathbf{a} a
Let ∣ ψ t ⟩ |\psi_t\rangle ∣ ψ t ⟩ ∣ ψ t ( f ) ⟩ |\psi_t(f)\rangle ∣ ψ t ( f )⟩ t t t ∣ ψ t ′ ⟩ |\psi'_t\rangle ∣ ψ t ′ ⟩ t + 1 t+1 t + 1 ∣ ψ t + 1 ⟩ = O f ∣ ψ t ′ ⟩ |\psi_{t+1}\rangle=O_f|\psi'_t\rangle ∣ ψ t + 1 ⟩ = O f ∣ ψ t ′ ⟩ 1 ≤ j < ℓ 1\leq j<\ell 1 ≤ j < ℓ
R j = max 0 ≤ t ≤ T ′ ∥ D B ∣ ψ t ⟩ ∥ ν j . R_j=\max_{0\leq t\leq T'}\lVert D_B|\psi_t\rangle\rVert_{\nu_j}. R j = 0 ≤ t ≤ T ′ max ∥ D B ∣ ψ t ⟩ ∥ ν j . Since input-independent unitaries W t W_t W t D B D_B D B ∥ D B ∣ ψ t ⟩ ∥ ν j = ∥ D B ∣ ψ t ′ ⟩ ∥ ν j \lVert D_B|\psi_t\rangle\rVert_{\nu_j}=\lVert D_B|\psi'_t\rangle\rVert_{\nu_j} ∥ D B ∣ ψ t ⟩ ∥ ν j = ∥ D B ∣ ψ t ′ ⟩ ∥ ν j D B D_B D B D B ∣ ψ 0 ⟩ = 0 D_B|\psi_0\rangle=0 D B ∣ ψ 0 ⟩ = 0 R j R_j R j
Claim 4.7. For every 1 ≤ j < ℓ 1\leq j<\ell 1 ≤ j < ℓ R j R_j R j
R j ≤ 4 j + 1 ( T ′ ) α j + 1 n 1 n ∗ α j + 1 − 1 / 2 . R_j\leq\frac{4^{j+1}(T')^{\alpha_j+1}}{\sqrt{n_1}\,n_*^{\alpha_j+1-1/2}}. R j ≤ n 1 n ∗ α j + 1 − 1/2 4 j + 1 ( T ′ ) α j + 1 . It remains to bound the expected block difference at size ℓ \ell ℓ ℓ − 1 \ell-1 ℓ − 1 T ′ T' T ′ ℓ \ell ℓ
∣ E ν ℓ [ ( D B g ) ( f ) ] ∣ ≤ 2 T ′ ρ ℓ n 1 R ℓ − 1 . \left|\mathbb{E}_{\nu_\ell}[(D_Bg)(f)]\right|\leq\frac{2T'}{\sqrt{\rho}}\sqrt{\frac{\ell}{n_1}}\,R_{\ell-1}. ∣ E ν ℓ [( D B g ) ( f )] ∣ ≤ ρ 2 T ′ n 1 ℓ R ℓ − 1 . { xref? } Claim 4.7 then gives the desired bound.
Contribution of one query. Let O i ( f ) O_i(f) O i ( f ) i i i O i ( f ) ∣ y ⟩ = ∣ y + f ( i ) m o d N ⟩ O_i(f)|y\rangle= |y + f(i) \bmod N\rangle O i ( f ) ∣ y ⟩ = ∣ y + f ( i ) mod N ⟩ O f = ∑ i ∣ i ⟩ ⟨ i ∣ ⊗ O i ( f ) O_f = \sum_i |i\rangle\langle i| \otimes O_i(f) O f = ∑ i ∣ i ⟩ ⟨ i ∣ ⊗ O i ( f ) ∣ ψ t ′ ( f ) ⟩ = ∑ i ∣ i ⟩ ⊗ ∣ ψ t , i ′ ( f ) ⟩ |\psi'_t(f)\rangle= \sum_i |i\rangle\otimes|\psi'_{t,i}(f)\rangle ∣ ψ t ′ ( f )⟩ = ∑ i ∣ i ⟩ ⊗ ∣ ψ t , i ′ ( f )⟩ Proposition 4.4 , the difference vector
∣ e B , t ⟩ = D B ∣ ψ t + 1 ⟩ − O f D B ∣ ψ t ′ ⟩ (27) |e_{B,t}\rangle= D_B|\psi_{t+1}\rangle- O_fD_B|\psi'_t\rangle \tag*{(27)} ∣ e B , t ⟩ = D B ∣ ψ t + 1 ⟩ − O f D B ∣ ψ t ′ ⟩ (27) has components
∣ e B , t , i ⟩ = { ( O i ( f ) − O i ( f { i } ) ) D B ∖ { i } ∣ ψ t , i ′ ( f { i } ) ⟩ , i ∈ B , 0 , i ∉ B . |e_{B,t,i}\rangle=
\begin{cases}
\left(O_i(f)-O_i(f^{\{i\}})\right)D_{B\setminus\{i\}}|\psi'_{t,i}(f^{\{i\}})\rangle, & i\in B,\\
0, & i\notin B.
\end{cases} ∣ e B , t , i ⟩ = { ( O i ( f ) − O i ( f { i } ) ) D B ∖ { i } ∣ ψ t , i ′ ( f { i } )⟩ , 0 , i ∈ B , i ∈ / B . Each vector ∣ e B , t , i ⟩ |e_{B,t,i}\rangle ∣ e B , t , i ⟩ ∣ e B , t ⟩ |e_{B,t}\rangle ∣ e B , t ⟩ ∣ i ⟩ |i\rangle ∣ i ⟩ ∣ e B , t , i ⟩ |e_{B,t,i}\rangle ∣ e B , t , i ⟩ (24) gives
∥ ∣ e B , t ⟩ ∥ ν ℓ 2 ≤ 4 E ν ℓ [ ∥ ∑ i ∈ B D B ∖ { i } ∣ ψ t , i ′ ( f { i } ) ⟩ ∥ 2 2 ] ≤ 4 j n 1 R j − 1 2 ( 2 ≤ j ≤ ℓ ) . (28) \begin{aligned}
\left\| |e_{B,t}\rangle\right\|_{\nu_\ell}^{2}
\leq4\mathbb{E}_{\nu_\ell}\left[\left\|\sum_{i\in B}D_{B\setminus\{i\}}|\psi'_{t,i}(f^{\{i\}})\rangle\right\|_2^2\right] \\
&\leq\frac{4j}{n_1}R_{j-1}^{2}\qquad(2\leq j\leq\ell). \tag*{(28)}
\end{aligned} ∥ ∣ e B , t ⟩ ∥ ν ℓ 2 ≤ 4 E ν ℓ i ∈ B ∑ D B ∖ { i } ∣ ψ t , i ′ ( f { i } )⟩ 2 2 ≤ n 1 4 j R j − 1 2 ( 2 ≤ j ≤ ℓ ) . (28) Summing over all queries. We now take j = ℓ j=\ell j = ℓ ( D B g ) ( f ) (D_Bg)(f) ( D B g ) ( f ) g g g ∣ u ⟩ |u\rangle ∣ u ⟩ B B B ρ \rho ρ ℓ \ell ℓ 1 / ρ 1/\sqrt{\rho} 1/ ρ
Let Q t ( f ) = O f W T ′ − 1 ⋯ O f W t + 1 Q_t(f)=O_fW_{T'-1}\cdots O_fW_{t+1} Q t ( f ) = O f W T ′ − 1 ⋯ O f W t + 1 t + 1 t+1 t + 1 Q T ′ − 1 = I Q_{T'-1}=I Q T ′ − 1 = I ∣ χ t ( f ) ⟩ = Q t ( f ) † ∣ u ⟩ |\chi_t(f)\rangle=Q_t(f)^\dagger|u\rangle ∣ χ t ( f )⟩ = Q t ( f ) † ∣ u ⟩ ∣ u ⟩ |u\rangle ∣ u ⟩ Q t ( f ) Q_t(f) Q t ( f ) (27) gives D B ∣ ψ T ′ ⟩ = ∑ t Q t ( f ) ∣ e B , t ⟩ D_B|\psi_{T'}\rangle=\sum_t Q_t(f)|e_{B,t}\rangle D B ∣ ψ T ′ ⟩ = ∑ t Q t ( f ) ∣ e B , t ⟩ g ( f ) = ⟨ 0 ∣ V f ∣ 0 ⟩ = ⟨ u ∣ ψ T ′ ⟩ g(f)=\langle0|V_f|0\rangle=\langle u|\psi_{T'}\rangle g ( f ) = ⟨ 0∣ V f ∣0 ⟩ = ⟨ u ∣ ψ T ′ ⟩
E ν ℓ [ ( D B g ) ( f ) ] = ∑ t = 0 T ′ − 1 E ν ℓ [ ⟨ χ t ∣ e B , t ⟩ ] . \mathbb{E}_{\nu_\ell}[(D_Bg)(f)]=\sum_{t=0}^{T'-1}\mathbb{E}_{\nu_\ell}[\langle\chi_t|e_{B,t}\rangle]. E ν ℓ [( D B g ) ( f )] = t = 0 ∑ T ′ − 1 E ν ℓ [⟨ χ t ∣ e B , t ⟩] . Since ∣ e B , t ⟩ |e_{B,t}\rangle ∣ e B , t ⟩ B B B ⟨ χ t ∣ e B , t ⟩ = ⟨ P B χ t ∣ e B , t ⟩ \langle\chi_t|e_{B,t}\rangle=\langle P_B\chi_t|e_{B,t}\rangle ⟨ χ t ∣ e B , t ⟩ = ⟨ P B χ t ∣ e B , t ⟩ P B P_B P B B B B f f f ∣ χ t ( f ) ⟩ |\chi_t(f)\rangle ∣ χ t ( f )⟩ B B B ρ \rho ρ ℓ \ell ℓ f f f ∥ P B ∣ χ t ⟩ ∥ ν ℓ 2 ≤ 1 / ρ \|P_B|\chi_t\rangle\|_{\nu_\ell}^2\leq1/\rho ∥ P B ∣ χ t ⟩ ∥ ν ℓ 2 ≤ 1/ ρ (28) and Claim 4.7 finishes the proof of the lemma:
∣ E ν ℓ [ D B g ( f ) ] ∣ ≤ ∑ t = 0 T ′ − 1 ∥ P B ∣ χ t ⟩ ∥ ν ℓ ∥ ∣ e B , t ⟩ ∥ ν ℓ ≤ 2 T ′ ρ ℓ n 1 R ℓ − 1 ≤ C ℓ ( T ′ ) 1 + α ℓ ρ n 1 n ∗ α ℓ − 1 / 2 . \left|\mathbb{E}_{\nu_\ell}[D_Bg(f)]\right|
\leq\sum_{t=0}^{T'-1}\|P_B|\chi_t\rangle\|_{\nu_\ell}\| |e_{B,t}\rangle\|_{\nu_\ell}
\leq\frac{2T'}{\sqrt{\rho}}\sqrt{\frac{\ell}{n_1}}R_{\ell-1}
\leq\frac{C^\ell(T')^{1+\alpha_\ell}}{\sqrt{\rho}n_1n_*^{\alpha_\ell-1/2}}. ∣ E ν ℓ [ D B g ( f )] ∣ ≤ t = 0 ∑ T ′ − 1 ∥ P B ∣ χ t ⟩ ∥ ν ℓ ∥∣ e B , t ⟩ ∥ ν ℓ ≤ ρ 2 T ′ n 1 ℓ R ℓ − 1 ≤ ρ n 1 n ∗ α ℓ − 1/2 C ℓ ( T ′ ) 1 + α ℓ . Using D B p = − 1 2 D B g D_Bp=-\frac{1}{2}D_Bg D B p = − 2 1 D B g T ′ = 2 T T'=2T T ′ = 2 T C C C □ \square □
Proof of Claim 4.7 . In the setting of the previous proof, for i ∈ B i\in B i ∈ B
∣ ξ i ⟩ = D B ∖ { i } ∣ ψ t , i ′ ( f ) ⟩ , ∣ ζ i ⟩ = D B ∖ { i } ∣ ψ t , i ′ ( f { i } ) ⟩ . |\xi_i\rangle=D_{B\setminus\{i\}}|\psi'_{t,i}(f)\rangle,\qquad
|\zeta_i\rangle=D_{B\setminus\{i\}}|\psi'_{t,i}(f^{\{i\}})\rangle. ∣ ξ i ⟩ = D B ∖ { i } ∣ ψ t , i ′ ( f )⟩ , ∣ ζ i ⟩ = D B ∖ { i } ∣ ψ t , i ′ ( f { i } )⟩ . Proposition 4.4 gives D B ∣ ψ t , i ′ ( f ) ⟩ = ∣ ξ i ⟩ − ∣ ζ i ⟩ D_B|\psi'_{t,i}(f)\rangle=|\xi_i\rangle-|\zeta_i\rangle D B ∣ ψ t , i ′ ( f )⟩ = ∣ ξ i ⟩ − ∣ ζ i ⟩ D B ∣ ψ t + 1 , i ( f ) ⟩ = D B O i ( f ) ∣ ψ t , i ′ ( f ) ⟩ = O i ( f ) ∣ ξ i ⟩ − O i ( f { i } ) ∣ ζ i ⟩ D_B|\psi_{t+1,i}(f)\rangle=D_BO_i(f)|\psi'_{t,i}(f)\rangle=O_i(f)|\xi_i\rangle-O_i(f^{\{i\}})|\zeta_i\rangle D B ∣ ψ t + 1 , i ( f )⟩ = D B O i ( f ) ∣ ψ t , i ′ ( f )⟩ = O i ( f ) ∣ ξ i ⟩ − O i ( f { i } ) ∣ ζ i ⟩ i i i f ( i ) f(i) f ( i ) a i a_i a i O i ( f ) ( ∣ ξ i ⟩ − ∣ ζ i ⟩ ) + ( O i ( f ) − O i ( f { i } ) ) ∣ ζ i ⟩ O_i(f)(|\xi_i\rangle-|\zeta_i\rangle)+(O_i(f)-O_i(f^{\{i\}}))|\zeta_i\rangle O i ( f ) ( ∣ ξ i ⟩ − ∣ ζ i ⟩) + ( O i ( f ) − O i ( f { i } )) ∣ ζ i ⟩ U , V U,V U , V ∣ ξ ⟩ , ∣ ζ ⟩ |\xi\rangle,|\zeta\rangle ∣ ξ ⟩ , ∣ ζ ⟩
∥ U ∣ ξ ⟩ − V ∣ ζ ⟩ ∥ 2 2 − ∥ ∣ ξ ⟩ − ∣ ζ ⟩ ∥ 2 2 = 2 Re ⟨ ξ ∣ ( I − U † V ) ∣ ζ ⟩ ≤ 4 ∥ ∣ ξ ⟩ ∥ 2 ∥ ∣ ζ ⟩ ∥ 2 . \lVert U|\xi\rangle-V|\zeta\rangle\rVert_{2}^{2}-\lVert|\xi\rangle-|\zeta\rangle\rVert_{2}^{2}=2\operatorname{Re}\langle\xi|(I-U^{\dagger}V)|\zeta\rangle\leq4\lVert|\xi\rangle\rVert_{2}\lVert|\zeta\rangle\rVert_{2}. ∥ U ∣ ξ ⟩ − V ∣ ζ ⟩ ∥ 2 2 − ∥ ∣ ξ ⟩ − ∣ ζ ⟩ ∥ 2 2 = 2 Re ⟨ ξ ∣ ( I − U † V ) ∣ ζ ⟩ ≤ 4 ∥ ∣ ξ ⟩ ∥ 2 ∥ ∣ ζ ⟩ ∥ 2 . Apply this to compare D B ∣ ψ t + 1 ⟩ D_B|\psi_{t+1}\rangle D B ∣ ψ t + 1 ⟩ D B ∣ ψ t ′ ⟩ D_B|\psi'_t\rangle D B ∣ ψ t ′ ⟩ ∣ ξ ⟩ = ∣ ξ i ⟩ |\xi\rangle=|\xi_i\rangle ∣ ξ ⟩ = ∣ ξ i ⟩ ∣ ζ ⟩ = ∣ ζ i ⟩ |\zeta\rangle=|\zeta_i\rangle ∣ ζ ⟩ = ∣ ζ i ⟩ U = O i ( f ) U=O_i(f) U = O i ( f ) V = O i ( f { i 0 } ) V=O_i(f^{\{i_0\}}) V = O i ( f { i 0 } ) i ∈ B i\in B i ∈ B B B B
∥ D B ∣ ψ t + 1 ⟩ ∥ ν j 2 − ∥ D B ∣ ψ t ′ ⟩ ∥ ν j 2 ≤ 4 ( E ν j [ ∑ i ∈ B ∥ ∣ ξ i ⟩ ∥ 2 2 ] ) 1 / 2 ( E ν j [ ∑ i ∈ B ∥ ∣ ζ i ⟩ ∥ 2 2 ] ) 1 / 2 . \lVert D_B|\psi_{t+1}\rangle\rVert_{\nu_j}^{2}-\lVert D_B|\psi'_t\rangle\rVert_{\nu_j}^{2}\leq4\left(\mathop{\mathbb{E}}_{\nu_j}\left[\sum_{i\in B}\lVert|\xi_i\rangle\rVert_{2}^{2}\right]\right)^{1/2}\left(\mathop{\mathbb{E}}_{\nu_j}\left[\sum_{i\in B}\lVert|\zeta_i\rangle\rVert_{2}^{2}\right]\right)^{1/2}. ∥ D B ∣ ψ t + 1 ⟩ ∥ ν j 2 − ∥ D B ∣ ψ t ′ ⟩ ∥ ν j 2 ≤ 4 ( E ν j [ i ∈ B ∑ ∥ ∣ ξ i ⟩ ∥ 2 2 ] ) 1/2 ( E ν j [ i ∈ B ∑ ∥ ∣ ζ i ⟩ ∥ 2 2 ] ) 1/2 . We prove the claim by induction on j j j Lemma 4.5 . Summing the increments up to any query time and then taking the maximum gives a bound on R j 2 R_j^2 R j 2
For j = 1 j=1 j = 1 ∣ ψ t ′ ⟩ |\psi'_t\rangle ∣ ψ t ′ ⟩ i 0 i_0 i 0 B = { i 0 } B=\{i_0\} B = { i 0 } f f f b 1 + ℓ b_1+\ell b 1 + ℓ 1 / ( b 1 + ℓ ) 1/(b_1+\ell) 1/ ( b 1 + ℓ ) f { i 0 } f^{\{i_0\}} f { i 0 } 1 / ( b 1 + ℓ ) 1/(b_1+\ell) 1/ ( b 1 + ℓ ) 4 / ( b 1 + ℓ ) ≤ 4 / n 1 4/(b_1+\ell)\leq4/n_1 4/ ( b 1 + ℓ ) ≤ 4/ n 1 D B ∣ ψ 0 ⟩ = 0 D_B|\psi_0\rangle=0 D B ∣ ψ 0 ⟩ = 0 T ′ T' T ′ R 1 2 ≤ 4 T ′ / n 1 R_1^2\leq4T'/n_1 R 1 2 ≤ 4 T ′ / n 1
For 2 ≤ j < ℓ 2\leq j<\ell 2 ≤ j < ℓ (25) to the first expectation to obtain upper bound 4 j / n ∗ 4^j/n_* 4 j / n ∗ (24) to the second expectation gives upper bound j n 1 R j − 1 2 \frac{j}{n_1}R_{j-1}^2 n 1 j R j − 1 2 4 2 j n ∗ n 1 R j − 1 \frac{4\sqrt{2^j}}{\sqrt{n_*}\sqrt{n_1}}R_{j-1} n ∗ n 1 4 2 j R j − 1 T ′ T' T ′
R j 2 ≤ 4 4 j 2 j T ′ n 1 n ∗ R j − 1 ( 2 ≤ j < ℓ ) . R_j^2\leq\frac{4\sqrt{4^j2^jT'}}{\sqrt{n_1n_*}}R_{j-1}\qquad(2\leq j<\ell). R j 2 ≤ n 1 n ∗ 4 4 j 2 j T ′ R j − 1 ( 2 ≤ j < ℓ ) . Use the induction hypothesis together with α 2 = 1 / 2 \alpha_2=1/2 α 2 = 1/2 α j + 1 = ( 1 + α j ) / 2 \alpha_{j+1}=(1+\alpha_j)/2 α j + 1 = ( 1 + α j ) /2 j 2 j ≤ 4 j + 1 \sqrt{j}\,2^j\leq4^{j+1} j 2 j ≤ 4 j + 1
R j ≤ 4 j + 1 ( T ′ ) α j + 1 n 1 n ∗ α j + 1 − 1 / 2 . R_j\leq\frac{4^{j+1}(T')^{\alpha_{j+1}}}{\sqrt{n_1}\,n_*^{\alpha_{j+1}-1/2}}. R j ≤ n 1 n ∗ α j + 1 − 1/2 4 j + 1 ( T ′ ) α j + 1 . Newton coefficient bounds
Now we return to Newton coefficients, the original goal of Lemma 4.1 . As mentioned earlier, we first consider the singleton case, i.e., w ∈ { 0 , 1 } m − 1 \mathbf{w}\in\{0,1\}^{m-1} w ∈ { 0 , 1 } m − 1
Lemma 4.8. Suppose N ≥ 8 A N\geq8A N ≥ 8 A T ≥ 1 T\geq1 T ≥ 1 T 2 ≤ N / 8 T^2\leq N/8 T 2 ≤ N /8 2 ≤ ℓ ≤ A 2\leq\ell\leq A 2 ≤ ℓ ≤ A T ≤ N α ℓ / ( 1 + α ℓ ) T\leq N^{\alpha_\ell/(1+\alpha_\ell)} T ≤ N α ℓ / ( 1 + α ℓ ) w ∈ { 0 , 1 } m − 1 \mathbf{w}\in\{0,1\}^{m-1} w ∈ { 0 , 1 } m − 1
∣ d ℓ ( w ) ∣ ≤ C ℓ T 1 + α ℓ N , |d_\ell(\mathbf{w})|\leq C^\ell\frac{T^{1+\alpha_\ell}}{N}, ∣ d ℓ ( w ) ∣ ≤ C ℓ N T 1 + α ℓ , where C C C
Proof. For integer 0 ≤ s ≤ N 0\leq s\leq N 0 ≤ s ≤ N q ( s ) q(s) q ( s ) s s s N − s N-s N − s q w q_{\mathbf{w}} q w { 0 } ∪ [ A ] \{0\}\cup[A] { 0 } ∪ [ A ] s = 0 , 1 s=0,1 s = 0 , 1 N − s + s j N-s+s^j N − s + s j j ≥ 1 j\geq1 j ≥ 1 Lemma 3.1 extends q q q 2 T 2T 2 T [ 0 , 1 ] [0,1] [ 0 , 1 ] 0 , … , N 0,\ldots,N 0 , … , N ( 2 T ) 2 ≤ N / 2 (2T)^2 \le N/2 ( 2 T ) 2 ≤ N /2 H = N H=N H = N ℓ \ell ℓ z = ℓ z=\ell z = ℓ d ℓ ( w ) d_\ell(\mathbf{w}) d ℓ ( w )
∣ d ℓ ( w ) ∣ ≤ 2 ℓ ℓ ( 2 ℓ ) ! ( 16 T 2 N ) ℓ ≤ C ℓ ( T 2 N ) ℓ ≤ C ℓ T 1 + α ℓ N . |d_\ell(\mathbf{w})| \le\frac{2^{\ell}\ell}{(2\ell)!}\left(\frac{16T^2}{N}\right)^\ell\le C^\ell\left(\frac{T^2}{N}\right)^\ell\le C^\ell\frac{T^{1+\alpha_\ell}}{N}. ∣ d ℓ ( w ) ∣ ≤ ( 2 ℓ )! 2 ℓ ℓ ( N 16 T 2 ) ℓ ≤ C ℓ ( N T 2 ) ℓ ≤ C ℓ N T 1 + α ℓ . The last inequality follows from T ≤ N α ℓ / ( 1 + α ℓ ) T \le N^{\alpha_\ell/(1+\alpha_\ell)} T ≤ N α ℓ / ( 1 + α ℓ )
( ℓ − 1 ) ( 1 + α ℓ ) − α ℓ ( 2 ℓ − 1 − α ℓ ) = ( 1 − α ℓ ) ( ℓ − 1 − α ℓ ) ≥ 0. (\ell-1)(1+\alpha_\ell)-\alpha_\ell(2\ell-1-\alpha_\ell)=(1-\alpha_\ell)(\ell-1-\alpha_\ell)\ge0. ( ℓ − 1 ) ( 1 + α ℓ ) − α ℓ ( 2 ℓ − 1 − α ℓ ) = ( 1 − α ℓ ) ( ℓ − 1 − α ℓ ) ≥ 0. Now we continue with general w \mathbf{w} w N ≥ 8 A N \ge8A N ≥ 8 A T ≥ 1 T \ge1 T ≥ 1 T 2 ≤ N / 8 T^2 \le N/8 T 2 ≤ N /8 2 ≤ ℓ ≤ A 2 \le\ell\le A 2 ≤ ℓ ≤ A T ≤ N α ℓ / ( 1 + α ℓ ) T \le N^{\alpha_\ell/(1+\alpha_\ell)} T ≤ N α ℓ / ( 1 + α ℓ )
Lemma 4.9. Let w ∈ S m − 1 \mathbf{w}\in S^{m-1} w ∈ S m − 1 ∑ i w i ≤ 3 N / 4 \sum_i w_i \le3N/4 ∑ i w i ≤ 3 N /4 ( w , ℓ ) (\mathbf{w},\ell) ( w , ℓ ) ρ \rho ρ ℓ \ell ℓ b j b_j b j j j j 1 ≤ j < ℓ 1\le j<\ell 1 ≤ j < ℓ n j = 1 + b j n_j=1+b_j n j = 1 + b j n ∗ = min 1 ≤ j < ℓ n j n_*=\min_{1\le j<\ell}n_j n ∗ = min 1 ≤ j < ℓ n j
∣ d ℓ ( w ) ∣ ≤ C ℓ T 1 + α ℓ ρ n 1 n ∗ α ℓ − 1 / 2 , (29) |d_\ell(\mathbf{w})| \le\frac{C^\ell T^{1+\alpha_\ell}}{\sqrt{\rho}\,n_1 n_*^{\alpha_\ell-1/2}}, \tag*{(29)} ∣ d ℓ ( w ) ∣ ≤ ρ n 1 n ∗ α ℓ − 1/2 C ℓ T 1 + α ℓ , (29) where C C C
Proof. The completion is feasible since ∑ i w i + ℓ ≤ 7 N / 8 \sum_i w_i+\ell\le7N/8 ∑ i w i + ℓ ≤ 7 N /8 w i ≤ 1 w_i\le1 w i ≤ 1 i i i Lemma 4.8 gives ∣ d ℓ ( w ) ∣ ≤ C ℓ T 1 + α ℓ / N |d_\ell(\mathbf{w})|\le C^\ell T^{1+\alpha_\ell}/N ∣ d ℓ ( w ) ∣ ≤ C ℓ T 1 + α ℓ / N (29) with ρ = 1 \rho=1 ρ = 1 n 1 = N − ℓ + 1 ≤ N n_1=N-\ell+1\le N n 1 = N − ℓ + 1 ≤ N n ∗ α ℓ − 1 / 2 = 1 n_*^{\alpha_\ell-1/2}=1 n ∗ α ℓ − 1/2 = 1 ℓ = 2 \ell=2 ℓ = 2 n ∗ = 1 n_*=1 n ∗ = 1 ℓ ≥ 3 \ell\ge3 ℓ ≥ 3 N − ℓ N-\ell N − ℓ Lemma 4.6 applies. By Proposition 4.3 , the expected block difference is d ℓ ( w ) d_\ell(\mathbf{w}) d ℓ ( w ) Lemma 4.6 finishes the proof.
Now we have to average over w \mathbf{w} w
Proof of Lemma 4.1 . The independent draws have mean one and is in S S S E [ ∑ i w i ] = m − 1 ≤ N / 2 \mathbb{E}[\sum_i w_i]=m-1\le N/2 E [ ∑ i w i ] = m − 1 ≤ N /2 [27 ] gives the stated bound on Pr [ G c ] \Pr[\mathcal{G}^c] Pr [ G c ]
Let Y j Y_j Y j j j j Y j ∼ Bin ( m − 1 , π ( j ) ) Y_j\sim\operatorname{Bin}(m-1,\pi(j)) Y j ∼ Bin ( m − 1 , π ( j )) G \mathcal{G} G N − ∑ i w i − ℓ ≥ N / 8 N-\sum_i w_i-\ell\ge N/8 N − ∑ i w i − ℓ ≥ N /8 Lemma 4.9 satisfy
ρ = 1 + Y ℓ , n 1 ≥ N / 8 , n j ≥ 1 + Y j ( 1 ≤ j < ℓ ) . \rho=1+Y_\ell,\qquad n_1\ge N/8,\qquad n_j\ge1+Y_j\quad(1\le j<\ell). ρ = 1 + Y ℓ , n 1 ≥ N /8 , n j ≥ 1 + Y j ( 1 ≤ j < ℓ ) . For the following bound, we first apply Lemma 4.9 and we drop the event indicator. We also use the following facts: since α ℓ − 1 / 2 ≥ 0 \alpha_\ell-1/2\ge0 α ℓ − 1/2 ≥ 0 G \mathcal{G} G n ∗ − α ℓ + 1 / 2 ≤ ∑ j = 1 ℓ − 1 ( 1 + Y j ) − α ℓ + 1 / 2 n_*^{-\alpha_\ell+1/2}\le\sum_{j=1}^{\ell-1}(1+Y_j)^{-\alpha_\ell+1/2} n ∗ − α ℓ + 1/2 ≤ ∑ j = 1 ℓ − 1 ( 1 + Y j ) − α ℓ + 1/2 ρ − 1 / 2 ≤ ( 1 + Y ℓ ) − 1 / 2 \rho^{-1/2}\le(1+Y_\ell)^{-1/2} ρ − 1/2 ≤ ( 1 + Y ℓ ) − 1/2
E [ 1 G ∣ d ℓ ( w ) ∣ ] ≤ C ℓ T 1 + α ℓ N ∑ j = 1 ℓ − 1 E [ ( 1 + Y ℓ ) − 1 / 2 ( 1 + Y j ) − α ℓ + 1 / 2 ] ≤ C ℓ T 1 + α ℓ N ( m a ) − α ℓ . \mathbb{E}\left[1_{\mathcal{G}}|d_\ell(\mathbf{w})|\right]\le\frac{C^\ell T^{1+\alpha_\ell}}{N}\sum_{j=1}^{\ell-1}\mathbb{E}\left[(1+Y_\ell)^{-1/2}(1+Y_j)^{-\alpha_\ell+1/2}\right]\le\frac{C^\ell T^{1+\alpha_\ell}}{N}(ma)^{-\alpha_\ell}. E [ 1 G ∣ d ℓ ( w ) ∣ ] ≤ N C ℓ T 1 + α ℓ j = 1 ∑ ℓ − 1 E [ ( 1 + Y ℓ ) − 1/2 ( 1 + Y j ) − α ℓ + 1/2 ] ≤ N C ℓ T 1 + α ℓ ( ma ) − α ℓ . In the last step we used Lemma 3.6 (since α ℓ < 1 \alpha_\ell<1 α ℓ < 1 a ≤ π ( s ) a\le\pi(s) a ≤ π ( s ) ℓ − 1 \ell-1 ℓ − 1 C ℓ C^\ell C ℓ
Proof of Lemma 4.2
We prove Lemma 4.2 by adding a small uniform component and correcting its low moments on r r r
Proof of Lemma 4.2 . Let v = π 1 − π 0 v = \pi_1 - \pi_0 v = π 1 − π 0 π ˉ = ( π 0 + π 1 ) / 2 \bar{\pi} = (\pi_0 + \pi_1)/2 π ˉ = ( π 0 + π 1 ) /2 Λ = 4 A − 1 \Lambda= 4^{A-1} Λ = 4 A − 1 I ′ I' I ′ r − 1 r-1 r − 1 ∣ v ∣ |v| ∣ v ∣ i ∈ I ′ i \in I' i ∈ I ′
v ( i ) = − ∑ j ∉ I ′ v ( j ) L i ( j ) , ∑ i ∈ I ′ ∣ v ( i ) ∣ ≤ Λ ∑ j ∉ I ′ ∣ v ( j ) ∣ . \begin{aligned}
v(i) &= -\sum_{j\notin I'} v(j)L_i(j), &
\sum_{i\in I'} |v(i)| &\leq\Lambda\sum_{j\notin I'} |v(j)|.
\end{aligned} v ( i ) = − j ∈ / I ′ ∑ v ( j ) L i ( j ) , i ∈ I ′ ∑ ∣ v ( i ) ∣ ≤ Λ j ∈ / I ′ ∑ ∣ v ( j ) ∣. Thus the r r r ∣ v ∣ |v| ∣ v ∣ δ / ( ( A + 1 ) ( 1 + Λ ) ) \delta/((A+1)(1+\Lambda)) δ / (( A + 1 ) ( 1 + Λ )) I I I r r r
π ˉ ( i ) ≥ ∣ v ( i ) ∣ / 2 ≥ η : = δ 2 ( A + 1 ) ( 1 + Λ ) . \bar{\pi}(i) \geq|v(i)|/2 \geq\eta:= \frac{\delta}{2(A+1)(1+\Lambda)}. π ˉ ( i ) ≥ ∣ v ( i ) ∣/2 ≥ η := 2 ( A + 1 ) ( 1 + Λ ) δ . Let U U U { 0 } ∪ [ A ] \{0\} \cup[A] { 0 } ∪ [ A ] L i L_i L i I I I e i e_i e i i i i
τ = η / Λ , ω = π ˉ + τ ( U − ∑ i ∈ I E U [ L i ] e i ) . \tau= \eta/\Lambda,\qquad\omega= \bar{\pi} + \tau\left(U-\sum_{i\in I}\mathbb{E}_U[L_i]e_i\right). τ = η /Λ , ω = π ˉ + τ ( U − i ∈ I ∑ E U [ L i ] e i ) . For every polynomial P P P r r r E U [ P ] = ∑ i ∈ I P ( i ) E U [ L i ] \mathbb{E}_U[P] = \sum_{i\in I}P(i)\mathbb{E}_U[L_i] E U [ P ] = ∑ i ∈ I P ( i ) E U [ L i ] r − 1 r-1 r − 1 ∑ i ∈ I ∣ E U [ L i ] ∣ ≤ Λ \sum_{i\in I}|\mathbb{E}_U[L_i]| \leq\Lambda ∑ i ∈ I ∣ E U [ L i ] ∣ ≤ Λ τ Λ = η \tau\Lambda= \eta τ Λ = η I I I
ω ( s ) ≥ τ A + 1 = δ 2 ( A + 1 ) 2 Λ ( 1 + Λ ) ≥ 32 − A δ . \omega(s) \geq\frac{\tau}{A+1} = \frac{\delta}{2(A+1)^2\Lambda(1+\Lambda)} \geq32^{-A}\delta. ω ( s ) ≥ A + 1 τ = 2 ( A + 1 ) 2 Λ ( 1 + Λ ) δ ≥ 3 2 − A δ . The last inequality uses the fact that 2 ( A + 1 ) 2 Λ ( 1 + Λ ) ≤ 4 ( A + 1 ) 2 16 A − 1 ≤ 32 A 2(A+1)^2\Lambda(1+\Lambda) \leq4(A+1)^2 16^{A-1} \leq32^A 2 ( A + 1 ) 2 Λ ( 1 + Λ ) ≤ 4 ( A + 1 ) 2 1 6 A − 1 ≤ 3 2 A A ≥ 2 A \geq2 A ≥ 2 ω \omega ω
∥ ω − π b ∥ 1 ≤ ∥ π ˉ − π b ∥ 1 + τ ( 1 + Λ ) ≤ δ / 2 + 2 η ≤ δ . \|\omega-\pi_b\|_1 \leq\|\bar{\pi}-\pi_b\|_1 + \tau(1+\Lambda) \leq\delta/2 + 2\eta\leq\delta. ∥ ω − π b ∥ 1 ≤ ∥ π ˉ − π b ∥ 1 + τ ( 1 + Λ ) ≤ δ /2 + 2 η ≤ δ . Applications
In this section, we illustrate the moment matching method on various applications such as k k k Theorems 2.5 and 2.6 give quantum lower bounds, which we transfer to graph testing problems and junta testing by reductions. Table 1 compares the resulting bounds with previous randomized and quantum query bounds and identifies the argument used. The list of applications is not exhaustive, the purpose of this section is only to provide some interesting examples where our main theorems can be applied. Throughout, k k k ε \varepsilon ε a k = ( 2 k − 1 − 1 ) / ( 2 k − 1 ) a_k = (2^{k-1} - 1)/(2^k - 1) a k = ( 2 k − 1 − 1 ) / ( 2 k − 1 )
Preliminaries for applications
We denote [ R ] 0 = { 0 , 1 , … , R } [R]_0 = \{0,1,\ldots,R\} [ R ] 0 = { 0 , 1 , … , R } x ∈ Σ I x \in\Sigma^I x ∈ Σ I Σ \Sigma Σ I I I s = ( s 1 , … , s N ) s=(s_1,\ldots,s_N) s = ( s 1 , … , s N ) ≤ R \le R ≤ R I = [ N ] I=[N] I = [ N ] Σ = [ R ] \Sigma=[R] Σ = [ R ]
In the bounded-degree graph model , we query the adjacency lists of the vertices of the input graph. For a graph with vertex set V V V d d d I = V × [ d ] I=V\times[d] I = V × [ d ] Σ = V ∪ { ⊥ } \Sigma=V\cup\{\perp\} Σ = V ∪ { ⊥ } ( v , i ) (v,i) ( v , i ) i i i v v v ⊥ \perp ⊥ unidirectional model , the algorithm only has access to the list of out-neighbors of the vertices. On the other hand, in the bidirectional model , there are two lists: one for the out-neighbors and one for the in-neighbors, so the algorithm has to specify if it would like to learn the i i i v v v
In quantum query complexity, the algorithm can use a unitary query operator, and for input x ∈ Σ I x\in\Sigma^I x ∈ Σ I O x ∣ i ⟩ ∣ z ⟩ = ∣ i ⟩ ∣ z + x i m o d ∣ Σ ∣ ⟩ O_x\lvert i\rangle\lvert z\rangle=\lvert i\rangle\lvert z+x_i\bmod\lvert\Sigma\rvert\rangle O x ∣ i ⟩ ∣ z ⟩ = ∣ i ⟩ ∣ z + x i mod ∣ Σ ∣⟩ z ∈ Σ z\in\Sigma z ∈ Σ i ∈ I i\in I i ∈ I
A property is a predicate P : D P → { 0 , 1 } \mathcal{P}:D_{\mathcal{P}}\to\{0,1\} P : D P → { 0 , 1 } D P ⊆ Σ I D_{\mathcal{P}}\subseteq\Sigma^I D P ⊆ Σ I x x x P \mathcal{P} P x ∈ P x\in\mathcal{P} x ∈ P x , y ∈ Σ I x,y\in\Sigma^I x , y ∈ Σ I
dist ( x , y ) = ∣ { i ∈ I : x i ≠ y i } ∣ ∣ I ∣ . \operatorname{dist}(x,y)=\frac{\left|\{i\in I:x_i\ne y_i\}\right|}{|I|}. dist ( x , y ) = ∣ I ∣ ∣ { i ∈ I : x i = y i } ∣ . We say that x x x ε \varepsilon ε P \mathcal{P} P dist ( x , y ) > ε \operatorname{dist}(x,y)>\varepsilon dist ( x , y ) > ε y ∈ P y\in\mathcal{P} y ∈ P
In the case of graphs, a graph property is defined as a set of graphs that is closed under graph isomorphism. In the case of bounded-degree graphs with maximum degree bound d d d ∣ V ∣ d |V|d ∣ V ∣ d
In property testing , an algorithm, also called a ε \varepsilon ε P \mathcal{P} P ε \varepsilon ε P \mathcal{P} P 2 / 3 2/3 2/3
The problem of k k k k k k [28 ] and their quantum versions were studied in [3 ] . The former is a general directed subgraph-freeness problem where the forbidden subgraph is restricted to having k k k S S S S S S S S S k k k k k k
We also present directed planarity and outerplanarity testing lower bounds. Here, planarity and outerplanarity refer to the underlying undirected graph obtained by ignoring arc directions and replacing each antiparallel edge pair by a single edge, but the oracle gives only outgoing neighbors in the unidirectional model defined above. Recall that an undirected graph G G G planar if it can be drawn in the plane such that edges intersect only at common endpoints. Similarly, G G G outerplanar if it can be drawn in a planar way with every vertex on the boundary of the outer (unbounded) face.
Testing distinctness and graph properties
We apply Theorem 2.6 to the classical hard instances considered by Peng and Wang [33 ] , then transfer the distinctness bound to graph testing through a local encoding.
The classical frequencies give a quantum lower bound
The classical random variables X 0 , X 1 X_0, X_1 X 0 , X 1 [ k ] [k] [ k ] [33 Section 2.2, Lemma 11] have k − 1 k-1 k − 1 [33 ] and apply Theorem 2.6 ; it remains to check that its input distributions satisfy the testing promises.
Corollary 5.1 (Testing k k k k ≥ 2 k \ge2 k ≥ 2 ε k = 1 / ( k 2 k ) \varepsilon_k = 1/(k2^k) ε k = 1/ ( k 2 k ) M ≥ N M \ge N M ≥ N 0 < ε ≤ ε k 0 < \varepsilon\le\varepsilon_k 0 < ε ≤ ε k
E k , N , M = { f : [ N ] → [ M ] : ∣ f − 1 ( a ) ∣ < k for every a ∈ [ M ] } \mathcal{E}_{k,N,M} = \{f : [N] \to[M] : |f^{-1}(a)| < k \text{ for every } a \in[M]\} E k , N , M = { f : [ N ] → [ M ] : ∣ f − 1 ( a ) ∣ < k for every a ∈ [ M ]} has quantum query complexity Ω ( N a k ) \Omega(N^{a_k}) Ω ( N a k ) k k k a k = ( 2 k − 1 − 1 ) / ( 2 k − 1 ) a_k = (2^{k-1} - 1)/(2^k - 1) a k = ( 2 k − 1 − 1 ) / ( 2 k − 1 )
Proof. Let us consider X 0 , X 1 X_0, X_1 X 0 , X 1 [33 Section 2.2] . Besides their k − 1 k-1 k − 1
Pr [ X 0 = k ] = 0 , Pr [ X 1 = k ] E [ X 1 ] = 1 k 2 k − 2 = 4 ε k . \Pr[X_0 = k] = 0,\qquad\frac{\Pr[X_1 = k]}{\mathbb{E}[X_1]} = \frac{1}{k2^{k-2}} = 4\varepsilon_k. Pr [ X 0 = k ] = 0 , E [ X 1 ] Pr [ X 1 = k ] = k 2 k − 2 1 = 4 ε k . For M = N M=N M = N Π b , N \Pi_{b,N} Π b , N Definition 2.1 . Under Π 0 , N \Pi_{0,N} Π 0 , N E k , N , N \mathcal{E}_{k,N,N} E k , N , N Definition 2.1 , each sampled multiplicity equals k k k Pr [ X b = k ] / E [ X b ] \Pr[X_b = k]/\mathbb{E}[X_b] Pr [ X b = k ] / E [ X b ] 1 − e − Ω ( N ) 1-e^{-\Omega(N)} 1 − e − Ω ( N ) Π 1 , N \Pi_{1,N} Π 1 , N ε k N \varepsilon_kN ε k N k k k 1 − o ( 1 ) 1-o(1) 1 − o ( 1 ) ε k \varepsilon_k ε k E k , N , N \mathcal{E}_{k,N,N} E k , N , N 1 / 3 − o ( 1 ) 1/3-o(1) 1/3 − o ( 1 )
For T > c N T > c\sqrt{N} T > c N Theorem 2.6 , with A = r = k A=r=k A = r = k
1 3 − o ( 1 ) ≤ C k T 2 − 2 1 − k N 1 − 2 1 − k + N e − c N / k 2 . \frac{1}{3}-o(1) \le C^k\frac{T^{2-2^{1-k}}}{N^{1-2^{1-k}}}+Ne^{-cN/k^2}. 3 1 − o ( 1 ) ≤ C k N 1 − 2 1 − k T 2 − 2 1 − k + N e − c N / k 2 . Thus T = Ω ( N a k ) T=\Omega(N^{a_k}) T = Ω ( N a k ) [ M ] [M] [ M ] □ \square □
Previous quantum bounds The bound Ω ( N 1 / 2 − 1 / ( 2 k ) / log 2 N ) \Omega(N^{1/2-1/(2k)}/\log^2 N) Ω ( N 1/2 − 1/ ( 2 k ) / log 2 N ) [3 Theorem 4.1] comes from dual polynomials, and [PW27, Theorem 7.2] obtained the same bound (with a worse logarithmic factor) even for bounded multiplicities. Corollary 5.1 improves this exponent for k ≥ 3 k \ge3 k ≥ 3 [3 Sections 1.3 and 1.5.1] . The optimal lower bound of Ω ( N 1 / 3 ) \Omega(N^{1/3}) Ω ( N 1/3 ) k = 2 k=2 k = 2 [5 ] (since a two-to-one function is ( 1 / 2 ) (1/2) ( 1/2 ) k ≥ 3 k \ge3 k ≥ 3 finding k k k [29 ] .
Graph consequences
We describe the standard local reduction that maps a k k k k k k
Let K a , b K_{a,b} K a , b a a a b b b f : [ N ′ ] → [ N ′ ] f : [N'] \to[N'] f : [ N ′ ] → [ N ′ ] G q ( f ) G_q(f) G q ( f ) N = N ′ ( q + 1 ) N = N'(q+1) N = N ′ ( q + 1 ) u i u_i u i v a , j v_{a,j} v a , j i , a ∈ [ N ′ ] i,a \in[N'] i , a ∈ [ N ′ ] j ∈ [ q ] j \in[q] j ∈ [ q ] q q q
u i ⟶ v f ( i ) , j . (30) u_i \longrightarrow v_{f(i),j}. \tag*{(30)} u i ⟶ v f ( i ) , j . (30) By this construction, each value of multiplicity c a c_a c a K c a , q K_{c_a,q} K c a , q q q q k k k
For q = 1 q=1 q = 1 k k k k k k k k k
For q = 3 q=3 q = 3 k = 3 k=3 k = 3 K 3 , 3 K_{3,3} K 3 , 3
For q = 2 q=2 q = 2 k = 3 k=3 k = 3 K 3 , 2 K_{3,2} K 3 , 2
Thus, we obtain the following corollary.
Corollary 5.2 (Graph testing problems). In the unidirectional bounded-degree model, the following quantum query lower bounds hold for N N N
For any constant k k k 0 < ε ≤ ε k / 4 0 < \varepsilon\le\varepsilon_k/4 0 < ε ≤ ε k /4 k k k Ω ( N a k ) \Omega(N^{a_k}) Ω ( N a k ) k k k
For 0 < ε ≤ 1 / 576 0 < \varepsilon\le1/576 0 < ε ≤ 1/576 Ω ( N 3 / 7 ) \Omega(N^{3/7}) Ω ( N 3/7 )
For 0 < ε ≤ 1 / 288 0 < \varepsilon\le1/288 0 < ε ≤ 1/288 Ω ( N 3 / 7 ) \Omega(N^{3/7}) Ω ( N 3/7 )
The bounds hold already on bipartite directed acyclic graphs whose indegree and undirected degree are at most k k k
Proof. Under the promise that multiplicities are at most k k k ε k \varepsilon_k ε k k k k N ′ N' N ′ ε k N ′ \varepsilon_kN' ε k N ′ k k k G q ( f ) G_q(f) G q ( f ) (30) . Thus G q ( f ) G_q(f) G q ( f ) N ′ = ⌊ N / ( q + 1 ) ⌋ N' = \lfloor N/(q+1)\rfloor N ′ = ⌊ N / ( q + 1 )⌋ ε k N ′ / ( q N ) ≥ ε k / [ 2 q ( q + 1 ) ] \varepsilon_kN'/(qN) \ge\varepsilon_k/[2q(q+1)] ε k N ′ / ( q N ) ≥ ε k / [ 2 q ( q + 1 )]
Table 2.
We finally apply Corollary 5.1, with the same k k k k = 3 k=3 k = 3
Previous quantum bounds For k k k k k k [3 ] transfers its k k k Ω ( N 1 / 2 − 1 / ( 2 k ) / log 2 N ) \Omega(N^{1/2-1/(2k)}/\log^2 N) Ω ( N 1/2 − 1/ ( 2 k ) / log 2 N ) q = 1 q=1 q = 1 Ω ~ ( N 1 / 2 − 1 / ( 2 k ) ) \widetilde{\Omega}(N^{1/2-1/(2k)}) Ω ( N 1/2 − 1/ ( 2 k ) ) Ω ~ ( N 1 / 3 ) \widetilde{\Omega}(N^{1/3}) Ω ( N 1/3 )
Image-size and junta testing
We use r = Θ ( log N ) r=\Theta(\log N) r = Θ ( log N ) A = O ( r 2 ) A=O(r^2) A = O ( r 2 )
Classical moment construction
Let us first revisit the classical moment construction for this problem. In fact, [RRSS09, Theorem 4.5] presented a similar construction for the distinct elements problem, which is related to image size testing. Their construction considers A = O ( exp ( r ) ) A=O(\exp(r)) A = O ( exp ( r )) A = O ( r 2 ) A=O(r^2) A = O ( r 2 ) § 9 .
Lemma 5.3. For fixed 0 < η < 1 / 2 0<\eta<1/2 0 < η < 1/2 r ≥ 2 r\ge2 r ≥ 2 X 0 , X 1 X_0,X_1 X 0 , X 1 [ A ] [A] [ A ] A ≤ C r 2 A\le Cr^2 A ≤ C r 2
E [ X 0 j ] E [ X 0 ] = E [ X 1 j ] E [ X 1 ] ( 1 ≤ j < r ) , 1 E [ X 0 ] ≥ 1 − η , 1 E [ X 1 ] ≤ η . \frac{\mathbb{E}[X_0^j]}{\mathbb{E}[X_0]}=\frac{\mathbb{E}[X_1^j]}{\mathbb{E}[X_1]}\quad(1\le j<r),\qquad\frac{1}{\mathbb{E}[X_0]}\ge1-\eta,\qquad\frac{1}{\mathbb{E}[X_1]}\le\eta. E [ X 0 ] E [ X 0 j ] = E [ X 1 ] E [ X 1 j ] ( 1 ≤ j < r ) , E [ X 0 ] 1 ≥ 1 − η , E [ X 1 ] 1 ≤ η . Here C C C η \eta η
Remark 5.4. The quadratic bound on the largest multiplicity also improves the lower bound obtained from the classical argument of [RRSS09]. Their construction [RRSS09, Theorem 4.5] uses A = O ( exp ( r ) ) A=O(\exp(r)) A = O ( exp ( r )) Ω ( N 1 − o ( 1 ) ) \Omega(N^{1-o(1)}) Ω ( N 1 − o ( 1 ) ) Ω ( N ( log log N log N ) 4 ) \Omega\left(N\left(\frac{\log\log N}{\log N}\right)^4\right) Ω ( N ( l o g N l o g l o g N ) 4 ) Ω ( N / log N ) \Omega(N/\log N) Ω ( N / log N )
Image-size testing
We consider inputs f : [ N ] → [ N ] f:[N]\to[N] f : [ N ] → [ N ] [1 ] , corresponds to testing the property of having image size at most ℓ \ell ℓ ℓ < N \ell<N ℓ < N [11 ] considered a special case of distinguishing image size at most γ N \gamma N γ N 0 < γ < 1 0<\gamma<1 0 < γ < 1 N N N [1 ] , where we distinguish image size at most ⌊ 3 N / 4 ⌋ \lfloor3N/4\rfloor ⌊ 3 N /4 ⌋ ⌈ 7 N / 8 ⌉ \lceil7N/8\rceil ⌈ 7 N /8 ⌉
We apply Theorem 2.5 with the random variables provided by Lemma 5.3. Singleton completion preserves the gap in image sizes.
Corollary 5.5 (Image-size testing). Let P N = { f : [ N ] → [ N ] : ∣ f ( [ N ] ) ∣ ≤ ⌊ 3 N / 4 ⌋ } P_N = \{f : [N] \to[N] : |f([N])| \le\lfloor3N/4 \rfloor\} P N = { f : [ N ] → [ N ] : ∣ f ([ N ]) ∣ ≤ ⌊ 3 N /4 ⌋} Testing P N P_N P N at proximity 1 / 8 1/8 1/8 has quantum query complexity Ω ( N ) \Omega(\sqrt{N}) Ω ( N )
Proof. Let us take r = ⌈ log N ⌉ r = \lceil\log N \rceil r = ⌈ log N ⌉ η = 1 / 10 \eta= 1/10 η = 1/10 X 0 X_0 X 0 X 1 X_1 X 1 μ b = E [ X b ] \mu_b = \mathbb{E}[X_b] μ b = E [ X b ] m = ⌊ N / 2 ⌋ m = \lfloor N/2 \rfloor m = ⌊ N /2 ⌋ Definition 2.1 , each sampled multiplicity has mean 1 1 1 1 / μ b 1/\mu_b 1/ μ b
E f ∼ Π b , N [ ∣ f ( [ N ] ) ∣ ] = N − m ( 1 − 1 / μ b ) + o ( 1 ) , \mathbb{E}_{f\sim\Pi_{b,N}}[|f([N])|] = N - m(1 - 1/\mu_b) + o(1), E f ∼ Π b , N [ ∣ f ([ N ]) ∣ ] = N − m ( 1 − 1/ μ b ) + o ( 1 ) , where the correction term corresponds to the overflow event, which happens with probability o ( 1 ) o(1) o ( 1 ) X 0 X_0 X 0 X 1 X_1 X 1 b = 0 b = 0 b = 0 19 N / 20 + o ( 1 ) 19N/20 + o(1) 19 N /20 + o ( 1 ) b = 1 b = 1 b = 1 11 N / 20 + o ( 1 ) 11N/20 + o(1) 11 N /20 + o ( 1 ) ∣ f ( [ N ] ) ∣ ≥ ⌊ 7 N / 8 ⌋ |f([N])| \ge\lfloor7N/8 \rfloor ∣ f ([ N ]) ∣ ≥ ⌊ 7 N /8 ⌋ X 0 X_0 X 0 ∣ f ( [ N ] ) ∣ ≤ ⌊ 3 N / 4 ⌋ |f([N])| \le\lfloor3N/4 \rfloor ∣ f ([ N ]) ∣ ≤ ⌊ 3 N /4 ⌋ X 1 X_1 X 1 f 1 ∈ P N f_1 \in P_N f 1 ∈ P N f 0 f_0 f 0 1 / 8 1/8 1/8 1 / 3 − o ( 1 ) 1/3 - o(1) 1/3 − o ( 1 )
Applying Theorem 2.5 directly to X 0 X_0 X 0 X 1 X_1 X 1 A = O ( r 2 ) A = O(r^2) A = O ( r 2 ) T ∈ Ω ( N ) T \in\Omega(\sqrt{N}) T ∈ Ω ( N )
Previous quantum bounds Ambainis, Belovs, Regev, and de Wolf [1 ] proved a lower bound of Ω ( N 1 / 3 ) \Omega(N^{1/3}) Ω ( N 1/3 ) [11 Theorem 6.2 and Section 6.1.2] improved the lower bound to Ω ( N / log 2 N ) \Omega(\sqrt{N}/\log^2 N) Ω ( N / log 2 N ) N N N γ N \gamma N γ N Corollary 5.5 removes the log 2 N \log^2 N log 2 N ⌊ 3 N / 4 ⌋ \lfloor3N/4 \rfloor ⌊ 3 N /4 ⌋ ⌊ 7 N / 8 ⌋ \lfloor7N/8 \rfloor ⌊ 7 N /8 ⌋ [32 Theorem 2] .
Remark 5.6. Theorem 2.6 improves the lower bound from Theorem 2.5 when A A A r r r A A A Corollary 5.5 , we take r = ⌈ log N ⌉ r = \lceil\log N \rceil r = ⌈ log N ⌉ A = Θ ( r 2 ) A = \Theta(r^2) A = Θ ( r 2 ) Theorem 2.6 would yield a suboptimal lower bound of Ω ( N 1 / 2 − o ( 1 ) ) \Omega(N^{1/2-o(1)}) Ω ( N 1/2 − o ( 1 ) )
Junta testing by reduction
A Boolean K K K K K K [1 Lemma 6.3] (already present in [6 ] ) to Corollary 5.5 . Since this reduction is standard in the literature (see e.g., [11 Section 6.2] ), we only state the result.
Corollary 5.7 (Junta testing). Testing Boolean K K K juntas at proximity 1 / 3 1/3 1/3 has quantum query complexity Ω ( K ) \Omega(\sqrt{K}) Ω ( K )
Previous quantum bounds [1 ] proved a lower bound of Ω ( K 1 / 3 ) \Omega(K^{1/3}) Ω ( K 1/3 ) [11 ] to Ω ( K / log 2 K ) \Omega(\sqrt{K}/\log^2 K) Ω ( K / log 2 K )
Acknowledgements
CK’s and FM’s research was supported in part by a bilateral grant between the Université Paris Cité and the National University of Singapore (2026-01-RESEARCH/UPCité-NUS and ANR-18-IDEX-0001), the French PEPR integrated projects EPIQ (ANR-22-PETQ-0007) and HQI (ANR-22-PNCQ-0002), and the ERC Advanced Grant PARQ.
SS’s research was supported by the NRF Investigatorship award (NRF-NRFI10-2024-0006) and CQT Young Researcher Career Development Grant (25-YRCDG-SS).
DS’s research was supported by the German Federal Ministry of Research, Technology and Space (QuSol, 13N17173), by the Deutsche Forschungsgemeinschaft under Germany’s Excellence Strategy – EXC-2111 – 390814868, and by the Munich Quantum Valley.
AI statement. We used GPT-6 Astra, GPT-6.1 Sol and Claude Opus 5.5 to explore proof strategies, refine mathematical arguments, search for related literature, and improve the presentation. The authors subsequently verified, simplified, and organized the argument, and rewrote its exposition. Important concepts and ideas were manually factored out and written down in an intuitive, understandable way. The authors take full responsibility for the correctness and content of the paper.
References
Deferred proofs on polynomials
We provide the missing proofs of some lemmas from § 3.1.2 . We restate these lemmas for ease of reading.
Lemma 3.2 (Taylor bound). Let H ≥ 1 H \ge1 H ≥ 1 d ≥ 0 d \ge0 d ≥ 0 d 2 ≤ H / 2 d^2 \le H/2 d 2 ≤ H /2 q ( z ) = ∑ ℓ = 0 d a ℓ z ℓ q(z) = \sum_{\ell=0}^{d} a_{\ell}z^{\ell} q ( z ) = ∑ ℓ = 0 d a ℓ z ℓ d d d ∣ q ( z ) ∣ ≤ 1 \lvert q(z)\rvert\le1 ∣ q ( z )∣ ≤ 1 z ∈ { 0 } ∪ [ H ] = { 0 , 1 , … , H } z \in\{0\} \cup[H] = \{0,1,\ldots,H\} z ∈ { 0 } ∪ [ H ] = { 0 , 1 , … , H } r ≥ 1 r \ge1 r ≥ 1 Q r = ∑ ℓ = 0 min ( r − 1 , r ) a ℓ z ℓ Q_r = \sum_{\ell=0}^{\min(r-1,r)} a_{\ell}z^{\ell} Q r = ∑ ℓ = 0 m i n ( r − 1 , r ) a ℓ z ℓ z ∈ [ 0 , H ] z \in[0,H] z ∈ [ 0 , H ]
∣ q ( z ) − Q r ( z ) ∣ ≤ 2 ( 2 r ) ! ( 4 d 2 H ) r z r . (31) \lvert q(z) - Q_r(z)\rvert\le\frac{2}{(2r)!}\left(\frac{4d^2}{H}\right)^r z^r. \tag*{(31)} ∣ q ( z ) − Q r ( z )∣ ≤ ( 2 r )! 2 ( H 4 d 2 ) r z r . (31) Proof. Denote M = ∥ q ∥ [ 0 , H ] = max z ∈ [ 0 , H ] ∣ q ( z ) ∣ M=\lVert q\rVert_{[0,H]}=\max_{z\in[0,H]}|q(z)| M = ∥ q ∥ [ 0 , H ] = max z ∈ [ 0 , H ] ∣ q ( z ) ∣
∥ q ′ ∥ [ 0 , H ] ≤ 2 d 2 H M . \lVert q'\rVert_{[0,H]}\le\frac{2d^2}{H}M. ∥ q ′ ∥ [ 0 , H ] ≤ H 2 d 2 M . where q ′ q' q ′ q q q M M M 1 / 2 1/2 1/2
M ≤ 1 + 1 2 ∥ q ′ ∥ [ 0 , H ] ≤ 1 + d 2 H M ≤ 1 + M 2 , M\le1+\frac{1}{2}\lVert q'\rVert_{[0,H]}\le1+\frac{d^2}{H}M\le1+\frac{M}{2}, M ≤ 1 + 2 1 ∥ q ′ ∥ [ 0 , H ] ≤ 1 + H d 2 M ≤ 1 + 2 M , hence M ≤ 2 M\le2 M ≤ 2
If r > d r>d r > d [ − 1 , 1 ] [-1,1] [ − 1 , 1 ] [ 0 , H ] [0,H] [ 0 , H ]
∥ q ( r ) ∥ [ 0 , H ] r ! ≤ M r ! ( 2 H ) r d 2 r ( 2 r − 1 ) ! ! ≤ 2 ( 2 r ) ! ( 4 d 2 H ) r , \frac{\lVert q^{(r)}\rVert_{[0,H]}}{r!}\le\frac{M}{r!}\left(\frac{2}{H}\right)^r\frac{d^{2r}}{(2r-1)!!}\le\frac{2}{(2r)!}\left(\frac{4d^2}{H}\right)^r, r ! ∥ q ( r ) ∥ [ 0 , H ] ≤ r ! M ( H 2 ) r ( 2 r − 1 )!! d 2 r ≤ ( 2 r )! 2 ( H 4 d 2 ) r , where q ( r ) q^{(r)} q ( r ) r r r r ! ( 2 r − 1 ) ! ! = ( 2 r ) ! / 2 r r!(2r-1)!!=(2r)!/2^r r ! ( 2 r − 1 )!! = ( 2 r )! / 2 r [22 ] . Applying Taylor’s theorem we get (10). □
Lemma 3.3 (Newton bound). Let H ≥ 1 H\ge1 H ≥ 1 d ≥ 0 d\ge0 d ≥ 0 q ( z ) q(z) q ( z ) d d d ∣ q ( z ) ∣ ≤ 1 |q(z)|\le1 ∣ q ( z ) ∣ ≤ 1 z ∈ { 0 } ∪ [ H ] z\in\{0\}\cup[H] z ∈ { 0 } ∪ [ H ]
d ℓ = ∑ s = 0 ℓ ( − 1 ) ℓ − s ( ℓ s ) q ( s ) ( 0 ≤ ℓ ≤ H ) . d_\ell=\sum_{s=0}^{\ell}(-1)^{\ell-s}\binom{\ell}{s}q(s)\qquad(0\le\ell\le H). d ℓ = s = 0 ∑ ℓ ( − 1 ) ℓ − s ( s ℓ ) q ( s ) ( 0 ≤ ℓ ≤ H ) . For an integer 1 ≤ r ≤ H + 1 1\le r\le H+1 1 ≤ r ≤ H + 1 Q r ( z ) = ∑ ℓ = 0 r − 1 d ℓ ( z ℓ ) Q_r(z)=\sum_{\ell=0}^{r-1}d_\ell\binom{z}{\ell} Q r ( z ) = ∑ ℓ = 0 r − 1 d ℓ ( ℓ z ) z ∈ { 0 } ∪ [ H ] z\in\{0\}\cup[H] z ∈ { 0 } ∪ [ H ]
q ( z ) − Q r ( z ) = ∑ ℓ = r H d ℓ ( z ℓ ) = ∑ ℓ = r z d ℓ ( z ℓ ) , q(z)-Q_r(z)=\sum_{\ell=r}^{H}d_\ell\binom{z}{\ell}=\sum_{\ell=r}^{z}d_\ell\binom{z}{\ell}, q ( z ) − Q r ( z ) = ℓ = r ∑ H d ℓ ( ℓ z ) = ℓ = r ∑ z d ℓ ( ℓ z ) , where empty sums are understood to be zero. Assume moreover that d 2 ≤ H / 2 d^2\le H/2 d 2 ≤ H /2 1 ≤ r ≤ H + 1 1\le r\le H+1 1 ≤ r ≤ H + 1 z ∈ { 0 } ∪ [ H ] z\in\{0\}\cup[H] z ∈ { 0 } ∪ [ H ]
∣ q ( z ) − Q r ( z ) ∣ ≤ 2 ( 2 r ) ! ( 4 d 2 H ) r z r . (32) |q(z)-Q_r(z)|\le\frac{2}{(2r)!}\left(\frac{4d^2}{H}\right)^r z^r. \tag*{(32)} ∣ q ( z ) − Q r ( z ) ∣ ≤ ( 2 r )! 2 ( H 4 d 2 ) r z r . (32) Proof. First we observe that
q ( z ) = ∑ ℓ = 0 H d ℓ ( z ℓ ) = ∑ ℓ = 0 z d ℓ ( z ℓ ) . q(z)=\sum_{\ell=0}^{H}d_\ell\binom{z}{\ell}=\sum_{\ell=0}^{z}d_\ell\binom{z}{\ell}. q ( z ) = ℓ = 0 ∑ H d ℓ ( ℓ z ) = ℓ = 0 ∑ z d ℓ ( ℓ z ) . Indeed, for 0 ≤ t ≤ z 0\le t\le z 0 ≤ t ≤ z d ℓ d_\ell d ℓ ( z t ) ( 1 − 1 ) z − t \binom{z}{t}(1-1)^{z-t} ( t z ) ( 1 − 1 ) z − t q ( t ) q(t) q ( t ) t = z t=z t = z
For the bound, extend q q q Q r Q_r Q r q q q 0 , … , r − 1 0,\ldots,r-1 0 , … , r − 1 r > d r>d r > d q q q Q r Q_r Q r r − 1 r-1 r − 1 r r r
∣ q ( z ) − Q r ( z ) ∣ ≤ ∥ q ( r ) ∥ [ 0 , H ] r ! ∣ ∏ j = 0 r − 1 ( z − j ) ∣ ≤ 2 ( 2 r ) ! ( 4 d 2 H ) r z r . \begin{aligned}
|q(z)-Q_r(z)|\le\frac{\lVert q^{(r)}\rVert_{[0,H]}}{r!}\left|\prod_{j=0}^{r-1}(z-j)\right| \\
&\le\frac{2}{(2r)!}\left(\frac{4d^2}{H}\right)^r z^r.
\end{aligned} ∣ q ( z ) − Q r ( z ) ∣ ≤ r ! ∥ q ( r ) ∥ [ 0 , H ] j = 0 ∏ r − 1 ( z − j ) ≤ ( 2 r )! 2 ( H 4 d 2 ) r z r . At integer z < r z < r z < r z ≥ r z \ge r z ≥ r z r z^r z r
Lemma 3.5 (Lagrange interpolation). Let A ≥ 2 A \ge2 A ≥ 2 0 ≤ d ≤ A 0 \le d \le A 0 ≤ d ≤ A s 0 < ⋯ < s d s_0 < \cdots< s_d s 0 < ⋯ < s d { 0 } ∪ [ A ] \{0\} \cup[A] { 0 } ∪ [ A ]
L i ( x ) = ∏ 0 ≤ h ≤ d h ≠ i x − s h s i − s h ( 0 ≤ i ≤ d ) . L_i(x) = \prod_{\substack{0 \le h \le d \\ h \ne i}} \frac{x-s_h}{s_i-s_h} \qquad(0 \le i \le d). L i ( x ) = 0 ≤ h ≤ d h = i ∏ s i − s h x − s h ( 0 ≤ i ≤ d ) . Every polynomial P P P d d d P ( x ) = ∑ i = 0 d P ( s i ) L i ( x ) P(x) = \sum_{i=0}^{d} P(s_i)L_i(x) P ( x ) = ∑ i = 0 d P ( s i ) L i ( x ) t ∈ { 0 } ∪ [ A ] t \in\{0\} \cup[A] t ∈ { 0 } ∪ [ A ] ∑ i = 0 d ∣ L i ( t ) ∣ ≤ 4 A − 1 \sum_{i=0}^{d} |L_i(t)| \le4^{A-1} ∑ i = 0 d ∣ L i ( t ) ∣ ≤ 4 A − 1
Proof. The first identity is the standard Lagrange interpolation formula [23 §3.3(i)] . At a node, ∑ i ∣ L i ( t ) ∣ = 1 \sum_i |L_i(t)| = 1 ∑ i ∣ L i ( t ) ∣ = 1 h h h t t t A − h + 1 A-h+1 A − h + 1 L i ( t ) L_i(t) L i ( t ) ( A ) d (A)_d ( A ) d i ! ( d − i ) ! i!(d-i)! i ! ( d − i )!
∑ i = 0 d ∣ L i ( t ) ∣ ≤ ∑ i = 0 d ( A ) d i ! ( d − i ) ! = 2 d ( A d ) ≤ 4 A − 1 . \sum_{i=0}^{d} |L_i(t)| \le\sum_{i=0}^{d} \frac{(A)_d}{i!(d-i)!} = 2^d {A \choose d} \le4^{A-1}. i = 0 ∑ d ∣ L i ( t ) ∣ ≤ i = 0 ∑ d i ! ( d − i )! ( A ) d = 2 d ( d A ) ≤ 4 A − 1 . To prove the last inequality, observe that 2 d ( A d ) 2^d {A \choose d} 2 d ( d A ) x d x^d x d
( 1 + 2 x ) A = ∑ j = 0 A 2 j ( A j ) x j . (1+2x)^A = \sum_{j=0}^{A} 2^j {A \choose j} x^j. ( 1 + 2 x ) A = j = 0 ∑ A 2 j ( j A ) x j . The largest coefficient of ( 1 + 2 x ) 2 = 1 + 4 x + 4 x 2 (1+2x)^2 = 1+4x+4x^2 ( 1 + 2 x ) 2 = 1 + 4 x + 4 x 2 4 4 4 1 + 2 x 1+2x 1 + 2 x 3 3 3 ( 1 + 2 x ) A (1+2x)^A ( 1 + 2 x ) A 4 ⋅ 3 A − 2 ≤ 4 A − 1 4 \cdot3^{A-2} \le4^{A-1} 4 ⋅ 3 A − 2 ≤ 4 A − 1
Deferred construction of matching moments
Our last missing proof is for a lemma in § 5.3.1 .
Lemma 5.3. For fixed 0 < η < 1 / 2 0 < \eta< 1/2 0 < η < 1/2 r ≥ 2 r \ge2 r ≥ 2 X 0 , X 1 X_0, X_1 X 0 , X 1 [ A ] [A] [ A ] A ≤ C r 2 A \le Cr^2 A ≤ C r 2
E [ X 0 j ] E [ X 0 ] = E [ X 1 j ] E [ X 1 ] ( 1 ≤ j < r ) , 1 E [ X 0 ] ≥ 1 − η , 1 E [ X 1 ] ≤ η . \frac{\mathbb{E}[X_0^j]}{\mathbb{E}[X_0]} = \frac{\mathbb{E}[X_1^j]}{\mathbb{E}[X_1]} \quad(1 \le j < r), \qquad\frac{1}{\mathbb{E}[X_0]} \ge1-\eta, \qquad\frac{1}{\mathbb{E}[X_1]} \le\eta. E [ X 0 ] E [ X 0 j ] = E [ X 1 ] E [ X 1 j ] ( 1 ≤ j < r ) , E [ X 0 ] 1 ≥ 1 − η , E [ X 1 ] 1 ≤ η . Here C C C η \eta η
Proof of Lemma 5.3. Let d = r − 2 d = r-2 d = r − 2 B = ⌈ 2 / η ⌉ B = \lceil2/\eta\rceil B = ⌈ 2/ η ⌉ A = 1 + ⌈ 16 B r 2 / η ⌉ ≤ 48 r 2 / η 2 A = 1+\lceil16Br^2/\eta\rceil\le48r^2/\eta^2 A = 1 + ⌈ 16 B r 2 / η ⌉ ≤ 48 r 2 / η 2
E d = min q : deg q ≤ d max a ∈ [ A ] ∣ a − 1 − q ( a ) ∣ ≤ 1 2 . E_d = \min_{\substack{q:\deg q \le d}} \max_{a \in[A]} |a^{-1} - q(a)| \le\frac{1}{2}. E d = q : d e g q ≤ d min a ∈ [ A ] max ∣ a − 1 − q ( a ) ∣ ≤ 2 1 . The bound E d ≤ 1 / 2 E_d \le1/2 E d ≤ 1/2 q ( a ) = 1 / 2 q(a) = 1/2 q ( a ) = 1/2 q q q d d d ∣ q ( a ) ∣ ≤ a − 1 + E d ≤ 3 / 2 < 2 |q(a)| \le a^{-1} + E_d \le3/2 < 2 ∣ q ( a ) ∣ ≤ a − 1 + E d ≤ 3/2 < 2 a ∈ [ A ] a \in[A] a ∈ [ A ] q ( 1 + z ) / 2 q(1+z)/2 q ( 1 + z ) /2 1 1 1 B B B
∣ q ( 1 ) − q ( B ) ∣ ≤ 8 ( B − 1 ) d 2 A − 1 ≤ η 2 , \lvert q(1)-q(B)\rvert\le\frac{8(B-1)d^{2}}{A-1} \le\frac{\eta}{2}, ∣ q ( 1 ) − q ( B )∣ ≤ A − 1 8 ( B − 1 ) d 2 ≤ 2 η , 2 E d ≥ 1 − 1 B − ∣ q ( 1 ) − q ( B ) ∣ ≥ 1 − η . 2E_d \ge1-\frac{1}{B}-\lvert q(1)-q(B)\rvert\ge1-\eta. 2 E d ≥ 1 − B 1 − ∣ q ( 1 ) − q ( B )∣ ≥ 1 − η . Let us write q q q ∣ a − 1 − q ( a ) ∣ ≤ t \lvert a^{-1}-q(a)\rvert\le t ∣ a − 1 − q ( a )∣ ≤ t
E d = max u , v ∈ R ≥ 0 A ∑ a = 1 A u a − v a a E_d=\max_{u,v\in\mathbb{R}_{\geq0}^{A}} \sum_{a=1}^{A}\frac{u_a-v_a}{a} E d = u , v ∈ R ≥ 0 A max a = 1 ∑ A a u a − v a subject to
∑ a = 1 A ( u a + v a ) = 1 , \sum_{a=1}^{A}(u_a+v_a)=1, a = 1 ∑ A ( u a + v a ) = 1 , ∑ a = 1 A ( u a − v a ) a j = 0 ( 0 ≤ j ≤ d ) . \sum_{a=1}^{A}(u_a-v_a)a^j=0 \qquad(0\leq j\leq d). a = 1 ∑ A ( u a − v a ) a j = 0 ( 0 ≤ j ≤ d ) . For an optimal solution, the j = 0 j=0 j = 0 ∑ a u a = ∑ a v a = 1 / 2 \sum_a u_a=\sum_a v_a=1/2 ∑ a u a = ∑ a v a = 1/2 ν 0 ( a ) = 2 u a \nu_0(a)=2u_a ν 0 ( a ) = 2 u a ν 1 ( a ) = 2 v a \nu_1(a)=2v_a ν 1 ( a ) = 2 v a d d d θ b : = ∑ a ν b ( a ) / a \theta_b:=\sum_a \nu_b(a)/a θ b := ∑ a ν b ( a ) / a θ 0 − θ 1 = 2 E d ≥ 1 − η \theta_0-\theta_1=2E_d\geq1-\eta θ 0 − θ 1 = 2 E d ≥ 1 − η 0 < θ b ≤ 1 0<\theta_b\leq1 0 < θ b ≤ 1 θ 0 ≥ 1 − η \theta_0\geq1-\eta θ 0 ≥ 1 − η θ 1 ≤ η \theta_1\leq\eta θ 1 ≤ η
Pr [ X b = a ] = ν b ( a ) a θ b . \Pr[X_b=a]=\frac{\nu_b(a)}{a\theta_b}. Pr [ X b = a ] = a θ b ν b ( a ) . Then E [ X b ] = 1 / θ b \mathbb{E}[X_b]=1/\theta_b E [ X b ] = 1/ θ b E [ X b j ] / E [ X b ] = ∑ a ν b ( a ) a j − 1 \mathbb{E}[X_b^j]/\mathbb{E}[X_b]=\sum_a \nu_b(a)a^{j-1} E [ X b j ] / E [ X b ] = ∑ a ν b ( a ) a j − 1
