Before revision:  We complement our upper bound for PSD testing with \ell_2^2-gap by giving a \tilde{\Omega}(1/\epsilon^2) lower bound for any non-adaptive algorithm.
After revision:  We complement our upper bound for PSD testing with Euclidean norm distance by giving a \tilde{\Omega}(1/\epsilon^2) lower bound for any non-adaptive algorithm.