The effect of unitary noise on Grover's quantum search algorithm

Abstract

The effect of unitary noise on the performance of Grover's quantum search algorithm is studied. This type of noise may result from tiny fluctuations and drift in the parameters of the (quantum) components performing the computation. The resulting operations are still unitary, but not precisely those assumed in the design of the algorithm. Here we focus on the effect of such noise in the Hadamard gate $W$, which is an essential component in each iteration of the quantum search process. To this end $W$ is replaced by a noisy Hadamard gate $U$. The parameters of $U$ at each iteration are taken from an arbitrary probability distribution (e.g. Gaussian distribution) and are characterized by their statistical moments around the parameters of $W$. For simplicity we assume that the noise is unbiased and isotropic, namely all noise variables in the parametrization we use have zero average and the same standard deviation $\epsilon$. The noise terms at different calls to $U$ are assumed to be uncorrelated. For a search space of size $N=2^n$ (where $n$ is the number of qubits used to span this space) it is found that as long as $\epsilon <O(n^{-1/2}{N}^{-1/4})$, the algorithm maintains significant efficiency, while above this noise level its operation is hampered completely. It is also found that below this noise threshold, when the search fails, it is likely to provide a state that differs from the marked state by only a few bits. This feature can be used to search for the marked state by a classical post-processing, even if the quantum search has failed, thus improving the success rate of the search process.

References in corpus (19)

• Quantum Mechanics helps in searching for a needle in a haystack
• Good Quantum Error-Correcting Codes Exist
• Decoherence Free Subspaces for Quantum Computation
• Strengths and Weaknesses of Quantum Computing
• Multiple Particle Interference and Quantum Error Correction
• Grover's quantum searching algorithm is optimal
• Quantum computers can search rapidly by using almost any transformation
• Implementation of a Quantum Search Algorithm on a Nuclear Magnetic Resonance Quantum Computer
• Theory of Decoherence-Free Fault-Tolerant Universal Quantum Computation
• Quantum computers can search arbitrarily large databases by a single query
• Grover's search algorithm: An optical approach
• Robustness of Decoherence-Free Subspaces for Quantum Computation
• Grover's Quantum Search Algorithm for an Arbitrary Initial Amplitude Distribution
• Nested quantum search and NP-complete problems
• Analysis of Generalized Grover's Quantum Search Algorithms Using Recursion Equations
• Single quantum querying of a database
• Dissipative dynamics in a quantum register
• Generalized Quantum Search with Parallelism
• Decoherence on Grover's quantum algorithm: perturbative approach

Cited by in corpus (26)

• Dynamics of Loschmidt echoes and fidelity decay
• Effects of Noisy Oracle on Search Algorithm Complexity
• One dimensional quantum walk with unitary noise
• Noise effect on Grover algorithm
• Prospect of using Grover's search in the noisy-intermediate-scale quantum-computer era
• Noise effects in the quantum search algorithm from the computational complexity point of view
• Grover search under localized dephasing
• A quantitative model for the effective decoherence of a quantum computer with imperfect unitary operations
• Quantum computation speedup limits from quantum metrological precision bounds
• Grover's search with local and total depolarizing channel errors
• A Benchmarking Study of Quantum Algorithms for Combinatorial Optimization
• Complementarity between Success Probability and Coherence in Grover Search Algorithm
• Classical versus quantum errors in quantum computation of dynamical systems
• Fault-ignorant Quantum Search
• Dynamics of discrete-time quantum walk with time-correlated unitary noise
• Effect of qubit losses on Grover's quantum search algorithm
• Higher order perturbation theory for decoherence in Grover's algorithm
• Robust quantum minimum finding with an application to hypothesis selection
• Theoretical Analyses of Quantum Counting against Decoherence Errors
• Invariance of success probability in Grover's quantum search under local noise with memory
• Performance of Grover's search algorithm with diagonalizable collective noises
• Characterizing error propagation in quantum circuits: the Isotropic Index
• Quantum algorithm for unstructured search of ranked targets
• Noise tolerance via reinforcement: Learning a reinforced quantum dynamics
• Phases and phase transition in Grover's algorithm with systematic noise
• A note on the runtime of a faulty Hamiltonian oracle