Quantum Computing and Communication Complexity

Marcos Villagra

A. Montina, Marcel Pfaffhauser, Stefan Wolf

Gilles Brassard A

Angad Mohandas Kamat

Quantum computing resources have been known to provide speed-ups in computational complexity in many algorithms. The impact of these resources in communication, however, has not attracted much attention. We investigate the impact of \nquantum entanglement on communication complexity. We provide a positive result, \nby presenting a class of multi-party communication problems wherein the presence of \na suitable quantum entanglement lowers the classical communication complexity. We \nshow that, in evaluating certains function whose parameters are distributed among \nvarious parties, the presence of prior entanglement can help in reducing the required \ncommunication. We also present an outline of realizing the required entanglement \nthrough optical photon quantum computing. We also suggest the possible impact of \nour results on network information flow problems, by showing an instance of a lower \nbound which can be broken by adding limited power to the communication model.

Ciarán M. Lee, Matty J. Hoban

What kind of object is a quantum state? Is it an object that encodes an exponentially growing amount of information (in the size of the system) or more akin to a probability distribution? It turns out that these questions are sensitive to what we do with the information. For example, Holevo's bound tells us that n qubits only encode n bits of classical information but for certain communication complexity tasks there is an exponential separation between quantum and classical resources. Instead of just contrasting quantum and classical physics, we can place both within a broad landscape of physical theories and ask how non-quantum (and non-classical) theories are different from, or more powerful than quantum theory. For example, in communication complexity, certain (non-quantum) theories can trivialise all communication complexity tasks. In recent work [C. M. Lee and M. J. Hoban, Proc. Royal Soc. A 472 (2190), 2016], we showed that the immense power of the information content of states in general (non-quantum) physical theories is not limited to communication complexity. We showed that, in general physical theories, states can be taken as "advice" for computers in these theories and this advice allows the computers to easily solve any decision problem. Aaronson has highlighted the close connection between quantum communication complexity and quantum computations that take quantum advice, and our work gives further indications that this is a very general connection. In this work, we review the results in our previous work and discuss the intricate relationship between communication complexity and computers taking advice for general theories.

Ronald de Wolf