Let $\mathcal{H} : \{0,1\}^* \rightarrow \{1,\cdots,n\}$ be a hash function.
I believe that in the Random Oracle model, the probability that an adversary $A$ can find a message $M$ such that $\mathcal{H}(M) \leq k$ is at most $(q+1) \frac{k}{n}$, where $q$ is the number of queries $A$ makes to $\mathcal{H}$.
What happens for a quantum adversary $B$, which can query $\mathcal{H}$ in superposition? I suspect that the probability that $B$ produces a message $M$ such that $\mathcal{H}(M)\leq k$ is bounded by $c q^2 \frac{k}{n}$, where $q$ i the number of quantum queries that $B$ makes to $\mathcal{H}$ and $c$ some constant.
I suspect this because this can be done with Grover's algorithm and I heard that Grover's Algorithm is optimal in some setting.
Is this true? What values of $c$ would work? How would you prove this?