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.
Grover's algorithm searches an unstructured database with a number of oracle queries that grows only as the square root of its size. Noise erodes this advantage, and we ask, analytically, how quickly. When a depolarizing channel acts on the whole register after every gate layer, it commutes with the gates, and the noisy state is the noiseless one with a coherent weight that decays geometrically with depth. The Grover rotation is not slowed. Its weight decays, the best stopping point moves earlier, and the expected query cost keeps its square-root scaling only while the accumulated noise over the circuit stays small. For independent errors on the qubits we show that the ideal Grover operator freezes any amplitude pushed out of the two-dimensional search plane. This gives the exact effect of a single error: phase flips do most damage early in the search, bit flips late, and combined errors at any time. For large databases it also reduces the noisy search to Bloch-type equations for the part of the state that stays in the plane, in which the algorithm is a rotation and the noise appears as leakage and dephasing. We derive the rates for bit-flip, phase-flip, depolarizing, and amplitude-damping noise and solve the equations. Local noise acts, to leading order, like a global channel strengthened by the number of qubits, so the tolerable error per qubit falls faster than the inverse square root of the database size by one power of the register size. For coherent errors in the rotation angle we bound the success probability by a band that widens linearly with depth. Our results recover, in closed form, scalings found earlier for particular noise models, and they explain why some errors are more harmful than others.
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.
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.