Now showing items 1-2 of 2
Separating quantum communication and approximate rank
One of the best lower bound methods for the quantum communication complexity of a function H (with or without shared entanglement) is the logarithm of the approximate rank of the communication matrix of H. This measure is ...
The complexity of quantum disjointness
We introduce the communication problem QNDISJ, short for Quantum (Unique) Non-Disjointness, and study its complexity under different modes of communication complexity. The main motivation for the problem is that it is a ...