Next we give a protocol for a simpler case of exact communication,namely protocols without error. The communication cost is at most 2 logllfllo.The main idea is degree reduction.You'll see how logllfllo naturally comes into the picture when using quantum protocols. The analysis of the protocol needs the following fact. Fact.For any tE(0,1]",supp(Atf)=supp(f)+supp(f). Proof.Let's see what the Fourier coefficients of Atf are.Define f(x)=f(x+t).Then f(a)=ExIf(x+t)xa(x)]=Ey[f(y)xa(y+t)]=Ey[f(y)Xa(y)xa(t)]=f(@)Xa(t). Thus, 4ia=7@=∑7a+f,-∑7a+70xa因 Therefore.if a supp(f)+supp(f),then there isn't B with both f(a+B)and f(B)being nonzero.So Af(a)=0 for those a. Notation in the protocol:f:{0,1n→{+1，-1，A=supp(i,Ek:{0,1→lAl2*],z=x+y. To see why the protocol works,consider the second round.If 4t,f is a constant,then f(z)= f(z+t)+4t,f is known;else,repeat the above procedure for f2=4t,f.Let k=2,and use Ek to encode Fourier coefficients of At,f.Note that though Alice doesn't know t and thusthe Fourier coefficients of 4t,f,she can still do that because for any ti,the Fourier support of 4t,f is within A+A. Complexity:Stage k takes loglA=2k logAl communication qubits,and there is at most d stages.Thus the total complexity is 2d loglsupp(f)l.Next we give a protocol for a simpler case of exact communication, namely protocols without error. The communication cost is at most 2 𝑑 log‖𝑓‖0. The main idea is degree reduction. You’ll see how log‖𝑓‖0 naturally comes into the picture when using quantum protocols. The analysis of the protocol needs the following fact. Fact. For any 𝑡 ∈ {0,1} 𝑛, supp(𝛥̂𝑡𝑓) ⊆ supp(𝑓̂) + supp(𝑓̂). Proof. Let’s see what the Fourier coefficients of 𝛥𝑡𝑓 are. Define 𝑓𝑡 (𝑥) = 𝑓(𝑥 + 𝑡). Then 𝑓𝑡 ̂(𝛼) = 𝐄𝑥 [𝑓(𝑥 + 𝑡)𝜒𝛼 (𝑥)] = 𝐄𝑦 [𝑓(𝑦)𝜒𝛼 (𝑦 + 𝑡)] = 𝐄𝑦 [𝑓(𝑦)𝜒𝛼 (𝑦)𝜒𝛼(𝑡)] = 𝑓̂(𝛼)𝜒𝛼 (𝑡). Thus, 𝛥̂𝑡𝑓(𝛼) = 𝑓̂𝑓𝑡 (𝛼) = ∑𝑓̂(𝛼 + 𝛽)𝑓𝑡 ̂(𝛽) 𝛽 = ∑𝑓̂(𝛼 + 𝛽)𝑓̂(𝛽) 𝛽 𝜒𝛽 (𝑡) Therefore, if 𝛼 ∉ supp(𝑓̂) + supp(𝑓̂), then there isn’ t 𝛽 with both 𝑓̂(𝛼 + 𝛽) and 𝑓̂(𝛽) being nonzero. So 𝛥̂𝑡𝑓(𝛼) = 0 for those 𝛼. Notation in the protocol: 𝑓: {0,1} 𝑛 → {+1,−1}, 𝐴 = supp(𝑓̂), 𝐸𝑘:{0,1} 𝑛 → [|𝐴|2 𝑘 ], 𝑧 = 𝑥 + 𝑦. To see why the protocol works, consider the second round. If 𝛥𝑡1 𝑓 is a constant, then 𝑓(𝑧) = 𝑓(𝑧 + 𝑡1 ) + 𝛥𝑡1 𝑓 is known; else, repeat the above procedure for 𝑓2 = 𝛥𝑡1 𝑓. Let 𝑘 = 2, and use 𝐸𝑘 to encode Fourier coefficients of 𝛥𝑡1 𝑓. Note that though Alice doesn’t know 𝑡1 and thus the Fourier coefficients of 𝛥𝑡1 𝑓, she can still do that because for any 𝑡1, the Fourier support of 𝛥𝑡1 𝑓 is within 𝐴 + 𝐴. Complexity: Stage 𝑘 takes log|A|2 𝑘 = 2 𝑘 log|𝐴| communication qubits, and there is at most 𝑑 stages. Thus the total complexity is 2 𝑑 log|supp(𝑓̂)|