Nontrivial expansion in sumsets Let $A \subset \mathbb{Z}/p$, let $f$ be a function on $\mathbb{Z}/p$ and let $B:=\{f(a): a \in A\}$.
Can we conclude that $|A+B|$ is large if $f$ is a sufficiently "nice" function?  For instance say that $f(a)=a^2$.  Then can we say that if $|A|=1000\sqrt{p}$ or even if $|A|=\frac{p}{\log^{*}(p)}$, then $|A+B| \ge p/100$?  
The idea should be that $A+B$ is only small if $A,B$ are related by some additive structure, and if $f$ is a sufficiently random function then it should kill any structure so that $A+B$ should be large.
 A: Here is a partial "yes", to complement Sam Zbarsky's negative answer to the question.
There are a bunch of different papers on this topic focusing on different functions $f$ and in different ranges. To simplify things, I will focus on $f(x)=x^2$, since you mentioned it.
For $|A|< p^{5/8}$, a result of Pham, Vinh and de Zeeuw gives $|A+f(A)| \gg |A|^{6/5}$.
For larger sets, I cannot find a reference from the top of my head, but I am quite confident that exponential sum techniques could prove that
\begin{equation} \label{claim}
|A+f(A)| \gg \min \left \{ \sqrt{p|A|}, \frac{|A|^2}{\sqrt{p}} \right \}.
\end{equation}
See for example Theorem 7 in this paper of Balog, Broughan and Shparlinksi, which implies this result for $f(x)=x^{-1}$. I am pretty sure that I have seen this result with $f(x)=x^2$ in the literature at some point, but cannot remember where right now. If this claim is correct then it is optimal, as you can construct a set $A$ of any given size with $|A+A^2| \ll \sqrt{|A|p}$.
A: We can't. This is written for $f(a)=a^2$ but it should work for any "sufficiently random" function, in fact it uses "randomness".
Let
$$
A=\left\{a\in \left[1,\frac{p}{\sqrt{\log^*p}}\right]\,\Bigg\vert\, f(a)\in \left[1,\frac{p}{\sqrt{\log^*p}}\right]\right\}
$$
Then it's not hard to see that $|A|\ge \frac{p}{10\log^*p}$ (essentially using the fact that squares on intervals $[a,a+\lfloor p/2a\rfloor]$ are approximately uniformly distributed, and looking at $a<\frac{p}{3\sqrt{\log^* p}}$. However,
$$
|A+A|\le\left|\left[1,\frac{2p}{\sqrt{\log^*p}}\right]\right|=\frac{2p}{\sqrt{\log^*p}}
$$
Edited to add: I think this should work for any function $f$ by introducing random offsets to the two intervals; that is we'll get some set $A$ so that both $A$ and $f(A)$ fit in an interval of size $\frac{p}{\sqrt{\log^*p}}$, but $\mathbb E|A|\ge \frac{p}{10\log^*p}$. Thus, some choice of offsets gives a counterexample.
