Exact Quantum Search by Parallel Unitary Discrimination Schemes

Abstract

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/3N+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.

8 pages (revtex4), 6 figures. Revised version with some typo error corrections and some clearer statement. Accepted by Phys.Rev.A .Comments are welcome!

References in corpus (11)

• Quantum Mechanics helps in searching for a needle in a haystack
• Strengths and Weaknesses of Quantum Computing
• Grover's quantum searching algorithm is optimal
• Grover Algorithm with zero theoretical failure rate
• Statistical distinguishability between unitary operations
• Using entanglement improves precision of quantum measurements
• On Arbitrary Phases in Quantum Amplitude Amplification
• Phase matching in quantum searching
• Entanglement Is Not Necessary for Perfect Discrimination between Unitary Operations
• Arbitrary phase rotation of the marked state can not be used for Grover's quantum search algorithm
• Local Distinguishability of Multipartite Unitary Operations

Cited by in corpus (5)

• The Perfect Distinguishability of Quantum Operations
• Optimal quantum discrimination of single-qubit unitary gates between two candidates
• Two Notes on Grover's Search: Programming and Discriminating
• Optimal Perfect Distinguishability between Unitaries and Quantum Operations
• Quantum Approximation of Normalized Schatten Norms and Applications to Learning