# 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 < 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 > 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})$.

• Finding each entry successively seems terribly slow. Is that really the best way? – Geoffrey Irving Mar 1 '16 at 17:04

The mechanism of finding $l$ largest entries is equivalent to finding $l$ least entries. The quantum algorithm for finding minimum can be slightly changed to find $l$ least entries. In the step 2 of that algorithm, we replace the total running time '$22.5\sqrt{N}+1.4lg(N)^2$' with $18\sqrt{N/l}+1.4lg(N)(lg(N)-lg(l))$ (the result is derived by summing over $l+1$ instead of 2 to $N$ in the proof of lemma 2). Then one of $l$ least elements occurs with a nonnegligible probability. Running the new algorithm about $l$ time to reveal all the least $l$ elements. Therefore, the total running time of new algorithm for finding the $l$ least entries will be $\mathcal{O}(lk\sqrt{mn/l})=\mathcal{O}(k\sqrt{lmn})$. This is only my coarse idea and it might not be precise.