Quantum Computing (fall2013) Instructor:Shengyu Zhang. Lecture 8 Quantum communication complexity:A recent protocol The original plan was to talk about lower bounds on quantum communication complexity,but it may again well fall into the category of being "too difficult".So after some reflections,I decided to change to something lighter but probably with a broader range of applications. 1.Fourier analysis over {0,1) In computer science,we often run into real-valued functions defined on {0,1)".(Name some examples yourself;you'd find that actually it's even hard to think of any common function we studied that doesn't fall into this category.)These functions form a linear space {f:{0,1m→R} It is easily seen that the addition of any two real-valued functions on the same domain gives another real-valued function on the domain. A standard set of basis of this space contains the following ones: f:s E(0.1)where f(x)=0 (1 ifx=s Actually these basis functions,when scaled up by a factor of v2n,are orthonormal under the inner product defined by (f,g)=Exeto.[f(x)g(x)] where all expectations in this note are over uniform distribution unless stated otherwise. Namely,we have that (fs,f)=6st.There is actually another orthonormal basis defined by characters. {xa:a E{0,1)"}where xa(x)=(-1)ax Exercise.Verify that these character functions form an orthonormal basis
Quantum Computing (Fall 2013) Instructor: Shengyu Zhang. Lecture 8 Quantum communication complexity: A recent protocol The original plan was to talk about lower bounds on quantum communication complexity, but it may again well fall into the category of being “too difficult”. So after some reflections, I decided to change to something lighter but probably with a broader range of applications. 1. Fourier analysis over {𝟎, 𝟏} 𝒏 In computer science, we often run into real-valued functions defined on {0,1} 𝑛 . (Name some examples yourself; you’d find that actually it’s even hard to think of any common function we studied that doesn’t fall into this category.) These functions form a linear space {𝑓:{0,1} 𝑛 → ℝ} It is easily seen that the addition of any two real-valued functions on the same domain gives another real-valued function on the domain. A standard set of basis of this space contains the following ones: {𝑓𝑠 : 𝑠 ∈ {0,1} 𝑛} where 𝑓𝑠 (𝑥) = { 1 𝑖𝑓 𝑥 = 𝑠 0 𝑖𝑓 𝑥 ≠ 𝑠 . Actually these basis functions, when scaled up by a factor of √2 𝑛, are orthonormal under the inner product defined by 〈𝑓, 𝑔〉 = 𝐄𝑥∈{0,1} 𝑛 [𝑓(𝑥)𝑔(𝑥)] where all expectations in this note are over uniform distribution unless stated otherwise. Namely, we have that 〈𝑓𝑠 ,𝑓𝑡 〉 = 𝛿𝑠𝑡. There is actually another orthonormal basis defined by characters. {𝜒𝛼 : 𝛼 ∈ {0,1} 𝑛} where 𝜒𝛼 (𝑥) = (−1) 𝛼⋅𝑥 Exercise. Verify that these character functions form an orthonormal basis
The new basis is usually called the Fourier basis.Any real-valued function can be written in the Fourier basis: F(a)Xa and the coefficients f(a)are called Fourier coefficients,computed by f(a)=E[f(x)xo(x)]. One useful fact about Fourier transform is that the multiplication in one domain becomes the convolution in the other.For f,g:{0,1)nR,their convolution f*g is defined by (f *g)(x)=E[f(y)g(x+y)]=E,[f(x +y)g(y)] In the Fourier domain,the definition is similar except for a normalization factor. -ga=∑foaa+m=∑fa+ma0. Fact.g=ffg=fg. One can define the tp-norm for f as usual: n,-rr)） When p =0,the quantity is the Fourier sparsity of f,i.e.the number of nonzero Fourier coefficients. Similarly,we can define an Lp-norm for f but note that it's more convenient to use the expectation instead of summation. llfllLp =(E.[lf(x)P)p An elegant fact is that fL lfle
The new basis is usually called the Fourier basis. Any real-valued function can be written in the Fourier basis: 𝑓 = ∑𝑓̂(𝛼)𝜒𝛼 𝛼 , and the coefficients 𝑓̂(𝛼) are called Fourier coefficients, computed by 𝑓̂(𝛼) = 𝐄𝑥 [𝑓(𝑥)𝜒𝛼 (𝑥)]. One useful fact about Fourier transform is that the multiplication in one domain becomes the convolution in the other. For 𝑓, 𝑔:{0,1} 𝑛 → ℝ, their convolution 𝑓 ⋆ 𝑔 is defined by (𝑓 ⋆ 𝑔)(𝑥) = 𝐄𝑦 [𝑓(𝑦)𝑔(𝑥 + 𝑦)] = 𝐄𝑦 [𝑓(𝑥 + 𝑦)𝑔(𝑦)] In the Fourier domain, the definition is similar except for a normalization factor. (𝑓̂ ⋆ 𝑔̂)(𝛼) = ∑𝑓̂(𝛽)𝑔̂(𝛼 + 𝛽) 𝛽 = ∑𝑓̂(𝛼 + 𝛽)𝑔̂(𝛽) 𝛽 . Fact. 𝑓𝑔̂ = 𝑓̂ ⋆ 𝑔̂, 𝑓̂⋆ 𝑔 = 𝑓̂𝑔̂. One can define the ℓ𝑝 -norm for 𝑓̂ as usual: ‖𝑓̂‖ ℓ𝑝 = (∑|𝑓̂(𝛼)| 𝑝 𝛼 ) 1/𝑝 When 𝑝 = 0, the quantity is the Fourier sparsity of 𝑓, i.e. the number of nonzero Fourier coefficients. Similarly, we can define an 𝐿𝑝 -norm for 𝑓 but note that it’s more convenient to use the expectation instead of summation. ‖𝑓‖𝐿𝑝 = (𝐄𝑥 [|𝑓(𝑥)| 𝑝]) 1/𝑝 An elegant fact is that ‖𝑓‖𝐿2 = ‖𝑓̂‖ ℓ2
In computer science,we run into Boolean functions a lot.There are two ways of writing expressing a Boolean value-{0,l}or{+1,-1}.Note that the group Z2兰({0,1}，⊕)兰 ({+1,-1),.),where and.are the XOR and multiplication,respectively.These two ways of representing a Boolean value can be exchanged easily as follows.Suppose that we use f for {0,1)-valued function and g for the same function but with range {+1,-1),then f=(1-g)/2,andg=1-2f For Boolean functions with range (+1,-1],we have the following fact. Parseval Identity.For any function f:{0,1}n→{+1，-1}，we have∑af(a)2=1 So one can view f(a)2 as a distribution over all a E (0,1)n. 2.F2-degree,discrete derivatives For Boolean functions f:(0,1)n[0,1],we can either view them as a polynomial over R or a polynomial over F2. Exercise.For the Parity function of 2 bits,write down it as a polynomial f E R[x,x]and f∈F2[x1,x2l Whenever we have a polynomial,we can talk about its degree.Note from the above example that the degree of f as a polynomial over R or that over F2 are different.We denote by deg(f)and deg2(f)the degrees f as a polynomial over R and that over F2, respectively. One interesting operator on functions is the derivative.For any f:{0,1)n[0,1}and any direction vector t E(0,1)",the discrete derivative of f along the direction t is another function △f:{0,1}n→{0,1}defined by△：f(x)=f(x)+f(x+t) Note that when we talk about polynomials over F2,all additions in the above equation are also over F2. Just as derivatives for polynomials over R,the discrete derivative also decrease the degree of a polynomial.That is
In computer science, we run into Boolean functions a lot. There are two ways of writing expressing a Boolean value---{0,1} or {+1, −1}. Note that the group ℤ2 ≅ ({0,1}, ⊕) ≅ ({+1, −1}, ⋅ ), where ⊕ and ⋅ are the XOR and multiplication, respectively. These two ways of representing a Boolean value can be exchanged easily as follows. Suppose that we use 𝑓 for {0,1}-valued function and 𝑔 for the same function but with range {+1, −1}, then 𝑓 = (1 − 𝑔)/2, and 𝑔 = 1 − 2𝑓. For Boolean functions with range {+1, −1}, we have the following fact. Parseval Identity. For any function 𝑓:{0,1} 𝑛 → {+1, −1}, we have ∑ 𝑓̂(𝛼) 2 𝛼 = 1. So one can view 𝑓̂(𝛼) 2 as a distribution over all 𝛼 ∈ {0,1} 𝑛 . 2. 𝔽𝟐 -degree, discrete derivatives For Boolean functions 𝑓:{0,1} 𝑛 → {0,1}, we can either view them as a polynomial over ℝ or a polynomial over 𝔽2 . Exercise. For the Parity function of 2 bits, write down it as a polynomial 𝑓 ∈ ℝ[𝑥1 ,𝑥2 ] and 𝑓 ∈ 𝔽2 [𝑥1 ,𝑥2 ]. Whenever we have a polynomial, we can talk about its degree. Note from the above example that the degree of 𝑓 as a polynomial over ℝ or that over 𝔽2 are different. We denote by deg(𝑓) and deg2 (𝑓) the degrees 𝑓 as a polynomial over ℝ and that over 𝔽2 , respectively. One interesting operator on functions is the derivative. For any 𝑓:{0,1} 𝑛 → {0,1} and any direction vector 𝑡 ∈ {0,1} 𝑛 , the discrete derivative of 𝑓 along the direction 𝑡 is another function 𝛥𝑡𝑓: {0,1} 𝑛 → {0,1} defined by 𝛥𝑡𝑓(𝑥) = 𝑓(𝑥) + 𝑓(𝑥 + 𝑡) Note that when we talk about polynomials over 𝔽2 , all additions in the above equation are also over 𝔽2 . Just as derivatives for polynomials over ℝ, the discrete derivative also decrease the degree of a polynomial. That is
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(𝑓)
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(𝑓̂)|
Protocol: Alice Bob l）=2-1/2(I0)cl0)M +l1)c Eseaf(s)xs(y)IE(s))M) l) On 11)c: lIE(s)》M→Xs(x)lE1(s)》M y=2-1/2(10)clo)M +l1)c∑seAf(s)x,(z)lE1(s)》M) ly ↓Onl1)c:IE(s》M→lsM Ipy'=2-1/2(l0)cl0)w +l1)c Eseaf(s)xs(z)Is)M) Apply FT on M:Is)MN-1/2 Xs(t)lt)M y=(2N)-12(10)c Elt)M +l1)c∑：∑seAf(sxs(z+tlt)M) =(2W)-1/2(Io)c∑tlt)M+l1)c∑tf(z+tlt)M) =N-/r(tM v2 Apply Hadamard on C,then measure M A random t∈{0，1]n and the corresponding f(z+t)
Protocol: Alice Bob |𝜓〉 = 2 −1/2 (|0〉𝐶 |0〉𝑀 +|1〉𝐶 ∑ 𝑓̂(𝑠)𝜒𝑠 (𝑦)|𝐸1 𝑠∈𝐴 (𝑠)〉𝑀) |𝜓〉 On |1〉𝐶: |𝐸1 (𝑠)〉𝑀 → 𝜒𝑠 (𝑥)|𝐸1 (𝑠)〉𝑀 |𝜓〉′ = 2 −1/2 (|0〉𝐶 |0〉𝑀 +|1〉𝐶 ∑ 𝑓̂(𝑠)𝜒𝑠 (𝑧)|𝐸1 𝑠∈𝐴 (𝑠)〉𝑀) |𝜓〉′ On |1〉𝐶: |𝐸1 (𝑠)〉𝑀 → |𝑠〉𝑀 |𝜓〉′ = 2 −1/2 (|0〉𝐶 |0〉𝑀 +|1〉𝐶 ∑ 𝑓̂(𝑠)𝜒𝑠 𝑠∈𝐴 (𝑧)|𝑠〉𝑀) Apply FT on M: |𝑠〉𝑀 → 𝑁−1/2 𝜒𝑠(𝑡)|𝑡〉𝑀 |𝜓〉′ = (2𝑁) −1/2 (|0〉𝐶 ∑𝑡 |𝑡〉𝑀 +|1〉𝐶 ∑ ∑ 𝑓̂(𝑠)𝜒𝑠 𝑡 𝑠∈𝐴 (𝑧 + 𝑡)|𝑡〉𝑀) = (2𝑁) −1/2 (|0〉𝐶 ∑𝑡 |𝑡〉𝑀 + |1〉𝐶 ∑𝑡 𝑓(𝑧 + 𝑡)|𝑡〉𝑀) = 𝑁−1/2 ∑ |0〉𝐶+𝑓(𝑧+𝑡)|1〉𝐶 √2 𝑡 |𝑡〉𝑀 Apply Hadamard on C, then measure M A random 𝑡 ∈ {0,1} 𝑛 and the corresponding 𝑓(𝑧 + 𝑡)
Note See [LS09]for a survey of classical and quantum lower bounds using norm-based methods.The protocol is from [Z14]. Reference [LS09]Troy Lee and Adi Shraibman,Lower bounds on communication complexity,Foundations and Trends in Theoretical Computer Science,2009 [Z14]Shengyu Zhang,Efficient quantum protocols for XOR functions,Proceedings ofthe 25th Annual ACM-SIAMSymposium on Discrete Algorithms(SODA),2014,to appear
Note See [LS09] for a survey of classical and quantum lower bounds using norm-based methods. The protocol is from [Z14]. Reference [LS09] Troy Lee and Adi Shraibman, Lower bounds on communication complexity, Foundations and Trends in Theoretical Computer Science, 2009. [Z14] Shengyu Zhang, Efficient quantum protocols for XOR functions, Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms(SODA), 2014, to appear