� 66.896 Quantum Complexity 2008-11-25 Lecture 22 Lecturer: Scott Aaronson Scribe: Jia Zheng (Colin) (Plan of the remaining classes: next Tuesday on classical simulation of quantum circuits, next Thursday Quantum Open House for topics you’d like to hear more about, next next Tuesday project presentation.) Last time we talked about several results in the setting of one-way communication, which is perhaps the simplest form. Of course we also care about two -way communication, and will discuss problems in both settings today. Basically Alice and Bob each hold some string and want to collectively accomplish some job; we are concerned with how much information they must communicate, rather than the computational feasibility. We talked about Holevo’s theorem, which shows the perhaps surprising result that qubits cannot encode asymptotically more classical bits. We have also seen random access coding, where Bob is only interested in a single bit of Alice’s string. But even when Bob only needs to find a single bit of his choice unknown to Alice, asympto t ic separation— if exists at all—is no more than a logarithmic additive factor. Today we’ll see some separation results. Notation. D1(f), R1(f), Q1(f) are the one-way deterministic, bounded-error randomized, and bounded-error quantum ( respectively) communication complexities. D(f), R(f), Q(f) are the two-way deterministic, bounded-error randomized, and bounded-error quantum (resp ectively) communication complexities. Remark. D1(f) is simply the number of distinct rows in the communication matrix. It can be shown that the definition of R1 is not changed if zero-error is required. There can be exponential separation between D1 and R1, e.g. for “equality of two n-bit strings”, 1 (x = y)EQ(x, y) = 0 (x = y) Clearly D1(EQ) = n, R1(EQ) ∈ Θ(log n) as we have seen la st lecture. Remark. While looking at asymptotic separation, we can safely confine our attention to pure states (for t he qubits to transfer), as any mixed state can be represented by a pure state with twice as many qubits. Mixed states sometimes do save a factor of 2, e.g. for EQ. As a side note, we can show Q1(EQ) ∈ Ω(log n) by a counting argument. Let |ψxidenote the qubits Alice sends to Bob. For every x =6 x′ we want |ψxi and |ψx ′ i to be sufficiently different. How many k-qubit states are there where no two of them have small inner product? The number is in the order of 22k . The intuition is to see states as 2k-bit strings and consider error correcting codes. So with k asymptotically below log n, k qubits cannot help distinguish 22log n different values o f x. We have seen expo nential separation between R1 and D1 . Is there such separation between Q1 and R1? Today we know the answer to be affirmative for partial functions, as partial funct io ns provide much leeway in the definition. But for total functions we are still clueless. 22-1� � Exponential separation between Q1, R1 for partial f Gavinsky et al. found some partia l f where R1(f) ∈ Θ(√n) but Q1(f) ∈ O(log n), based on prior work of Bar-Yossef, Jayram and Kerenidis. Suppose Alice knows the gender x1, . . . , xn of n people where half are male and half female, Bob knows a perfect matching in which either (i) boys are matched to boys, girls to girls, o r (ii) every boy is matched to a girl. How much must Alice send, to help Bob decide which case (orientation)? Remark. If Bob can communicate to Alice he can simply send a pair in the matching using log n bits to hear back if they are gay. If Alice sends genders of a random set of people, how large must the set be to contain at least some pair in Bob’s matching? This is the birthday paradox, so R1(f) ∈ O(√n log n). The log n factor used to store the index can in fact be eliminated, giving R1(f) ∈ O(√n). Let Alice simply send t he equal superposition of all xi (superposition of basis states |ii phase-shifted by xi): n1 √n (−1)xi |ii i=1 Let M denote Bob’s matching. Bob makes up some function satisfying g(i) = g(j) iff (i, j) ∈ M , and computes n1 √n (−1)xi |ii|g(i)i i=1 Measuring the first qubit in a basis containing |ii√ +2|ji, |ii−|√2 jifor any (i, j) ∈ M will collapse the state to (−1)xi |ii + (−1)xj |ji√2 for some (i, j) ∈ M. Then xi ⊕xj (i.e. gay or straight) can be readily found by measuring in Hadamard basis. We can see that this O(lo g n) protocol is zero-error. The hard part of the separation proof is, as usual, to show the lower bound Ω(√n) for R1(f). This is also from Gavinsky et al. No strong separation when Bob’s input is small It t urns out (Aaronson 2004) that D1(f) ∈ O(mQ1(f) log Q1(f)) for all partial and t otal f, where m is the length of Bob’s input. The proof technique is the same as in the argument that BQP/qpoly ⊆ PostBQP/poly where we start with a maximally mixed state. In this setting Alice ha s to specify each input bit of Bob, that is why there is a factor of m. This result implies that m must be large for any function to provide strong separation between Q1 and D1 . For large m, there can indeed be exponential separation as we saw above. The Inner Product Problem This is a problem that seems specifically designed to maximize communication complex-tixy. Alice and Bob hold vectors x and y; they want to find the inner product mod 2. 22-2� Unsurprisingly, the classical and randomized communication complexities are both Ω(n). As it turns out, there is an incredibly slick proo f that Q1(f) and Q(f) are also Ω(n). Proof. Supp ose there is a quantum protocol r equiring less than n qubits. Then Bo b can run the prot ocol on superpo sition of all possible inputs: 1 √2n (−1)xy|yi y∈{0,1}n Given this state, Hadamard it would give Bob the state x, just like the Bernstein-Vazirani problem. This means Bob can learn Alice’s input using less than n qubits,