<p>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 <a href="http://arxiv.org/abs/quant-ph/9607014" rel="nofollow">quantum algorithm for finding minimun</a> 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})$.</p>

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

CC BY-SA 3.0
2016-03-01T17:04:48.280Z
Finding each entry successively seems terribly slow.  Is that really the best way?
Geoffrey Irving
CC BY-SA 3.0
2016-03-01T14:40:08.740Z
2016-03-01T14:40:08.740Z
Chao-Hua Yu
<p>The mechanism of finding $l$ largest entries is equivalent to finding $l$ least entries. The <a href="http://arxiv.org/abs/quant-ph/9607014" rel="nofollow">quantum algorithm for finding minimum</a> 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.</p>

CC BY-SA 3.0
2016-03-03T02:12:07.277Z
2016-03-03T02:25:24.350Z
2016-03-03T02:25:24.350Z
Chao-Hua Yu
<p>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.</p>

<p>Unfortunately, <a href="http://arxiv.org/abs/1510.02824v2" rel="nofollow">Ahle et al.</a> 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.</p>

<p>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$.</p>

<p><strong>Question</strong>: Is $\tilde{O}(k \sqrt{m n})$ the right quantum complexity for $l = 1$?  What about for larger $l \ll m, n$?</p>

<approximation-algorithms><quantum-computing><linear-algebra>
Quantum complexity of maximum inner product search
Geoffrey Irving
# Quantum complexity of maximum inner product search

(Asked by: username_0 on 2016-02-28)

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.](http://arxiv.org/abs/1510.02824v2) 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$?

**Tags:** approximation-algorithms, quantum-computing, linear-algebra


---

## 2 answers

### Answer by username_1 on 2016-03-01. Score: 2

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](http://arxiv.org/abs/quant-ph/9607014) 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})$.

> **Comments:**
> **username_0**: Finding each entry successively seems terribly slow.  Is that really the best way?  

---

### Answer by username_1 on 2016-03-03. Score: 2

The mechanism of finding $l$ largest entries is equivalent to finding $l$ least entries. The [quantum algorithm for finding minimum](http://arxiv.org/abs/quant-ph/9607014) 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.


---

