|
|
 |
| |
|
|
|
A New Exponentially Fast Quantum Algorithm for Searching Target in the Unstructured Database |
|
|
|
PP: 13-17 |
|
|
|
doi:10.18576/qpl/110103
|
|
|
|
Author(s) |
|
|
|
Dhananjay P. Mehendale,
|
|
|
|
Abstract |
|
|
| We propose a fresh new idea of cutting the size of the search space (database) to half at each iteration and thus achieve an efficient quantum search algorithm with complexity O(LogN)2. This is exponential speedup over Grover’s algorithm. Grover’s quantum algorithm [6] has been proven to be optimal [1,2,7]. It has been shown that for any number of oracle lookups up to about π/4√N, Grover’s quantum searching algorithm will give the maximal possible probability of finding the desired target [1]. Therefore, as long as the entire setup used for the Grover’s algorithm remains the same i.e. (i) the database to which the unique target belongs remains the same and (ii) we consider to invoke only those oracles which give value 1 for exactly one unique input called the target we cannot do any better. In the quantum algorithm that we propose here we do not change (ii) but we manage to change (i) i.e. we manage to change the search space (database) after each iteration, in fact we manage to reduce its size by half by excluding that half part of the search space having no (or zero) overlap with the target state by making use of the inner product [3] of the the target state and the register corresponding half part of the database under consideration. We show that this simple change in the setup enables us to achieve exponential speedup over Grover’s quantum algorithm. In this new quantum search algorithm the amplitude of the target state is not amplified directly as is done in Grover’s algorithm instead the proposed algorithm reduces the size of the search space by half in each iterative step which indirectly amplifies (doubles) the amplitude of the target state during each iteration and attains the maximal amplitude, ≈ 1, for it in LogN iterations.
|
|
|
|
|
|
|
|
