Physics – Quantum Physics
Scientific paper
2003-11-10
Physics
Quantum Physics
12 pages, 2 figures. Some new results added; some errors corrected
Scientific paper
The polynomial method and the Ambainis's lower bound (or \emph{Alb}, for short) method are two main quantum lower bound techniques. While recently Ambainis showed that the polynomial method is not tight, the present paper aims at studying the power and limitation of \emph{Alb}'s. We first use known \emph{Alb}'s to derive $\Omega(n^{1.5})$ lower bounds for \textsc{Bipartiteness}, \textsc{Bipartiteness Matching} and \textsc{Graph Matching}, in which the lower bound for \textsc{Bipartiteness} improves the previous $\Omega(n)$ one. We then show that all the three known Ambainis's lower bounds have a limitation $\sqrt{N\cdot \min\{C_0(f), C_1(f)\}}$, where $C_0(f)$ and $C_1(f)$ are the 0- and 1-certificate complexity, respectively. This implies that for some problems such as \textsc{Triangle}, $k$-\textsc{Clique}, and \textsc{Bipartite/Graph Matching} which draw wide interest and whose quantum query complexities are still open, the best known lower bounds cannot be further improved by using Ambainis's techniques. Another consequence is that all the Ambainis's lower bounds are not tight. For total functions, this upper bound for \emph{Alb}'s can be further improved to $\min \{\sqrt{C_0(f)C_1(f)}, \sqrt{N\cdot CI(f)}\}$, where $CI(f)$ is the size of max intersection of a 0-and a 1-certificate set. Again this implies that $Alb$'s cannot improve the best known lower bound for some specific problems such as \textsc{And-Or Tree}, whose precise quantum query complexity is still open. Finally, we generalize the three known \emph{Alb}'s and give a new \emph{Alb} style lower bound method, which may be easier to use for some problems.
No associations
LandOfFree
On the power of Ambainis's lower bounds 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 On the power of Ambainis's lower bounds, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the power of Ambainis's lower bounds will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-421998