Loading ...
Sorry, an error occurred while loading the content.

340[My Computational Complexity Web Log] Favorite Theorems: Quantum Lower Bounds

Expand Messages
  • Lance
    Nov 8, 2004
    • 0 Attachment
      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 O(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 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 permuation. Ambainis' work formed the basis for many other papers applying the techniques and improving them including work recently presented at Dagstuhl.

      Posted by Lance to My Computational Complexity Web Log at 11/8/2004 09:30:11 AM