5
$\begingroup$

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?

$\endgroup$
  • 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 '12 at 19:51
  • 1
    $\begingroup$ @Artem, this is not the element distinctness problem. $\endgroup$ – Craig Feinstein Mar 1 '12 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 '12 at 20:30
  • $\begingroup$ OK, is there anything better than $O(N^{1/3})$? $\endgroup$ – Craig Feinstein Mar 1 '12 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 Vega Mar 4 '12 at 12:27
8
$\begingroup$

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.

$\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.