Noise in Grover's Quantum Search Algorithm
arXiv:quant-ph/9903070 · doi:10.1103/PhysRevA.61.012301
Abstract
Grover's quantum algorithm improves any classical search algorithm. We show how random Gaussian noise at each step of the algorithm can be modelled easily because of the exact recursion formulas available for computing the quantum amplitude in Grover's algorithm. We study the algorithm's intrinsic robustness when no quantum correction codes are used, and evaluate how much noise the algorithm can bear with, in terms of the size of the phone book and a desired probability of finding the correct result. The algorithm loses efficiency when noise is added, but does not slow down. We also study the maximal noise under which the iterated quantum algorithm is just as slow as the classical algorithm. In all cases, the width of the allowed noise scales with the size of the phone book as N^-2/3.
17 pages, 2 eps figures. Revised version. To be published in PRA, December 1999
References in corpus (3)
Cited by in corpus (20)
- Implementation of quantum search algorithm using classical Fourier optics
- Effects of Noisy Oracle on Search Algorithm Complexity
- Experimental NMR Realization of A Generalized Quantum Search Algorithm
- 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
- Quantum computation speedup limits from quantum metrological precision bounds
- A Benchmarking Study of Quantum Algorithms for Combinatorial Optimization
- Complementarity between Success Probability and Coherence in Grover Search Algorithm
- Fault-ignorant Quantum Search
- Robust quantum searching with spontaneously decaying qubits
- Implementation of many-qubit Grover search with trapped ultracold ions
- Subspace projection method for unstructured searches with noisy quantum oracles using a signal-based quantum emulation device
- 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
- Phases and phase transition in Grover's algorithm with systematic noise
- Noise tolerance via reinforcement: Learning a reinforced quantum dynamics
- Quantum algorithm for unstructured search of ranked targets
- Performance of Grover's search algorithm with diagonalizable collective noises