DEPARTMENT OF MATHEMATICS AND COMPUTER SCIENCE               
                    UNIVERSITY OF SOUTHERN DENMARK, ODENSE                   

               Quantum Information and Communication Complexity              

                                Richard Cleve                                
                        Department of Computer Science                       
                            University of Calgary                            

                     Thursday, May 11, 2000, at 10:15 AM                     
                                   Room 82B                                  


Recent advances  in  communication complexity  in  a setting  where  quantum
information is  available are  reviewed.  Holevo's  Theorem implies  that  n
qubits (quantum bits) cannot convey more  classical information than n bits.
Nevertheless,  there   are  information   processing   tasks  that   require
communication and  for  which  using  qubits  instead  of  bits  results  in
substantial savings.  It  is  also  natural to  view  Bell's  Theorem  about
nonlocality in the context of communication complexity.  We give examples of
scenarios  where   quantum   entanglement   can  be   used   to   circumvent
communication.


                                                       Host: Kim Skak Larsen