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

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

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

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

CC BY-SA 3.0
2012-03-24T14:20:08.783Z
2012-03-24T14:20:08.783Z
Robin Kothari
<p>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?</p>

CC BY-SA 3.0
2012-03-01T19:51:29.147Z
A hint: take a look at the [element distinctness problem](http://en.wikipedia.org/wiki/Element_distinctness_problem). I am not sure if this question is research level.
Artem Kaznatcheev
CC BY-SA 3.0
2012-03-01T20:18:22.980Z
@Artem, this is not the element distinctness problem.
Craig Feinstein
CC BY-SA 3.0
2012-03-01T20:30:54.637Z
of course not, but the element distinctness problem trivially gives you a $O(N^{1/3})$ algorithm.
Artem Kaznatcheev
CC BY-SA 3.0
2012-03-01T20:50:58.807Z
OK, is there anything better than $O(N^{1/3})$?
Craig Feinstein
CC BY-SA 3.0
2012-03-04T12:27:10.273Z
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
<quantum-computing>
Quantum algorithms for determining whether two sets intersect
Craig Feinstein
# Quantum algorithms for determining whether two sets intersect

(Asked by: username_0 on 2012-03-01)

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?

**Tags:** quantum-computing

> **Comments:**
> **username_1**: A hint: take a look at the [element distinctness problem](http://en.wikipedia.org/wiki/Element_distinctness_problem). I am not sure if this question is research level.  
> **username_0**: @Artem, this is not the element distinctness problem.  
> **username_1**: of course not, but the element distinctness problem trivially gives you a $O(N^{1/3})$ algorithm.  
> **username_0**: OK, is there anything better than $O(N^{1/3})$?  
> **username_2**: 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.  

---

## 1 answers

### Answer by username_3 on 2012-03-24. Score: 8 | Accepted answer

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.


---

