Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR10-024 | 21st February 2010 18:25

On a singular value method in quantum communication complexity


Authors: Henning Wunderlich, Stefan Arnold
Publication: 24th February 2010 22:02
Downloads: 898


We introduce a new lower bound method for bounded-error quantum communication complexity,
the \emph{singular value method (svm)}, based on sums of squared singular values of the
communication matrix, and we compare it with existing methods.

The first finding is a constant factor improvement of lower bounds based on the
spectral norm. This is exemplified with an $n/2 - \mcal{O}(1)$ lower bound for
the inner product function mod two.

As our main result we exhibit a function based on quasi-random graphs
such that svm yields a \emph{linear} lower bound while the spectral norm method
only yields a \emph{constant} lower bound.
In addition, we discuss the strength of svm and show that the class of languages with
a low svm value is as hard as the communication complexity version of
the polynomial hierarchy.


Comment #1 to TR10-024 | 18th May 2013 22:49


Authors: Henning Wunderlich
Accepted on: 18th May 2013 22:49


Annoyingly, the main result of this work (svn method) turned out to be "cold coffee",
because it had been derived earlier in the context of sampling, see
Andris Ambainis, Leonard J. Schulman, Amnon Ta-Shma, Umesh V. Vazirani, Avi Wigderson:
The Quantum Communication Complexity of Sampling. FOCS 1998: 342-351

ISSN 1433-8092 | Imprint