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