For searching an unsorted database with N items, a classical computer requires O(N) steps but Grover's quantum searching algorithm requires only O(¿N) steps. However, it is also known that Grover's algorithm is effective in the case where the initial amplitude distribution of dataset is uniform, but is not always effective in the non-uniform case. In this paper, we will consider the influence of initial amplitude distribution of dataset for Grover's and Ventura's algorithms. Further, in order to improve the performance of quantum searching, we propose a new algorithm and analyze its dynamics.
For searching an unsorted database with N items, a classical computer requires O(N) steps but Grover's quantum searching algorithm requires only O(¿N) steps. However, it is also known that Grover's algorithm is effective in the case where the initial amplitude distribution of dataset is uniform, but is not always effective in the non-uniform case. In this paper, we will consider the influence of initial amplitude distribution of dataset for Grover's and Ventura's algorithms. Further, in order to improve the performance of quantum searching, we propose a new algorithm and analyze its dynamics.
For searching any item in an unsorted database with N items, Grover's quantum searching algorithm takes only O(√N) steps, which is much faster than O(N) steps required for a classical computer. However, it is known that Grover's algorithm is effective only in the case where the initial amplitude distribution of dataset is uniform. On the other hand, Ventura has also proposed a quantum searching algorithm. The algorithm is effective only in the special case for the initial amplitude distribution. Therefore, we have proposed an effective quantum searching algorithm in another case in the previous paper. In this paper, we generalize the previous algorithm and propose several effective algorithms in several cases where initial amplitude distributions of dataset are non-uniform. Further, in order to show the effectiveness of the algorithms, we analyze their dynamics.
For searching any item in an unsorted database with N items, a classical computer takes O(N) steps but Grover’s quantum searching algorithm takes only O( √ N) steps. However, it is also known that Grover’s algorithm is effective only in the case where the initial amplitude distribution of dataset is uniform, but is not always effective in the nonuniform case. In this paper, we propose some quantum search algorithms. First, we propose an algorithm in analog time based on quantum walk by solving the schrodinger equation. The proposed algorithm shows best performance in optimum time. Next, we will apply the result to Grover search algorithm. It is shown that the proposed algorithm shows better performance than the conventional one. Further, we propose the improved algorithm by introducing the idea of the phase rotation. The algorithm shows best performance compared with the conventional ones.
The problem of Grover's and Ventura's algorithms are not effective in any arbitrary amplitude distribution are studied.First,combining with the characteristics of quantum computing,a new algorithm is proposed and its amplitude dynamics with recursive function are analyzed.Further,a simulation with Matlab to compare the performance of three algorithms are made.Finally,the conclusion that the proposed algorithm can make up for Grover's and Ventura's deficiencies.If the value of m in advance is known,the appropriate algorithm to increase the probability of success can be seected.
IntroductionFor a search problem associated with a unsorted database, the remarkable Grover's quantum algorithm (1) provides a quadratic speedup over its classical counterpart.The search problem can be described as follows: for a given function f , there exists one unknown element in the set {0, 1, ..., N -1} that satisfies f (x)=-1, say x = τ, whereas the other N -1o n e sg i v e f (x)=1.How many times of evaluations of f are required to determine the element τ for f (τ)=-1?Through a conventional algorithm, one needs O(N) trials to achieve this aim.How about the utility of quantum algorithm for the search?For the scenario in the quantum world, the search problem can be rephrased in the quantum mechanical language: for a given unitary operator I τ , that is sometimes called the oracle operator, and a set of state vectors (orthonormal basis): s = {|0 , |1 , ..., |N -1 }, I τ |x = |x for all states in the set except I τ |x = -|x for x = τ.H owma n yqueriesofI τ are required to determine |τ ?By Grover's algorithm, one needs only O( √ N) quantum mechanical steps to find the marked state |τ out.It has been shown that Grover's algorithm is optimal since it needs minimal oracle calls to perform a quantum search (2).The quantum searching process will be briefly reviewed as follows.The first step of Grover's algorithm is to prepare a superposition state of all elements with uniform probability amplitude:Then apply the Grover kernel G = -I η I τ to |s ,w h er eI η is a unitary operator and contains no bias against the marked state.For large N,a f t e ra b o u tm = π √ N/4 repetitions of G operations, the probability to observe |τ is close to one, i.e., G m |s ∼ |τ .( 2 ) Since every single G involves one query of I τ ,onlyO( √ N) searching steps are required for a quantum search task.In what follows, we will first investigate on the general SU(2) formulation for the kernel of Grover's searching operator G.The discussions of quantum searching certainty, robustness, and the analog analogue version of the Grover's algorithm will be given afterwards.
Grover quantum search algorithm access the unsorted database O (N~(1/2)) times,however,the probability of acquiring so- lutions usually falls with the increase of the number of solutions,the reason of which is analyzed and an improved algorithm based on en- larging searching space is proposed with a new parameter i to make the algorithm controllable in order to trade off between success proba- bility and iterative steps.Simulated experiments of the reciprocal problem showcase that this proposed algorithm can find solutions with higher probability than traditional Grover algorithm at the condition of equivalent iterative steps,and the success probability can even be increased if the iterative steps is unlimited.Thus,it can conclude that our proposed algorithm is more efficient and effective.The validity of the improved algorithm is manifested by experiment.
In this paper, Grover's quantum search algorithm is analyzed using a classical computer by calculating the amplitudes and the probabilities of finding a single marked state for n=5, 10, 15, 20, 25, and 27 qubit states.The calculations show that the marked state can be found in 𝒪(√𝑁) iterations, where 𝑁 = 2 ( is the number of items.The possibility of improving Grover's search algorithm to find a single item in N search elements is discussed by calculating the amplitudes and hence the probabilities of finding a single marked state for n=5, 10, 15, 20, 25, 30, 35, 40, 45, and 50 qubit states.The calculations showed that the marked state could be found with sufficiently high probability in 𝒪(ln (𝑁)) iterations.This is quite a remarkable speed-up that can be achieved to find a single marked element in an unsorted N search element.