Physics – Quantum Physics
Scientific paper
2007-09-23
Physics
Quantum Physics
8 pages (revtex4), 6 figures. Revised version with some typo error corrections and some clearer statement. Accepted by Phys.Re
Scientific paper
10.1103/PhysRevA.78.012303
We study the unsorted database search problem with items $N$ from the viewpoint of unitary discrimination. Instead of considering the famous $O(\sqrt{N})$ Grover's the bounded-error algorithm for the original problem, we seek for the results about the exact algorithms, i.e. the ones succeed with certainty. Under the standard oracle model $\sum_j (-1)^{\delta_{\tau j}}|j>< j|$, we demonstrate a tight lower bound ${2/3}N+o(N)$ of the number of queries for any parallel scheme with unentangled input states. With the assistance of entanglement, we obtain a general lower bound ${1/2}(N-\sqrt{N})$. We provide concrete examples to illustrate our results. In particular, we show that the case of N=6 can be solved exactly with only two queries by using a bipartite entangled input state. Our results indicate that in the standard oracle model the complexity of exact quantum search with one unique solution can be strictly less than that of the calculation of OR function.
Duan Runyao
Wu Xiaodi
No associations
LandOfFree
Exact Quantum Search by Parallel Unitary Discrimination Schemes 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 Exact Quantum Search by Parallel Unitary Discrimination Schemes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Exact Quantum Search by Parallel Unitary Discrimination Schemes will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-651649