Quantum Computation and Information Seminar 

19/04/2005, 16:00 — 17:00 — Room P4.35, Mathematics Building
Caslav Brukner, U Vienna

How to compute a function without knowing its input? Using quantum entanglement!

When the inputs of a function are distributed among remote parties, neither of them can determine its value as every party knows only her/his own data and not the data of the partners. To have an efficiency in computing the function higher than by a simple random guess the partners necessarily need to communicate. I will demonstrate the cases for which already a small amount of communication between the partners leads to the correct value of the function if they share quantum entanglement, while classically the same amount of communication leave them with an efficiency not better than by a random guess. Thus, although entanglement on its own cannot be used for communication (any such communication will also be a superluminal one!) it surprisingly can (significantly) save on communication. Such a reduction of communication complexity might be important in future for speeding up distributed computations, e.g. within VLSI circuits.