Subexponential Computation of Truncated Theta Series

We describe an algorithm to compute in $O(e^{c\sqrt{ k\log k}})$ binary operations, for some absolute constant $c>0$, expressions like $\sum_{1\leq n\leq 2^\alpha} e^{\frac{2\pi i n^2}{2^k}} n^a$ and $\sum_{\substack{1\leq n\leq 2^\alpha\\ 1\leq m\leq 2^\beta}} e^{\frac{2\pi i nm}{2^k}} n^a m^b$ where $\alpha,\beta= O(k)$ and $a,b$ are fixed (small) nonnegative integers. The error terms in these computations are $O(e^{-c k})$.