Quantum complexity of maximum inner product search Given two matrices $X \in \mathbb{R}^{m \times k}$, $Y \in \mathbb{R}^{n \times k}$, maximum inner product search (MIPS) asks for the largest $l$ entries of $X Y^T$.  Typically $k \ll m, n$ (many small dot products).  In the approximate version, we ask for entries within a factor $\alpha &lt; 1$ of the true largest.

Unfortunately, Ahle et al. show that an approximate solution to MIPS in subquadratic time $O(k^{O(1)} (mn)^{1-\epsilon})$ for $\epsilon &gt; 0$ would contradict the strong exponential time hypothesis.  Terminology note: Ahle et al. calls it inner product similarity join (IPS) instead of MIPS.

Ahle et al. consider only classical complexity.  However, it is easy to beat the subquadratic limit using a quantum computer: applying Grover to the $m \times n$ search space gives $\tilde{O}(k \sqrt{m n})$ for $l = 1$.

Question: Is $\tilde{O}(k \sqrt{m n})$ the right quantum complexity for $l = 1$?  What about for larger $l \ll m, n$?
I think the quantum complexity is right for $l=1$, if a quantum oracle $O$ that can compute the inner product of any two row vectors from $X$ and $Y$, namely, $O: |i\rangle|j\rangle|0\rangle \rightarrow |i\rangle|j\rangle|X_i\cdot X_j\rangle$, is provided. Computing the inner product of two $k$-length vectors requires time $\mathcal{O}(k)$. Based on this oracle, we can use the quantum algorithm for finding minimun to find maximum and the oracle complexity will scales as $\mathcal{O}(\sqrt{mn})$. Then the total time complexity will be $\mathcal{O}(k\sqrt{mn})$.

The above algorithm can be utilized to find $l$ largest entries of $XY^{T}$ in a successive manner. For example, finding the second largest entry is equivalent to finding the largest entry of the rest entries when we 'take' the true largest one away. Therefore, i think the quantum complexity for finding $l$ largest entries will be $\mathcal{O}(lk\sqrt{mn})$.