Alice and Bob have subsets of {1,…,n}. How much communication do Alice and Bob need to determine if their subsets have a empty intersection. In classical communication complexity even with probabilistic players, Alice and Bob need Ω(n) bits of communication to solve this Set Disjointness Problem.
What if we allow communication with quantum bits? A clever protocol by Buhrman, Cleve and Wigderson based on Grover's quantum search algorithm shows how Alice and Bob can solve Set Disjointness communicating with (up to log factors) n1/2 quantum bits. Could Alice and Bob do better? The best known lower bounds were about O(log n) until Razborov showed the Buhrman-Cleve-Wigderson protocol was essentially optimal.
In another important paper in quantum lower bounds, Andris Ambainis developed the hybrid method for proving lower bounds on quantum query complexity. This method gave researchers a new tool in proving stronger and sometimes tight bounds in the number of queries a quantum algorithm needs to an input to solve a problem like inverting a permutation. Ambainis' work formed the basis for many other papers applying the techniques and improving them including work recently presented at Dagstuhl.
Jain, Radhakrishnan, and Sen have also shown an Omega(n/k^2) quantum c.c. lower bound for the set disjointness problem when the protocols are restricted to be k rounds. This result, on the one hand, is more general than Razborov's, but on the other, yields only an Omega(n^{1/3}) l.b. for arbitrary-round q.c.c. for set disjointness. See http://www.iqc.ca/conferences/qip/presentations/radhakrishnan.pdf for Jaikumar Radhakrishnan's presentation of this work, and http://portal.acm.org/citation.cfm?id=946243.946331 for the FOCS abstract.
ReplyDeleteSiva