In classical computing, we can run the key search (for example AES) by running parallel computing nodes as many as possible.
It is clear that we can run many Grover's algorithms, too.
My question is; it possible to have a speed up using more than one Grover's algorithm as in classical computing?
Certainly! Imagine you have $K=2^k$ copies of the search oracle $U_S$ that you can use. Normally, you'd search by iterating the action $$ H^{\otimes n}(\mathbb{I}_n-2|0\rangle\langle 0|^{\otimes n})H^{\otimes n}U_S, $$ starting from an initial state $(H|0\rangle)^{\otimes n}$. This takes time $\Theta(\sqrt{N})$. (I'm using $\mathbb{I}_n$ to denote the $2^n\times 2^n$ identity matrix.)
You could replace this with $2^k$ parallel copies, each indexed by an $x\in\{0,1\}^k$, using $$ \left(\mathbb{I}_k\otimes H^{\otimes (n-k)}\right)\mathbb{I}_k\otimes(\mathbb{I}_{n-k}-2|0\rangle\langle 0|^{\otimes (n-k)})\left(\mathbb{I}_k\otimes H^{\otimes (n-k)}\right)U_S $$ and starting from a state $|x\rangle(H|0\rangle)^{\otimes(n-k)}$ The time required for running these would be reduced to $O(\sqrt{N/K})$, at the cost of requiring $K$ times more space.
In a scaling sense, one might consider this an irrelevant result. If you have a fixed number of oracles, $K$, then you get a fixed ($\sqrt{K}$) improvement (just like, if you have $K$ parallel classical cores, the best improvement you can get is a factor of $K$), and that does not change the scaling. But it does change the fundamental running time. We know that Grover's algorithm is exactly optimal. It takes the absolute minimum time possible with a single oracle. So, knowing that you get a $\sqrt{K}$ improvement in time is useful with regards to that benchmark of a specific running time at a specific value of $N$.
In a sense, if we were doing it in parallel on different nodes, you would save time for running. But if we talk about complexity (that is what we refer to speedup generally), we need a bit of analysis.
You agree that we need about $ \sqrt{N} $ operations for the non-parallel case. Say we have two nodes, and we separate the list of N elements into two lists of size $ N_1,N_2 $. The search on the sub-lists takes about $ \sqrt{N_1},\sqrt{N_2} $.
However, we have that $$ \sqrt{N} = \sqrt{N_1+N_2} \le \sqrt{N_1} + \sqrt{N_2} $$
And you would still need to verify which output among what is returned by the parallel processes is the one you seek. It adds a constant in the complexity so we generally hide it into the $O$ notation.
However, that would still be interesting especially if we have to cluster hardware because we are limited in numbers of qubits or another limitations.
