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.
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
