Exact quantum search by parallel unitary discrimination schemes
- Publication Type:
- Journal Article
- Citation:
- Physical Review A - Atomic, Molecular, and Optical Physics, 2008, 78 (1)
- Issue Date:
- 2008-07-02
Closed Access
| Filename | Description | Size | |||
|---|---|---|---|---|---|
 | 2008004783OK.pdf | 189.87 kB |
Copyright Clearance Process
- Recently Added
- In Progress
- Closed Access
This item is closed access and not available.
We study the unsorted database search problem with items N from the viewpoint of unitary discrimination. Instead of considering the famous O (N) Grover bounded-error algorithm for the original problem, we seek the results for the exact algorithms, i.e., those that succeed with certainty. Under the standard oracle model j (-1) δτ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-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 the exact quantum search with one unique solution can be strictly less than that of the calculation of the OR function. © 2008 The American Physical Society.
Please use this identifier to cite or link to this item: