Grover search under localized dephasing
arXiv:1712.06558 · doi:10.1103/PhysRevA.99.012339
Abstract
Decoherence in quantum searches, and in the Grover search in particular, has already been extensively studied, leading very quickly to the loss of the quadratic speedup over the classical case, when searching for some target (marked) element within a set of size . The noise models used were, however, global. In this paper we study Grover search under the influence of localized partially dephasing noise of rate . We find, that in the case when the size of the affected subspace is much smaller than , and the target is unaffected by the noise, namely when , the quadratic speedup is retained. Once these restrictions are not met, the quadratic speedup is lost. In particular, if the target is affected by the noise, the noise rate needs to scale as in order to keep the speedup. We observe also an intermediate region, where if and the target is unaffected, the speedup seems to obey , which for is worse than the quantum, but better than the classical case. We put obtained results for quantum searches also into perspective of quantum walks and searches on graphs.
arXiv comment14 pages, 5 figures; version contains clarified and expanded texts and updated references
References in corpus (18)
- Quantum Mechanics helps in searching for a needle in a haystack
- Strengths and Weaknesses of Quantum Computing
- A Quantum Random Walk Search Algorithm
- Grover's quantum searching algorithm is optimal
- Theory of Decoherence-Free Fault-Tolerant Universal Quantum Computation
- Decoherence can be useful in quantum walks
- Quantum random walks with decoherent coins
- Quantum walks based on an interferometric analogy
- Quantum walks on quotient graphs
- Effects of Noisy Oracle on Search Algorithm Complexity
- Quantum searches on highly symmetric graphs
- Quantum walks with random phase shifts
- Decoherence in Quantum Walks on the Hypercube
- 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
- Grover's search with local and total depolarizing channel errors
- Fault-ignorant Quantum Search
Cited by in corpus (7)
- Prospect of using Grover's search in the noisy-intermediate-scale quantum-computer era
- Accelerating Grover Adaptive Search: Qubit and Gate Count Reduction Strategies with Higher-Order Formulations
- A Benchmarking Study of Quantum Algorithms for Combinatorial Optimization
- Complementarity between Success Probability and Coherence in Grover Search Algorithm
- Quantum search degeneration under amplitude noise in queries to the oracle
- Invariance of success probability in Grover's quantum search under local noise with memory
- Performance of Grover's search algorithm with diagonalizable collective noises