# Quantum Random Oracle Model

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?

You are right, the success probability of a $q$-query quantum adversary is $\Theta(\frac{k(q+1)^2}{n})$. You can find a proof of the upper and lower bound in this paper.