For there to be $M> 1$ target items to be searched in an unsorted database of size $N$, with $M/N\ll 1$ for a sufficiently large $N$, we explore the performance of Grover's search algorithm when considering some possible situations that may arise in a four-complex-dimensional subspace, for which in the case of identical rotation angles $\phi=\theta$, we give the maximum success probabilities of finding a desired state and their corresponding numbers of Grover iterations in an approximate fashion. Our analysis reveals that the case of identical rotation angles $\phi=\theta$ is energetically favorable compared to the case $\left| {\theta - \phi } \right|\gg 0$ for boosting the probability to detect a desired state.
For there to be M>1 target items to be searched in an unsorted database of size N, with M/N≪1 for a sufficiently large N, we explore the performance of Grover's search algorithm when considering some possible situations that may arise in a four-complex-dimensional subspace, for which in the case of identical rotation angles ϕ=θ, we give the maximum success probabilities of finding a desired state and their corresponding numbers of Grover iterations in an approximate fashion. Our analysis reveals that the case of identical rotation angles ϕ=θ is energetically favorable compared to the case ∣θ−ϕ∣≫0 for boosting the probability to detect a desired state.
The success probability of a search of M targets from a database of size N, using Grover's search algorithm depends critically on the number of iterations of the composite operation of the oracle followed by Grover's diffusion operation. Although the required number of iterations scales as O(N) for large N, the asymptote is not a good indicator of the optimal number of iterations when M/N is not small. A scheme for the determination of the exact number of iterations, subject to a threshold set for the success probability of the search (probability of detecting the target state(s)), is crucial for the efficacy of the algorithm. In this work, a general scheme for the construction of n-qubit Grover's search algorithm with 1≤M≤N target states is presented, along with the procedure to find the optimal number of iterations for a successful search. It is also shown that for given N and M, there is an upper-bound on the success probability of the algorithm.
Since a quantum system is inevitably influenced by some unpredictable perturbations,we thereby conclude that all the experimental realizations of Grover quantum search algorithm reported were,in fact,achieved in a three-dimensional complex subspace.We also prove that in a two-dimensional complex subspace,for any given initial superposition of basis states |γ0〉=cos β0|α〉+sin β0eiζ|β〉(β0 is a small positive real number,ζ is an arbitrary real number),there exists a set of solutions Fj={(θj,θj-1,…,θ1),(φj,φj-1,…,φ1)} such that a desired state can be found with certainty for some positive integer j≥2,where the phase rotation angles θl and φl are real numbers but not equal to 2k′π,1≤l≤j,k′ is an arbitrary integer.If it is only required that a desired state can be found with high success probability,then as the total number of the desired and undesired states in an unsorted database is sufficiently large the above set of solutions Fj can be written in the form Σji=1θl=Σji=1φl.for a relatively small positive integer j.
Grover's quantum algorithm was developed to solve the problem of searching an unstructured database for a certain unique element. In general, this problem can be formulated as follows: an unstructured database consists of elements and contains one unique element that has a certain property that can be tested with polynomial complexity, and which must be found with minimal time and complexity. Classical methods require querying the database to find the desired element, while Grover's algorithm allows you to perform only approximately steps, which are iterations of the procedure, to the database and be sure that the resulting element will be exactly the desired element with a probability close to 1. As in quantum algorithms aimed at cryptanalysis of symmetric transformations, Grover's algorithm repeats the procedure (Grover's iteration) to increase the probability of obtaining the correct result. Similarly to such algorithms in Grover's method, when iterations are continued after reaching the required number of iterations, the probability of obtaining the correct result decreases. This is due to the fact that during the execution of Grover's iteration, a rotation is performed in the complex space. Thus, each iteration, making a turn, brings the register closer and closer to the desired state, but at a certain point a maximum closeness is reached, at which the continued use of iterations will lead to a turn past the desired state, which will move the state of the system away from the desired state. The database for this algorithm can be any search space consisting of a certain number of elements. So, for example, it can be applied to find a secret key for a symmetric cryptograms formation or to find a collision for a hashing function.
For the case when the search space is confined to a two-dimensional complex subspace,if the total number of an unsorted database is sufficiently large,then a unique desired state can still be found with high success probability provided any two sets of phase rotation angles,which are completely independent(unrelated to each other) but the number of elements in one of the sets is relatively small compared to the total number of an unsorted database,satisfy the multiphase matching equation.In this paper we showed that for a quantum search problem with some specific requirements,one may combine the multiphase matching equation and the classical exhaustive algorithm such that a unique desired state can be found with success probability almost close to unity.Finally,we gave a numerical example.
Abstract We systematically generalize the Grover algorithm in a density matrix formalism by exploiting the underlying two-dimensional subspace of the problem. Using this, we derive analytic expressions for the success probability after arbitrary iterations of the generalized Grover operator with two generic phase angles . We show for the phase matching condition with three iterations, success probability can be achieved only with knowledge about the lower bound , where λ is the ratio of marked to total number of states in the database. This result will improve the quantum search algorithm when applied to databases with unknown number of marked states in the specified regime of λ , at the cost of decreased efficiency in the smaller λ region.
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.