External environment influences on Grover’s search algorithm modeled by quantum noise are investigated. The algorithm is shown to be robust under that external dissipation. Explicitly we prove that the resulting search positive maps acting on unsorted N-dimensional database made of projective density matrices depend on x the strength of the environment, and that there are infinitely many x values for which search is successful O ( N ) after queries. These algorithms are quantum entropy increasing.
External influences in the form of quantum noise on Grover’s search algorithm are investigated. The study shows that the algorithm can be robust under such external dissipation. The effect of noise is described by a completely positive trace preserving map, acting on an unsorted N‐dimensional database made of projective density matrices. To evaluate the efficiency of the algorithm two figures of merit are used, the radial fidelity giving the projection between the Bloch vectors of target and final density operators, and the cosine of angular fidelity between the same vectors. Explicitly we prove that the resulting search positive map depends on x, the strength of the coupling to the environment, and that there are infinitely many x values, named good x’s and bad x’s, for which search is successful after O(N) queries, or fails, respectively . Next we study the information theoretic aspects of the dissipative quantum search algorithm. To this end we view the initial state as a pure qubit signal entering through a cascade of quantum channels, each channel described by a completely positive map, and corresponds to the iterations of the algorithm. This map is identical to the dissipative search map of the algorithm for which the parameter x now characterizes the influence of the noisy channel exercised upon the incoming quantum signal. The process of searching is understood as transmission of the initial signal/item through the composite channel made by O(N) elementary channels. The quality of this transmission corresponds to the fidelity of targeting the wanted item in the quantum database, and is studied in terms of the majorization/quantum entropy of the input‐output density matrix, and by the entropy exchanged between the qubit signal/item and an external environment.
Grover proposed how a quantum computer can find a single marked object in a database of size N by using only O(N) queries of the oracle that identifies the object with the probability of finding the marked object being not exactly 1.The Grover quantum search algorithm is generalized to deal with an arbitrary mixed initial state.The probability of finding the marked object is calculated and it is found that it depends strongly on the specific initial state.Our results contribute to analyze the influence of quantum noise on Grover algorithm based on pure state.Finally,we give few examples to show that for some extremely mixed initial states.
We analyze the robustness of Grover's quantum search algorithm performed by a quantum register under a possibly time-correlated noise acting locally on the qubits. We model the noise as originating from an arbitrary but fixed unitary evolution
U of some noisy qubits. The noise can occur with some probability in the interval between any pair of consecutive noiseless Grover evolutions. Although each run of the algorithm is a unitary process, the noise model leads to decoherence when all possible runs are considered. We derive a set of unitary
U's, called good noises, for which the success probability of the algorithm at any given time remains unchanged with varying nontrivial total number
m of noisy qubits in the register. The result holds irrespective of the presence of any time correlations in the noise. We show that only when
U is either of the Pauli matrices ${\ensuremath{\sigma}}_{x}$ and ${\ensuremath{\sigma}}_{z}$ (which give rise to
m-qubit bit-flip and phase-damping channels, respectively, in the time-correlation-less case), the algorithm's success probability stays unchanged when increasing or decreasing
m. In contrast, when
U is the Pauli matrix ${\ensuremath{\sigma}}_{y}$ (giving rise to
m-qubit bit-phase flip channel in the time-correlation-less case), the success probability at all times stays unaltered as long as the parity (even or odd) of the total number
m remains the same. This asymmetry between the Pauli operators stems from the inherent symmetry-breaking existing within the Grover circuit. We further show that the positions of the noisy sites are irrelevant in the case of any of the Pauli noises. The results are illustrated in the cases of time-correlated and time-correlation-less noise. We find that the former case leads to a better performance of the noisy algorithm. We also discuss physical scenarios where our chosen noise model is of relevance.
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.
The quantum search algorithm is one of the milestones of quantum algorithms. Compared with classical algorithms, it shows quadratic speed-up when searching marked states in an unsorted database. However, the success rates of quantum search algorithms are sensitive to the number of marked states. In this paper, we study the relation between the success rate and the number of iterations in a quantum search algorithm of given λ=M/N, where M is the number of marked state and N is the number of items in the dataset. We develop a robust quantum search algorithm based on Grover–Long algorithm with some uncertainty in the number of marked states. The proposed algorithm has the same query complexity ON as the Grover’s algorithm, and shows high tolerance of the uncertainty in the ratio M/N. In particular, for a database with an uncertainty in the ratio M±MN, our algorithm will find the target states with a success rate no less than 96%.