Quantum Computing (fall2013) Instructor:Shengyu Zhang. Lecture 7 Quantum communication complexity:upper bounds 1 Classical communication complexity:a brief introduction 1.1 models and definitions In communication complexity,we consider the problem of computing a function with input variables distributed to two(or more)parties.Since each party only holds part of the input,they need to communicate in order to compute the function value.The communication complexity measures the minimum communication needed. The most common communication models include two-way:two parties,Alice and Bob,holding inputs x and y,respectively,talk to each other back and forth one-way:two parties,Alice and Bob,holding inputs x and y,respectively,but only Alice sends a message to Bob. Simultaneous Message Passing (SMP):Three parties:Alice,Bob and Referee.Alice and Bob hold inputs x and y,respectively,and they each send one message to Referee,who then outputs an answer multiparty:k parties,each holding some input variables and they communicate in a certain way. Some example functions are: Equality (EQn):To decide whether x =y,where x,y E(0,1)n. Inner Product (IPn):To compute (x,y)=x1y+..+xnyn mod 2,where x,y E{0,1)n Disjointness(DISJn):To decide whether 3i s.t.xi=yi=1 for x,y E(0,1]n The computation modes include deterministic:all messages are deterministically specified in the protocol.Namely,each message of any party depends only on her input and the previous messages that she saw. randomized:parties can use randomness to decide the messages they send. quantum:the parties have quantum computers and they send quantum messages.Quantum Computing (Fall 2013) Instructor: Shengyu Zhang. Lecture 7 Quantum communication complexity: upper bounds 1 Classical communication complexity: a brief introduction 1.1 models and definitions In communication complexity, we consider the problem of computing a function with input variables distributed to two (or more) parties. Since each party only holds part of the input, they need to communicate in order to compute the function value. The communication complexity measures the minimum communication needed. The most common communication models include  two-way: two parties, Alice and Bob, holding inputs 𝑥 and 𝑦, respectively, talk to each other back and forth.  one-way: two parties, Alice and Bob, holding inputs 𝑥 and 𝑦, respectively, but only Alice sends a message to Bob.  Simultaneous Message Passing (SMP): Three parties: Alice, Bob and Referee. Alice and Bob hold inputs 𝑥 and 𝑦, respectively, and they each send one message to Referee, who then outputs an answer.  multiparty: 𝑘 parties, each holding some input variables and they communicate in a certain way. Some example functions are:  Equality (𝐄𝐐𝑛): To decide whether 𝑥 = 𝑦, where 𝑥,𝑦 ∈ {0,1} 𝑛.  Inner Product (𝐈𝐏𝑛): To compute 〈𝑥,𝑦〉 = 𝑥1𝑦1 + ⋯ + 𝑥𝑛𝑦𝑛 mod 2, where 𝑥,𝑦 ∈ {0,1} 𝑛.  Disjointness (𝐃𝐈𝐒𝐉𝑛): To decide whether ∃𝑖 s.t. 𝑥𝑖 = 𝑦𝑖 = 1 for 𝑥,𝑦 ∈ {0,1} 𝑛. The computation modes include  deterministic: all messages are deterministically specified in the protocol. Namely, each message of any party depends only on her input and the previous messages that she saw.  randomized: parties can use randomness to decide the messages they send.  quantum: the parties have quantum computers and they send quantum messages