2.2 Protocol for Disjointness A classic result for Disjn is that the randomized communication complexity(bounded error, two-way communication)is 0(n).Namely, Theorem4.Q(Disjn)=0(vnlogn). Proof.The protocol is actually pretty simple.Just run Grover's search to search for a position i E [n] s.t.xi=yi=1.The Grover's search algorithm is a query algorithm,which uses an oracle 0:∑l0→∑(-140 Note that Disin is nothing but OR(z)where z=xAy.So it is enough to simulate the oracle Oxy in order to invoke Grover's search.Can we use efficient communication to simulate Oxy?Yes. Actually Alice can do∑iiO)→∑iaili)lxi〉and send the working space(which has only logn qubits)to Bob,who can do iaili)xiA yi).Then Bob does iai(-1)xiAyi li)xiA yi).Finally they erase IxiA yi)by doing the first two steps again: ∑a4-)Ay一∑a-woI6AWo6Aw》=∑a-iI0I0 3 SMP communication and quantum fingerprint Recall that the communication complexity for EQ in the private-coin SMP model is). We'll show that if we use quantum communication,then the complexity can be reduced to O(logn). First,let's review the notion of error correcting code.Suppose that a sender A wishes to send an n-bit string xE(0,1)n to a receiver B through a noisy channel.Suppose the message is E(x).The channel flips each bit of E(x)independently with probability at most a small constant e.To cope with the noise,A needs to add some redundancy.What's the minimum length of the message E(x)s.t.B can recover the correct x with probability 99%?The answer is m =0(n).Check:what if we add e and the recovery probability in?Fix such an error correcting code E(x). We'll need another tool called Swap-Test,which measures how close two unknown states are. Suppose that we are given two states,)in register A and l)in register B,and we want to estimate ()Here is the test. Swap-Test:2.2 Protocol for Disjointness A classic result for 𝐃𝐢𝐬𝐣𝑛 is that the randomized communication complexity (bounded error, two-way communication) is 𝛺(𝑛). Namely, Theorem 4. 𝑄(𝐃𝐢𝐬𝐣𝑛 ) = O(√𝑛log 𝑛). Proof. The protocol is actually pretty simple. Just run Grover’s search to search for a position 𝑖 ∈ [𝑛] s.t. 𝑥𝑖 = 𝑦𝑖 = 1. The Grover’s search algorithm is a query algorithm, which uses an oracle 𝑂𝑧 :∑𝛼𝑖 |𝑖〉 𝑖 → ∑𝛼𝑖 (−1) 𝑧𝑖|𝑖〉 𝑖 Note that 𝐃𝐢𝐬𝐣𝑛 is nothing but 𝑂𝑅(𝑧) where 𝑧 = 𝑥 ∧ 𝑦. So it is enough to simulate the oracle 𝑂𝑥∧𝑦 in order to invoke Grover’s search. Can we use efficient communication to simulate 𝑂𝑥∧𝑦? Yes. Actually Alice can do ∑ 𝛼𝑖 |𝑖〉|0〉 𝑖 → ∑ 𝛼𝑖 |𝑖〉 𝑖 |𝑥𝑖 〉 and send the working space (which has only log𝑛 qubits) to Bob, who can do ∑ 𝛼𝑖 |𝑖〉|𝑥𝑖 ∧ 𝑦𝑖 〉 𝑖 . Then Bob does ∑ 𝛼𝑖 (−1) 𝑥𝑖∧𝑦𝑖 |𝑖〉|𝑥𝑖 ∧ 𝑦𝑖 〉 𝑖 . Finally they erase |𝑥𝑖 ∧ 𝑦𝑖 〉 by doing the first two steps again: ∑𝛼𝑖 (−1) 𝑥𝑖∧𝑦𝑖|𝑖〉|𝑥𝑖 ∧ 𝑦𝑖 〉 𝑖 → ∑𝛼𝑖 (−1) 𝑥𝑖∧𝑦𝑖 |𝑖〉|(𝑥𝑖 ∧ 𝑦𝑖 ) ⊕(𝑥𝑖 ∧ 𝑦𝑖)〉 𝑖 = ∑𝛼𝑖 (−1) 𝑥𝑖∧𝑦𝑖 |𝑖〉|0〉 𝑖 3 SMP communication and quantum fingerprint Recall that the communication complexity for 𝐄𝐐𝑛 in the private-coin SMP model is Θ(√𝑛). We’ll show that if we use quantum communication, then the complexity can be reduced to O(log𝑛). First, let’s review the notion of error correcting code. Suppose that a sender A wishes to send an 𝑛-bit string 𝑥 ∈ {0,1} 𝑛 to a receiver B through a noisy channel. Suppose the message is 𝐸(𝑥). The channel flips each bit of 𝐸(𝑥) independently with probability at most a small constant 𝜖. To cope with the noise, A needs to add some redundancy. What’s the minimum length of the message 𝐸(𝑥) s.t. B can recover the correct 𝑥 with probability 99%? The answer is 𝑚 = 𝑂(𝑛). Check: what if we add 𝜖 and the recovery probability in? Fix such an error correcting code 𝐸(𝑥). We’ll need another tool called Swap-Test, which measures how close two unknown states are. Suppose that we are given two states, |𝜓〉 in register A and |𝜙〉 in register B, and we want to estimate 〈𝜓|𝜙〉. Here is the test. Swap-Test: