There is no simple answer to such question. You can train neural network with one sample, you'd just overfit to it. Moreover, there are some recent results that in some cases neural networks with few orders of magnitude more parameters than samples can achieve better test set performance than smaller networks. Such rules of thumb don’t even work for much simpler models, e.g. you can fit regularized linear regression to dataset that has less samples than the model parameters. So it is certainly not true that you need the number of samples to be equal to number of parameters squared.
It would also depend on what is your data, for example if it was multiclass classification with ten classes, this makes only 1000 samples per class, on average. Is it many, or little? Say that you are classifying animals based on photos. If there are approximately 360 official dog breeds, and crossbread dogs of many different looks, then having 1000 images of dogs would not catch even a fraction of possible variability of different dogs.
Also keep in mind that neural networks flourish when trained on huge amounts of data, if that is not the case, then I'd start with trying different machine learning algorithms first.