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?
$\begingroup$
$\endgroup$
5
-
2$\begingroup$ A hint: take a look at the element distinctness problem. I am not sure if this question is research level. $\endgroup$– Artem Kaznatcheev ♦Mar 1, 2012 at 19:51
-
1$\begingroup$ @Artem, this is not the element distinctness problem. $\endgroup$– Craig FeinsteinMar 1, 2012 at 20:18
-
5$\begingroup$ of course not, but the element distinctness problem trivially gives you a $O(N^{1/3})$ algorithm. $\endgroup$– Artem Kaznatcheev ♦Mar 1, 2012 at 20:30
-
$\begingroup$ OK, is there anything better than $O(N^{1/3})$? $\endgroup$– Craig FeinsteinMar 1, 2012 at 20:50
-
3$\begingroup$ 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. $\endgroup$– Juan Bermejo VegaMar 4, 2012 at 12:27
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
It's not completely obvious to me that this problem can be reduced to element distinctness (ED). What if the two sets are disjoint, but the sets contain repeated elements? If you just solve ED on the union of the two sets, ED will return YES, but the sets are disjoint.
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.
answered Mar 24, 2012 at 14:20