2005/04/30 by Hiroo Azuma · 7 citations
Computer Science · Mathematics · Physics and Astronomy · #Algorithm #Density matrix #Mathematical physics #Mathematics #Operator (biology) #Order (exchange) #Perturbation theory (quantum mechanics) #Physics #Quantum #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Mechanics and Applications #Quantum decoherence #Quantum mechanics #Qubit #quant-ph
paper · pdf · doi:10.1103/physreva.72.042305
published in Physical Review A 72(4) (American Physical Society) · 18 pages, Latex2e, 5 eps figures; v2: comments about precision of approximation with higher order polynomials added; v3: minor corrections
arxiv created 2005/07/29 · openalex publication_date 2005/10/04 · arxiv updated 2011/01/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
In this paper, we study decoherence in Grover's quantum search algorithm using a perturbative method. We assume that each two-state system (qubit) that belongs to a register suffers a phase-flip error (\ensuremathσz error) with probability p independently at every step in the algorithm, where 0\ensuremath\leqslantp\ensuremath\leqslant1. Considering an n-qubit density operator to which Grover's iterative operation is applied M times, we expand it in powers of 2Mnp and derive its matrix element order by order under the large-n limit. [In this large-n limit, we assume p is small enough, so that 2Mnp can take any real positive value or zero. We regard x\ensuremath≡2Mnp (\ensuremath\geqslant0) as a perturbative parameter.] We obtain recurrence relations between terms in the perturbative expansion. By these relations, we compute higher orders of the perturbation efficiently, so that we extend the range of the perturbative parameter that provides a reliable analysis. Calculating the matrix element numerically by this method, we derive the maximum value of the perturbative parameter x at which the algorithm finds a correct item with a given threshold of probability Pth or more. (We refer to this maximum value of x as xc, a critical point of x.) We obtain a curve of xc as a function of Pth by repeating this numerical calculation for many points of Pth and find the following facts: a tangent of the obtained curve at Pth=1 is given by x=(8∕5)(1\ensuremath-Pth), and we have xc>\ensuremath-(8∕5)loge\phantom\rule0.2em0exPth near Pth=0.