Noise effect on Grover algorithm
arXiv:0801.1261 · doi:10.1140/epjd/e2007-00295-1
Abstract
The decoherence effect on Grover algorithm has been studied numerically through a noise modelled by a depolarizing channel. Two types of error are introduced characterizing the qubit time evolution and gate application, so the noise is directly related to the quantum network construction. The numerical simulation concludes an exponential damping law for the successive probability of the maxima as time increases. We have obtained an allowed-error law for the algorithm: the error threshold for the allowed noise behaves as Eth(N) ~ 1/N1.1 (N being the size of the data set). As the power of N is almost one, we consider the Grover algorithm as robust to a certain extent against decoherence. This law also provides an absolute threshold: if the free evolution error is greater than 0.043, Grover algorithm does not work for any number of qubits affected by the present error model. The improvement in the probability of success, in the case of two qubits has been illustrated by using a fault-tolerant encoding of the initial state by means of the [[7,1,3]] quantum code.
Accepted to be published in Eur. Phys. J. D (2008)
References in corpus (10)
- Quantum Mechanics helps in searching for a needle in a haystack
- Experimental realization of a quantum algorithm
- Resilient Quantum Computation: Error Models and Thresholds
- A Portable High-Quality Random Number Generator for Lattice Field Theory Simulations
- Effects of Noisy Oracle on Search Algorithm Complexity
- The effect of unitary noise on Grover's quantum search algorithm
- Noise in Grover's Quantum Search Algorithm
- Decoherence on Grover's quantum algorithm: perturbative approach
- Dissipative decoherence in the Grover algorithm
- Phase diagram for the Grover algorithm with static imperfections
Cited by in corpus (21)
- Prospect of using Grover's search in the noisy-intermediate-scale quantum-computer era
- Variational Quantum Linear Solver with Dynamic Ansatz
- Noise effects in the quantum search algorithm from the computational complexity point of view
- Quantum computation speedup limits from quantum metrological precision bounds
- Grover's search with local and total depolarizing channel errors
- Special Session: Noisy Intermediate-Scale Quantum (NISQ) Computers -- How They Work, How They Fail, How to Test Them?
- A Benchmarking Study of Quantum Algorithms for Combinatorial Optimization
- Complementarity between Success Probability and Coherence in Grover Search Algorithm
- Effect of qubit losses on Grover's quantum search algorithm
- Using Quantum Switches to Mitigate Noise in Grover's Search Algorithm
- Subspace projection method for unstructured searches with noisy quantum oracles using a signal-based quantum emulation device
- A classical limit of Grover's algorithm induced by dephasing: Coherence vs entanglement
- ArsoNISQ: Analyzing Quantum Algorithms on Near-Term Architectures
- Concise Quantum Associative Memories with Nonlinear Search Algorithm
- Simulation of static and random errors on Grover's search algorithm implemented in a Ising nuclear spin chain quantum computer with few qubits
- Invariance of success probability in Grover's quantum search under local noise with memory
- Noise tolerance via reinforcement: Learning a reinforced quantum dynamics
- Characterizing error propagation in quantum circuits: the Isotropic Index
- Phases and phase transition in Grover's algorithm with systematic noise
- Noise Effects on the Wilczek-Zee Geometric Phase
- Search Via quantum walks with intermediate measurements