  We undertake a systematic study of sketching a quadratic form: given an $n
\times n$ matrix $A$, create a succinct sketch $\textbf{sk}(A)$ which can
produce (without further access to $A$) a multiplicative
$(1+\epsilon)$-approximation to $x^T A x$ for any desired query $x \in
\mathbb{R}^n$. While a general matrix does not admit non-trivial sketches,
positive semi-definite (PSD) matrices admit sketches of size
$\Theta(\epsilon^{-2} n)$, via the Johnson-Lindenstrauss lemma, achieving the
"for each" guarantee, namely, for each query $x$, with a constant probability
the sketch succeeds. (For the stronger "for all" guarantee, where the sketch
succeeds for all $x$'s simultaneously, again there are no non-trivial
sketches.)
  We design significantly better sketches for the important subclass of graph
Laplacian matrices, which we also extend to symmetric diagonally dominant
matrices. A sequence of work culminating in that of Batson, Spielman, and
Srivastava (SIAM Review, 2014), shows that by choosing and reweighting
$O(\epsilon^{-2} n)$ edges in a graph, one achieves the "for all" guarantee.
Our main results advance this front.
  $\bullet$ For the "for all" guarantee, we prove that Batson et al.'s bound is
optimal even when we restrict to "cut queries" $x\in \{0,1\}^n$.
  In contrast, previous lower bounds showed the bound only for {\em
spectral-sparsifiers}.
  $\bullet$ For the "for each" guarantee, we design a sketch of size $\tilde
O(\epsilon^{-1} n)$ bits for "cut queries" $x\in \{0,1\}^n$. We prove a
nearly-matching lower bound of $\Omega(\epsilon^{-1} n)$ bits. For general
queries $x \in \mathbb{R}^n$, we construct sketches of size
$\tilde{O}(\epsilon^{-1.6} n)$ bits.
