  A Euclidean distance matrix $D(\alpha)$ is defined by
$D_{ij}=(\alpha_i-\alpha_j)^2$, where $\alpha=(\alpha_1,\ldots,\alpha_n)$ is a
real vector. We prove that $D(\alpha)$ cannot be written as a sum of
$\left[2\sqrt{n}-2\right]$ nonnegative rank-one matrices, provided that the
coordinates of $\alpha$ are algebraically independent. This result allows one
to solve several open problems in computation theory. In particular, we provide
an asymptotically optimal separation between the complexities of quantum and
classical communication protocols computing a matrix in expectation.
