deg2(Af)≤deg2(f)-1. When we use {+1,-1}as the range,then the derivative changes to Ag(x)=g(x)g(x+t). 3.Quantum Fourier transform For a function f:{0,1)n{+1,-1),one can define an n-qubit quantum state If one applies Hadamard gates,one on each qubit,then the state becomes Verify this！ 4.XOR functions XOR functions are the class of functions F(x,y)=f(x+y)for some n-bit function f.We sometimes denote such function F by f The class contains interesting functions such as Equality and Hamming Distance.It also has an intimate connection to Fourier analysis because the rank of the communication matrix Me is nothing but the Fourier sparsity of f,i.e.the number of nonzero Fourier coefficients. Exercise.rank(M)= A lower bound for the quantum communication complexity for XOR functions is the following.First, let's define a variant of the Fourier 1-norm. lfl1e=minllgll1:lf(x)-g(xl≤e,x∈{0,1 Theorem([LS09)).Qe(f)=(logllflle). It was considered to be pretty tight,but it has lacked rigorous argument.Recently,the following bound was shown,which implies that the above lower bound is tight for low degree polynomials. Theorem([Z14])Qe(f)=o(2dlogllflle)where d=deg2(f)deg2 (Δ𝑡𝑓) ≤ deg2 (𝑓) − 1. When we use {+1,−1} as the range, then the derivative changes to 𝛥𝑡𝑔(𝑥) = 𝑔(𝑥)𝑔(𝑥 + 𝑡). 3. Quantum Fourier transform For a function 𝑓:{0,1} 𝑛 → {+1,−1}, one can define an n-qubit quantum state 1 √𝑁 ∑𝑓(𝑥)|𝑥〉 𝑥 If one applies Hadamard gates, one on each qubit, then the state becomes 1 √𝑁 ∑𝑓̂(𝛼)|𝛼〉 𝛼 Verify this! 4. XOR functions XOR functions are the class of functions 𝐹(𝑥,𝑦) = 𝑓(𝑥 + 𝑦) for some 𝑛-bit function 𝑓. We sometimes denote such function 𝐹 by 𝑓 ∘⊕ The class contains interesting functions such as Equality and Hamming Distance. It also has an intimate connection to Fourier analysis because the rank of the communication matrix 𝑀𝐹 is nothing but the Fourier sparsity of 𝑓, i.e. the number of nonzero Fourier coefficients. Exercise. rank(𝑀𝑓∘⊕) = ‖𝑓̂‖ 0 . A lower bound for the quantum communication complexity for XOR functions is the following. First, let’s define a variant of the Fourier 1-norm. ‖𝑓‖1,𝜖 = min{‖𝑔‖1 :|𝑓(𝑥) − 𝑔(𝑥)| ≤ 𝜖, ∀𝑥 ∈ {0,1} 𝑛} Theorem ([LS09]). 𝑄𝜖 (𝑓 ∘⊕) = Ω(log‖𝑓‖1,𝜖 ). It was considered to be pretty tight, but it has lacked rigorous argument. Recently, the following bound was shown, which implies that the above lower bound is tight for low degree polynomials. Theorem ([Z14]) 𝑄𝜖 (𝑓 ∘⊕) = 𝑂(2 𝑑 log‖𝑓‖1,𝜖 ) where 𝑑 = deg2(𝑓)