# Quantum algorithms for determining whether two sets intersect

Grover's algorithm is a quantum algorithm that is able to locate a special record in an $N$ element unsorted database in $\Theta(\sqrt{N})$ time. What quantum algorithms are known to determine whether two sets of size $\sqrt{N}$ intersect (so there are $N$ ordered pairs with one element from each set)? Do they beat the $\Theta(\sqrt{N})$ time of Grover's algorithm?

• A hint: take a look at the element distinctness problem. I am not sure if this question is research level. – Artem Kaznatcheev Mar 1 '12 at 19:51
• @Artem, this is not the element distinctness problem. – Craig Feinstein Mar 1 '12 at 20:18
• of course not, but the element distinctness problem trivially gives you a $O(N^{1/3})$ algorithm. – Artem Kaznatcheev Mar 1 '12 at 20:30
• OK, is there anything better than $O(N^{1/3})$? – Craig Feinstein Mar 1 '12 at 20:50
• Nope, unless you use an unusual query model. Otherwise such an algorithm would give you a faster way to solve the element distincness problem, whose complexity is proven to be tight. Check the link @Artem provided. – Juan Bermejo Vega Mar 4 '12 at 12:27

But this problem (let's call it Set Disjointness or SD) has query complexity $\Theta(n^{2/3})$ when the two sets are of size $n$.
To show a lower bound of $\Omega(n^{2/3})$, we can reduce ED to SD. Here's a simple probabilistic reduction: Take any ED instance. Randomly partition it into two parts and solve SD on this instance. If it was a NO instance of ED, it will be a NO instance of SD. If it was a YES instance, then with probability >= 1/2, it will be a YES instance of SD.
For an upper bound of $O(n^{2/3})$, I can't, off the top of my head, think of a reduction to a known problem. The easiest way I can think of is to use Ambainis' algorithm for ED, but modify it to work for this problem. It is known that Ambinis' algorithm actually works for any two-place relation R(.,.), not just the relation EQUALITY(x,y), which is 1 iff x and y are the same. So we can use the relation R(x,y) = 1 iff x = y and x and y are from different sets.