3
$\begingroup$

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$?

$\endgroup$
1
$\begingroup$

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

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.