After Bob sends Alice a bit, she responds with a lengthy reply. At the cost of a factor of two in the total communication, Alice could just as well have given Bob her two possible replies at once without listening to him at all, and have him select which one applies. Motivated by a conjecture stating that this form of “round elimination” is impossible in exact quantum communication complexity, we study the orthogonal rank and a symmetric variant thereof for a certain family of Cayley graphs. The orthogonal rank of a graph is the smallest number d for which one can label each vertex with a nonzero d-dimensional complex vector such that adjacent vertices receive orthogonal vectors. We show an exp(n) lower bound on the orthogonal rank of the graph on {0, 1}n in which two strings are adjacent if they have Hamming distance at least n/2. In combination with previous work, this implies an affirmative answer to the above conjecture.

Additional Metadata
Keywords Orthogonal rank, Quantum communication complexity, Round elimination
Journal Quantum Information and Computation
Grant This work was funded by the The Netherlands Organisation for Scientific Research (NWO); grant id nwo/639.071.409 - Quantum and classical data transmission
Briët, J, & Zuiddam, J. (2017). On the orthogonal rank of Cayley graphs and impossibility of quantum round elimination. Quantum Information and Computation, 17(1-2), 106–116.

Additional Files
1608.06113.pdf Author Manuscript , 329kb