We address the case in which querying the oracle in Grover’s algorithm is exposed to noise including phase distortions. The oracle-box wires can be altered by an opposing party that tries to prevent reception of correct data from the oracle. This situation reflects an experienced truth that any access to prophetic knowledge cannot be common and direct. To study this problem, we introduce a simple model of collective phase distortions on the basis of a phase-damping channel. In the model, the probability of success is not altered via the oracle-box wires per se . Phase distortions of the considered type can hardly be detected via any one-time query to the oracle. However, the probability of success is significantly changed when such errors are introduced as an intermediate step in the Grover iteration. We investigate the probability of success with respect to variations of the parameter that characterizes the amount of phase errors. It turns out that the probability of success decreases significantly even if the error is not very high. Moreover, this probability quickly reduces to the value of one half, which corresponds to the completely mixed state. We also study trade-off relations between quantum coherence and the probability of success in the presence of noise of the considered type.
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.
Grover’s search algorithm and similar techniques are widely used in quantum information science. Communication lines with the so-called oracle are one of inevitable vulnerabilities of quantum search. The impact of localized dephasing and amplitude damping on Grover’s algorithm had already been discussed in recent literature. In this paper, we study the influence of depolarization in the oracle-box wires on the search process. It is shown that even low level of noise is sufficient to degenerate Grover’s algorithm. Complementarity relations between the relative entropy of coherence and the success probability in the presence of depolarization are studied as well.
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.
Learning and sensing are among the most promising applications of quantum technology, often with provable quantum advantages. In any realistic experiment, however, noise threatens to erase these advantages as the problem size grows. We introduce oracle distillation, a procedure that distills many queries to a noisy oracle into a single high-fidelity oracle. Here the oracle, an unknown unitary from a known family, models the interface through which a quantum device learns about an unknown system. We construct an explicit protocol that distills any Boolean oracle, both under adversarial noise that corrupts a constant fraction of the input qubits and under i.i.d. depolarizing noise at a constant rate on every qubit. At the heart of the protocol is the weak query, in which the device deliberately queries the oracle only weakly, trading response strength for the ability to correct errors. Our protocol is near-optimal among all protocols that distill the oracle while keeping its errors correctable, revealing a fundamental tension between these two requirements. An important implication of the protocol is a threshold theorem: every Boolean oracle problem whose quantum advantage is polynomial in the domain size, including Grover search,
k-forrelation, and Simon's problem, retains a quantum advantage whenever the per-qubit depolarizing rate is below a constant threshold. In particular, the quadratic quantum advantage of Grover search, long believed fragile under noise, survives nearly intact at low error rates even when almost every query involves errors on one or more qubits. We further extend the protocol to fractional and continuous-time Boolean oracles. Quantum error correction can thus protect not only prescribed operations but also unknown dynamics. Our results make a large family of quantum advantages in learning robust against noise and open a path toward robust computational sensing.
Grover's quantum search algorithm provides a quadratic quantum advantage over classical algorithms across a broad class of unstructured search problems.The original protocol is probabilistic, returning the desired result with significant probability on each query but, in general, requiring several iterations of the algorithm.We present a modified version to return the correct result with certainty without having user control over the quantum search oracle.Our deterministic, two-parameter "D2p" protocol utilizes generalized phase rotations replacing the phase inversions after a standard oracle query.The D2p protocol achieves a 100% success rate in no more than one additional iteration compared to the optimal number of steps as in the original Grover's search enabling the same quadratic speedup.We also provide a visualization using the Bloch sphere for enhanced geometric intuition.
A randomly walking quantum particle searches in Grover’s Θ(√ N) iterations for a marked vertex on the complete graph of N vertices by repeatedly querying an oracle that flips the amplitude at the marked vertex, scattering by a “coin” flip, and hopping. Physically, however, potential energy barriers can hinder the hop and cause the search to fail, even when the amplitude of not hopping decreases with N. We correct for these errors by interpreting the quantum walk search as an amplitude amplification algorithm and modifying the phases applied by the coin flip and oracle such that the amplification recovers the Θ(√ N) runtime.