Computational Complexity

Monday, November 08, 2004

 
Favorite Theorems: Quantum Lower Bounds

Posted by Lance

October Edition

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) n^1/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.

Quantum Communication Complexity of Symmetric Predicates by Alexander Razborov.

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.

9:30 AM #

1.  Scott says:  
   
   Actually the hybrid method is due to Bennett, Bernstein, Brassard, and Vazirani; it was a predecessor of Andris's quantum adversary method.
   

   6:32 AM, November 09, 2004

2.  Anonymous says:  
   
   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.
   
   Siva
   

   2:15 PM, November 09, 2004