Now notice that r takes value 0 and 1 each with halfprobability,so regardless of the value of the second item,the summation is I always with probability half.Thus with probability half the protocol detects that x≠y. To make the error probability smaller,one can simply repeat the above protocol k times,dropping the error probability to 1/2k In the above protocol we assumed that Alice and Bob have shared randomness.There is a theorem(by Newman)saying that in two-way or one-way models,allowing public-coin randomness doesn't change the complexity by an additive Oflogn)amount,compared to private-coin randomness where each party has her own and private randomness. In the SMP model,however,things are different.The above procedure works if Alice and Bob share public randomness r---They just send (x,r)and (y,r)respectively to Referee,who then compares these two fingerprints.What if they do not share public randomness?Then it turns out that the communication complexity for EQn in the SMP model is (vn).Both upper and lower bounds are nontrivial,and we'll skip the proofs here.(It's in a reading project.) 2 Quantum communication complexity 2.1 Models We define two party two-way model,and others are similar.A protocol goes as follows.Alice performs a unitary operation U on her register A and the channel register C,and then sends the channel register C to Bob.Bob then performsa unitary operation V on his register B and the channel register C,and sends the channel register C back to Alice.And the protocol goes on.The communication cost is the number of qubits of C times the number oftimes C is sent(in either direction).The e-error quantum communication complexity is the minimum communication cost of any quantum protocol that computes the function with error probability at most e. We will use Q(f)to denote the e-error quantum communication complexity for f.We usually omit the subscript e if e=1/3.Now notice that 𝑟𝑖 takes value 0 and 1 each with half probability, so regardless of the value of the second item, the summation is 1 always with probability half. Thus with probability half the protocol detects that 𝑥 ≠ 𝑦. To make the error probability smaller, one can simply repeat the above protocol k times, dropping the error probability to 1/2 𝑘 . In the above protocol we assumed that Alice and Bob have shared randomness. There is a theorem (by Newman) saying that in two-way or one-way models, allowing public-coin randomness doesn’t change the complexity by an additive O(log𝑛) amount, compared to private-coin randomness where each party has her own and private randomness. In the SMP model, however, things are different. The above procedure works if Alice and Bob share public randomness 𝑟---They just send 〈𝑥, 𝑟〉 and 〈𝑦, 𝑟〉 respectively to Referee, who then compares these two fingerprints. What if they do not share public randomness? Then it turns out that the communication complexity for 𝐄𝐐𝑛 in the SMP model is Θ(√𝑛). Both upper and lower bounds are nontrivial, and we’ll skip the proofs here. (It’s in a reading project.) 2 Quantum communication complexity 2.1 Models We define two party two-way model, and others are similar. A protocol goes as follows. Alice performs a unitary operation 𝑈1 on her register A and the channel register C, and then sends the channel register C to Bob. Bob then performs a unitary operation 𝑉1 on his register B and the channel register C, and sends the channel register C back to Alice. And the protocol goes on. The communication cost is the number of qubits of C times the number of times C is sent (in either direction). The 𝜖-error quantum communication complexity is the minimum communication cost of any quantum protocol that computes the function with error probability at most 𝜖. We will use 𝑄𝜖(𝑓) to denote the 𝜖-error quantum communication complexity for 𝑓. We usually omit the subscript 𝜖 if 𝜖 = 1/3