Quantum lower bounds for the set equality problems

Details Quantum lower bounds for the set equality problems Quantum lower bounds for the set equality problems

2003-09-08

arxiv.org/abs/quant-ph/0309068v2

Physics

Quantum Physics

7 pages, improved presentation

Scientific paper

The set equality problem is to decide whether two sets $A$ and $B$ are equal or disjoint, under the promise that one of these is the case. Some other problems, like the Graph Isomorphism problem, is solvable by reduction to the set quality problem. It was an open problem to find any $w(1)$ query lower bound when sets $A$ and $B$ are given by quantum oracles with functions $a$ and $b$. We will prove $\Omega(\frac{n^{1/3}}{\log^{1/3} n})$ lower bound for the set equality problem when the set of the preimages are very small for every element in $A$ and $B$.

Affiliated with

Also associated with

No associations

Rating

Quantum lower bounds for the set equality problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Quantum lower bounds for the set equality problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum lower bounds for the set equality problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-47946