Decoherence on Grover's quantum algorithm: perturbative approach

Abstract

In this paper, we study decoherence on Grover's quantum searching algorithm using a perturbative method. We assume that each two-state system (qubit) suffers σ_{z} error with probability p (0\leq p\leq 1) independently at every step in the algorithm. Considering an n-qubit density operator to which Grover's operation is applied M times, we expand it in powers of 2Mnp and derive its matrix element order by order under the n\to \infty limit. (In this large n limit, we assume p is small enough, so that 2Mnp(\geq 0) can take any real positive value or 0.) This approach gives us an interpretation about creation of new modes caused by σ_{z} error and an asymptotic form of an arbitrary order correction. Calculating the matrix element up to the fifth order term numerically, we investigate a region of 2Mnp (perturbative parameter) where the algorithm finds the correct item with a threshold of probability P_{th} or more. It satisfies 2Mnp<(8/5)(1-P_{th}) around 2Mnp\simeq 0 and P_{th}\simeq 1, and this linear relation is applied to a wide range of P_{th} approximately. This observation is similar to a result obtained by E. Bernstein and U. Vazirani concerning accuracy of quantum gates for general algorithms. We cannot investigate a quantum to classical phase transition of the algorithm, because it is outside the reliable domain of our perturbation theory.

32 pages, Latex 2e, 11 eps figures, v2: comments added in Section 8, minor corrections also added, v3: minor corrections and one reference added

Cited by in corpus (15)

• One dimensional quantum walk with unitary noise
• The effect of unitary noise on Grover's quantum search algorithm
• Noise effect on Grover algorithm
• Grover search under localized dephasing
• 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
• Fault-ignorant Quantum Search
• Using Quantum Switches to Mitigate Noise in Grover's Search Algorithm
• Higher order perturbation theory for decoherence in Grover's algorithm
• A classical limit of Grover's algorithm induced by dephasing: Coherence vs entanglement
• Theoretical Analyses of Quantum Counting against Decoherence Errors
• Invariance of success probability in Grover's quantum search under local noise with memory
• Characterizing error propagation in quantum circuits: the Isotropic Index
• Noise-Resilient Quantum Reinforcement Learning